# 常见算法总结 – 排序篇

#### 1.冒泡排序

public static void bubble(int[] array) {

for (int i = 0; i < array.length - 1; i++) {

for (int j = 0; j + 1  array[j + 1]) {

int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;

}

}

}

}

#### 2.快速排序

public static void quick(int[] array, int begin, int end) {

if (begin >= end) {
return;
}

int beginRange = begin;
int endRange = end;

int compareInt = array[begin];

begin++;

while (begin  compareInt) {
end--;
continue;
}

if (array[begin]  array[begin]) {

int tmp = array[begin];
array[begin] = array[beginRange];
array[beginRange] = tmp;

}

quick(array, beginRange, begin - 1);
quick(array, end + 1, endRange);

return;

}

#### 3.选择排序

public static void selectSort(int[] array) {

if (array.length == 0) {
return;
}

for (int i = 0; i < array.length; i++) {

int min = array[i];
int minIndex = i;

for (int j = i; j < array.length; j++) {
if (array[j] < min) {
min = array[j];
minIndex = j;
}
}

int tmp = array[i];
array[i] = min;
array[minIndex] = tmp;
}
}

#### 4.归并排序

public static void sort(int[] array, int left, int right) {

//1.设置递归的base case
if (left == right) {
return;
}
//2.分别排两边
int mid = left + (right - left) / 2;
sort(array, left, mid);
sort(array, mid + 1, right);
//3.合并
merge(array, left, mid + 1, right);

}

public static void merge(int[] array, int leftPtr, int rightPtr, int rightBound) {

int mid = rightPtr - 1;
int[] temp = new int[rightBound - leftPtr + 1];

int i = leftPtr, j = rightPtr, k = 0;
while (i <= mid && j <= rightBound) {
temp[k++] = array[i] <= array[j] ? array[i++] : array[j++];
}

while (i <= mid) {
temp[k++] = array[i++];
}
while (j <= rightBound) {
temp[k++] = array[j++];
}

//不要忘了把temp数组复制到arr中
for (int m = 0; m < temp.length; m++) {
array[leftPtr + m] = temp[m];
}

}

#### 5.桶排序

public static void bucketSort(int[] array){

int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;

for(int i = 0; i < array.length; i++){
max = Math.max(max, array[i]);
min = Math.min(min, array[i]);
}

//桶数
int bucketNum = (max - min) / array.length + 1;
ArrayList<ArrayList> bucketArr = new ArrayList(bucketNum);
for(int i = 0; i < bucketNum; i++){
}

//将每个元素放入桶
for(int i = 0; i < array.length; i++){
int num = (array[i] - min) / (array.length);
}

//对每个桶进行排序
for(int i = 0; i < bucketArr.size(); i++){
Collections.sort(bucketArr.get(i));
}

int k = 0;

for (int i = 0; i < bucketArr.size(); i++) {

for (Integer integer : bucketArr.get(i)) {
array[k++] = integer;
}

}

}

#### 6.计数排序

public static int[] countSort(int[] array) {
if (array == null || array.length == 0) {
return null;
}

int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;

//找出数组中的最大最小值
for (int i = 0; i < array.length; i++) {
max = Math.max(max, array[i]);
min = Math.min(min, array[i]);
}

int help[] = new int[max];

//找出每个数字出现的次数
for (int i = 0; i < array.length; i++) {
int mapPos = array[i] - min;
help[mapPos]++;
}

int index = 0;
for (int i = 0; i  0) {
array[index++] = i + min;
}
}

return array;
}

#### 7.希尔排序

public static void shellSort(int[] arr) {
//step:步长
for (int step = arr.length / 2; step > 0; step /= 2) {
//对一个步长区间进行比较 [step,arr.length)
for (int i = step; i = 0 && arr[j] > value; j -= step) {
//j为左区间的取值，j+step为右区间与左区间的对应值。
arr[j + step] = arr[j];
}
//此时step为一个负数，[j + step]为左区间上的初始交换值
arr[j + step] = value;
}
}
}