排序算法的基础&进阶
| 类型 | 平均情况下，时间复杂度 | 最好情况下，时间复杂度 | 最坏情况下，时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n)有序情况 | O(n²)无序情况 | O(1) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n²)有序情况 | O(logn) | 不稳定 |
| 插入排序 | O(n²) | O(n)有序情况 | O(n²)无序情况 | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 希尔排序 | O(nlog²n) | O(nlog²n) | O(nlog²n) | O(1) | 不稳定 |
关键词含义
n：数据规模
时间复杂度
算法运行过程中所耗费的时间。
空间复杂度
算法运行过程中临时占用存储空间的大小。例如：O(1)表示所需空间大小为常量，与数据量n无关。
稳定性含义
- 稳定：在排序之前，如果两个数相等，那么排序之后，这两个数的先后顺序不变。如排序前，a=b，a在b的前面；那么排序后，a依旧在b的前面。
- 不稳定：在排序之前，如果两个数相等，那么排序之后，这两个数的先后顺序改变。如排序前，a=b，a在b的前面；那么排序后，a在b的后面。
冒泡排序
原理步骤
- 比较相邻的两个数，如果前面的数大于后面的数，就交换这两个数。
- 相邻的最前一对数和最后一对数都要进行比较，这样最后一个数就是最大的数。
- 每个元素重复以上步骤，除了最后一个数。
- 重复1-3的步骤。
代码实现
private static int[] bubbleSort(int array[]) {
if (array.length == 0) {
return array;
}
// 第1个for循环相当于步骤4
for (int i = 0; i < array.length; i++) {
// 第2个for循环相当于步骤3
// array.length -1 是因为后面有j+1，先-1是为了避免数组越界
// array.length -1 - i，之所以减i（已经排过1遍，就减1；如果已经排过i遍，就减i），是为了不比较排在最后且已经排好序的数，相当于步骤3的最后一句话
for (int j = 0; j < array.length - 1 - i; j++) {
int temp;
// if判断语句相当于步骤1和步骤2
if (array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
return array;
}
快速排序
原理步骤
- 取数组中的一个数作为key。
- 从后往前获取数组的数，并将其与key进行对比。
- 如果其中一个数小于key，那么就将这个数和key交换位置。
- 交换位置之后，从前往后获取数组的数，并将其与key对比。
- 如果其中一个数大于key，那么就将这个数和key交换位置。
- 重复2-5的过程，直到key前面的数都比key小，key后面的数都比key大，这样就完成一次排序。
- 以key为中心，对key前面的数组和后面的数组执行1-6的过程，直到数组完全有序。
代码实现
private static void quickSort(int[] array, int left, int right) {
if (left >= right) {
return;
}
int i, j, x;
i = left;
j = right;
x = array[i];
while (i < j) {
while (i < j && array[j] > x) {
j--;
}
if (i < j) {
array[i] = array[j];
i++;
}
while (i < j && array[i] < x) {
i++;
}
if (i < j) {
array[j] = array[i];
j--;
}
}
// j=i
array[j] = x;
quickSort(array, j + 1, right);
quickSort(array, left, j - 1);
}
插入排序
原理
- 每一步将一个待排序的数插入到已经排好序的序列中，直到插完所有数据。
代码实现
private static int[] insertSort(int array[]) {
if (array.length == 0) {
return array;
}
int i, j, temp;
// 注释①
for (i = 1; i < array.length; i++) {
// 注释②
temp = array[i];
// 注释③
for (j = i - 1; j >= 0 && array[j] > temp; j--) {
// 注释④
array[j+1] = array[j];
}
// 注释⑤
array[j+1] = temp;
}
return array;
}
注释①
- 默认数组第一个数（i=0的数）是有序的。
注释②
- array[i]为待排序的数据。
注释③
- array[i]前面的数与array[i]进行排序。
注释④
- arr[j]相当于前数，arr[j+1]相当于后数。
- 如果前数比后数大，交换位置，前数放到后数的位置。
注释⑤
- 如果for循环内前数和后数交换了位置（即前数挪到了后数的位置），那么注释⑤处的代码，就是将后数挪到前数的位置，实现交换。
- 如果缺少注释⑤处的代码，那么前数的位置就会“空缺”，或者说依旧是原来的数，并没有实现交换。
- 如果for循环内两数并没有交换（即跳出了for循环），此时j=i-1,j+1=i,与tmp=a[i]效果是一样的。
选择排序
原理步骤：
- 从未排序的序列中取出最小（最大）的数，放入已排序序列的初始位置；
- 继续从未排序序列剩余的数中取最小（最大）的数，放在已排序序列的末尾。
- 持续执行②的步骤，直到整个序列有序。
代码实现
private static int[] selectionSort(int[] array) {
if (array.length == 0) {
return array;
}
for (int i = 0; i < array.length; i++) {
int min = i;
for (int j = i; j < array.length; j++) {
// 从未排序序列中获取最小值
if (array[j] < array[min]) {
min = j;
}
}
// 把获取的最小值放入已排序序列的末尾（此时i代表末尾的索引）
int temp = array[i];
array[i] = array[min];
array[min] = temp;
}
return array;
}
总结1：
- 插入排序和选择排序可以划为一类排序算法来理解和掌握。
- 它们都具有相同点——将数组划分为已排序、未排序两个部分，然后将未排序的部分逐个迁移到已排序的部分，最终使整个数组实现完全有序。
- 而不同点在于从未排序合入到已排序的方式。插入排序会将未排序的数据在已排序的数组中执行直接插入排序；而选择排序会先在未排序的数组中选出最小值，当这个值合入到已排序的数组中时，不需要再进行比较，直接放到已排序数组的末尾就可以了。
希尔排序
原理步骤
- 把一个数组按增量进行分组。（增量指分组数量）
- 每个分组采用直接插入排序进行排序。
- 然后减小增量，每个分组的元素数目增加，直到增量为1，整个文件变为一组，算法结束。
代码实现
private static int[] shellSort(int[] array) {
if (array.length == 0) {
return array;
}
// gap为分组数目
for (int gap = array.length / 2; gap > 0; gap = gap / 2) {
// i为索引,对每组进行排序
for (int i = gap; i < array.length; i++) {
// j为临时变量
int j = i;
// 分组内元素的个数可能大于2个，因此使用while循环
while (j - gap >= 0 && array[j] < array[j - gap]) {
// 在同一个分组中，如果后面的数（j）比前面的（j-gap）大，就交换它们的位置
int temp = array[j];
array[j] = array[j - gap];
array[j - gap] = temp;
j = j - gap;
}
}
}
return array;
}
归并排序
原理步骤
- 将一个数组分为左子数组和右子数组，两个子数组的长度为n/2（n为数组的总长度）。
- 在两个子数组间进行归并排序（即每个子数组划分为更小的左子数组和右子数组，直到无法再分时，对两个数组进行排序，详情见代码）。
- 将两个有序的子数组合并为一个最终的有序数组。
代码实现
private static int[] mergeSort(int[] array) {
// 数组只有一个元素或没有元素，直接返回。
// 脱离递归的条件
if (array.length < 2) {
return array;
}
// 将数组分为两半，分别进行排序
int[] left = Arrays.copyOfRange(array, 0, array.length / 2);
int[] right = Arrays.copyOfRange(array, array.length / 2, array.length);
return merge(mergeSort(left),mergeSort(right));
}
/**
* 将左数组与右数组合并为一个有序数组
* 注意：此时左数组、右数组已经有序
* @param left
* @param right
* @return
*/
private static int[] merge(int[] left, int[] right) {
// 合并后的有序数组
int[] result = new int[left.length + right.length];
for (int index = 0, i = 0, j = 0; index < result.length; index++) {
if (i >= left.length) {
// 如果左数组已经遍历结束，就插入右数组的值
result[index] = right[j];
j++;
} else if (j >= right.length) {
// 如果右数组已经遍历结束，就插入左数组的值
result[index] = left[i];
i++;
} else if (left[i] > right[j]) {
// 左数组与右数组的值同时存在时，就对两数进行比较
// 如果右数组的值比较小，就插入右数组的值。
result[index] = right[j];
j++;
} else {
// 左数组与右数组的值同时存在时，就对两数进行比较
// 如果左数组的值比较小，就插入左数组的值。
result[index] = left[i];
i++;
}
}
return result;
}
总结2：
- 希尔排序和归并排序可以划为一类排序算法来理解和掌握。
- 它们都具有相同点——先将整个大的数组分为不同的小组，然后对小组的数据进行排序，最终将所有小组合并为一个有序数组。
- 而不同点在于分组后的排序方式不同。希尔排序会针对一个小组内的数据执行直接插入排序，而归并排序会直接将两个小组合并为一个有序数组。
排序算法进阶
- 以上冒泡、快排、插入、选择、希尔、归并这六种排序算法都是基础的排序算法，很多中等、困难难度的算法题一般都是基于上述算法进行解决。（比如《合并两个有序数组》其实就是归并算法的某一部分）
- 推荐《最小K个数》、《数组中的第K个最大元素》作为进阶学习。（它们都是基于快排实现，类似的变形有最大K个数等）
作者：度熊君
链接：https://juejin.cn/post/7067027053119275022
来源：稀土掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
