talk is simple, show me your code！！先上代码,之后补全注释(个人学习向，有问题欢迎交流)
总结一下 冒泡排序，插入排序，选择排序的各自的特点，方便记忆一些。
相同:
三者都是两重for循环，外层的循环差不多，都是从头到尾遍历数组
区别：
冒泡排序，第一层循环到length-1,第二层循环到length-1-i
插入排序，第一层循环i从1开始，第二层循环是从i到0
选择排序，第一层循环里需要记录i的值，第二层循环从i到length
关于排序函数的传参，除了快速排序，归并排序，其他基本都只传数组本身就行。
快速排序，除了数组，还要传首尾的index
归并排序，除了首尾的index，还要再传入额外的数组来保存数据
常见的比较类排序中，只有 冒泡排序，插入排序，归并排序是稳定的。
| 排序方法 | 时间复杂度 平均 | 时间复杂度 最坏 | 时间复杂度 最好 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
| 插入排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 快速排序 | O(nlogN) | O(n²) | O(nlogN) | O(logN) | 不稳定 |
| 堆排序 | O(nlogN) | O(nlogN) | O(nlogN) | O(1) | 不稳定 |
| 归并排序 | O(nlogN) | O(nlogN) | O(nlogN) | O(N) | 稳定 |
| 希尔排序 | O(n1.3) | O(n²) | O(n) | O(1) | 不稳定 |
private static void quickSort(int[] array, int l, int r) {
if (array == null) {
return;
} else if (array.length == 0) {
return;
} else {
// 递归终止条件，必须加
if (l < r) {
int i = quickSortArray(array, l, r);
quickSort(array, l, i - 1);
quickSort(array, i + 1, r);
}
}
}
private static int quickSortArray(int[] array, int l, int r) {
if (array == null || l < 0 || r < 0 || l > r) {
return 0;
} else {
int x = l;
int y = r;
int temp = array[l];
while (x < y) {
while (x < y && array[y] >= temp) {
y--;
}
if (x < y) {
array[x] = array[y];
}
while (x < y && array[x] < temp) {
x++;
}
if (x < y) {
array[y] = array[x];
}
}
array[x] = temp;
return x;
}
}
可以试着排序数组 [4，3，4] ，如果 array[y] >= temp 和 array[x] < temp 中, 同时不加 = ，会陷入死循环。
但是同时都加上，是没问题的。
必须加上，这是递归的终止条件
// 未优化版
public void bubbleSort(int[] array) {
if (array == null || array.length < 2)
return;
for (int i = 0; i < array.length - 1; i++) {
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j+1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
// 稍稍优化了一下，如果内部循环一圈没有发生交换，可以提前退出
private static void bubbleSort(int[] array) {
if (array == null) {
return;
} else if (array.length == 1) {
return;
} else {
boolean flag = true;
int i = 1;
while (flag) {
flag = false;
for (int j = 0; j < array.length - i; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
flag = true;
}
}
i++;
}
}
}
/**
* 第i次排的时候认为前i-1项已经排序完成，把新的这个数插入到前i-1项中的正确位置即可
*
* @param array
*/
private static void insertSort(int[] array) {
if (array == null) {
return;
} else if (array.length == 1) {
return;
} else {
int i, j;
for (i = 1; i < array.length; i++) {
for (j = i - 1; j >= 0 && array[j] > array[j + 1]; j--) {
// swap(array[j], array[j + 1]);
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
/**
* 每次选最小的放到最前面
*
* @param array
*/
private static void selectSort(int[] array) {
if (array == null) {
return;
} else if (array.length == 1) {
return;
} else {
int i, j;
int index = 0;
for (i = 0; i < array.length; i++) {
index = i;
for (j = i; j < array.length; j++) {
if (array[j] < array[index]) {
index = j;
}
}
int temp = array[i];
array[i] = array[index];
array[index] = temp;
}
}
}
public static void heapSort(int[] array) {
/**
* 构建大顶堆
*/
for (int i = array.length / 2 - 1; i >= 0; i--) {
adjustHeap(array, i, array.length);
}
/**
* 调整堆，第一项与最后一项互换，然后对前length-2项重新构建大顶堆
*/
for (int i = array.length - 1; i > 0; i--) {
// swap(array[0], array[i]);
int temp = array[0];
array[0] = array[i];
array[i] = temp;
adjustHeap(array, 0, i);
}
}
/**
* 调整大顶堆,头尾元素互换，然后重新构建大顶堆
* @param array
* @param i
* @param length
*/
private static void adjustHeap(int[] array, int i, int length) {
int temp = array[i];
for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
if (k + 1 < length && array[k + 1] > array[k]) {
k++;
}
if (array[k] > temp) {
array[i] = array[k];
i = k;
} else {
break;
}
}
array[i] = temp;
}
/**
* 归并排序
* @param array
* @param first
* @param last
* @param temp
*/
private static void mergeSort(int array[], int first, int last, int temp[]) {
if (array == null) {
return;
}
if (first < last) {
int mid = (first + last) / 2;
mergeSort(array, first, mid, temp);
mergeSort(array, mid + 1, last, temp);
mergeArray(array, first, mid, last, temp);
}
}
/**
* 将两个排好序的序列合并
* @param array
* @param first
* @param mid
* @param last
* @param temp
*/
private static void mergeArray(int[] array, int first, int mid, int last, int[] temp) {
int l = first;
int r = mid;
int x = mid + 1;
int y = last;
int k = 0;
while (l <= r && x <= y) {
if (array[l] <= array[x]) {
temp[k++] = array[l++];
} else {
temp[k++] = array[x++];
}
}
while (l <= r) {
temp[k++] = array[l++];
}
while (x <= y) {
temp[k++] = array[x++];
}
for (int i = 0; i < k; i++) {
array[first + i] = temp[i];
}
}
/**
* 希尔排序，对直接插入排序的改进，又叫缩小增量排序
*
* @param array
* @param length
*/
public void shellSort(int []array) {
if (array == null || array.length < 1) {
return;
}
/**
* 调整步长，假如数组长度为10，那么步长的变化就是5-2-1
*/
for (int step = array.length / 2; step > 0; step = step / 2) {
for (int i = step; i < array.length; i++) {
for (int j = i - step; j >= 0 && array[j + step] < array[j]; j-= step) {
int temp = array[j];
array[j] = array[j + step];
array[j + step] = temp;
}
}
}
}
private static void swap(int i, int j) {
if (i == j) {
return;
}
i ^= j;
j ^= i;
i ^= j;
}