参考资料：
算法 第四版 (塞奇威克(Sedgewick, R.))
文中引用的所有网络内容均以 [x] 的形式标出，点击即可跳转到出处。
如有错误，欢迎大家在评论区指正！
一文搞定算法基础（一）—— 排序那些事
1. 排序
在继续阅读之前，首先我们要清楚排序的本质是什么？假设我们要从小到大排序，一个数组中取两个元素如果前面比后面大，则为一个逆序，容易看出排序的本质就是消除逆序数。[1]
如下为代码示例中会用到的两个公共类。
//所有排序算法的基类
package com.book1.chapter2.sort;
public abstract class Sort { public abstract void sort(int[] arr);
/**
* 交换
*/
public void exchange(int[] a, int i, int j) { SortUtils.exchange(a, i, j);
}
/**
* a是否小于b
*
* @param a
* @param b
* @return
*/
public boolean less(int a, int b) { return SortUtils.less(a,b);
}
}
//排序算法的工具类
package com.book1.chapter2.sort;
import java.time.Duration;
import java.time.LocalDateTime;
import java.util.Arrays;
public class SortUtils { /**
* 是否为有序数组
*
* @param arr
* @return
*/
public static boolean isOrderArr(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { if (arr[i] > arr[i + 1]) { return false;
}
}
return true;
}
/**
* 打印数组
*
* @param arr
*/
public static void printArr(int[] arr) { System.out.println(Arrays.toString(arr));
}
/**
* 交换两个元素
*
* @param a
* @param i
* @param j
*/
public static void exchange(int[] a, int i, int j) { int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
/**
* a是否小于b
*
* @param a
* @param b
* @return
*/
public static boolean less(int a, int b) { return a < b;
}
/**
* 分析时间
*
* @param arr
* @param sort
*/
public static void analyseTime(int[] arr, Sort sort) { LocalDateTime s = LocalDateTime.now();
sort.sort(arr);
LocalDateTime e = LocalDateTime.now();
System.out.printf("是否有序：%s，用时:%s\n", isOrderArr(arr), Duration.between(s, e).toMillis());
}
}
1.1 选择排序
思想
- 找到数组中最小的那个元素；
- 将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）；
- 在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置；
- 循环1~3 。
这种方法叫做选择排序，因为它在不断地选择剩余元素之中的最小者。
代码
package com.book1.chapter2.sort;
public class SelectSort extends Sort { /**
* 选择排序:
* 时间复杂度：O(n^2)
* 空间复杂度：O(1)
*
* @return
*/
@Override
public void sort(int[] arr) { int min;
//0.遍历数组的每一个索引i
for (int i = 0; i < arr.length; i++) { min = i;
//1. 找到数组中最小的那个元素；
for (int j = i + 1; j < arr.length; j++) { if (less(arr[j], arr[min])) { min = j;
}
}
//2. 将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）；
exchange(arr, i, min);
}
//循环步骤0~2，即在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复
}
}
缺点
-
一个已经有序的数组（或是主键全部相等的数组）和一个元素随机排列的数组所用的排序时间竟然一样长！
- 究其原因，是由于步骤1遍历了一遍数组，而未对下次扫描提供有效信息。（成本不低，有效产出太少！）
1.2 插入排序
思想
在已有的有序序列中，插入新元素。
- 判断新元素的插入位置；
- 为了给新元素腾出空间，需要将新元素之后的所有元素在都向右移动一位；
- 插入新元素；
- 循环1~3。
这种算法叫做插入排序。
代码
package com.book1.chapter2.sort; public class InsertSort extends Sort{ /** * 时间复杂度：O(n^2) * 空间复杂度：O(1) * 与选择排序的区别： * 选择排序是从待排序序列中挑选最小的元素放到当前索引位置。 * 插入排序是对当前索引位置（包含）之前的序列进行冒泡排序 * * @return */ @Override public void sort(int[] arr) { //遍历数组 // 为什么此处不是从0开始？见问答 for (int i = 1; i < arr.length; i++) { // 在已有的有序序列（arr[0] ~ arr[i]）中, //判断新元素的插入位置 //将新元素之后的元素逐个右移 for (int j = i; j > 0 && less(arr[j], arr[j - 1]); j--) { exchange(arr, j, j - 1); } } } }问答
-
为什么此处不是从0开始？
因为当数组只有1个元素时，数组本身即是有序的，所以插入排序应该从第 2 个元素开始（对应索引是 1）。
适用场景
- 数组中每个元素距离它的最终位置都不远；
- 一个有序的大数组接一个小数组；
- 数组中只有几个元素的位置不正确。
1.3 希尔排序
希尔排序和插入排序类似，但是希尔排序为什么比插入排序快？我们之前讲过排序的本质即是消除逆序数，插入排序每次交换只能消除 1 个逆序数，而希尔排序一次性可以消除多个逆序数。
思想
- 选择合适的间隔 h；
- 对间隔为 h 的两个元素进行比较，若后一个大于前一个，则交换；
- 缩小 h ，循环进行步骤 1 ~ 2。
使数组中任意间隔为 h 的元素都是有序的，则整个数组都会是有序的。
代码
package com.book1.chapter2.sort; public class ShellSort extends Sort { /** * 时间复杂度：O(NlogN) * 不稳定 * @return */ @Override public void sort(int[] arr) { int len = arr.length; //初始化间隔 int h = len / 3 + 1; //间隔需要大于等于1。（因为元素的间隔为0则代表元素位置重合） while (h >= 1) { //以间隔为h，进行插入排序 for (int i = h; i < len; i++) { for (int j = i; j >= h && less(arr[j], arr[j - h]); j = j - h) { exchange(arr, j, j - h); } } //缩小间隔后继续循环 h /= 3; } } }问答
-
为什么希尔排序的时间复杂度能突破 O ( n 2 ) O(n^2) O(n2)？
可以用逆序数来理解，假设我们要从小到大排序，一个数组中取两个元素如果前面比后面大，则为一个逆序，容易看出排序的本质就是消除逆序数，可以证明对于随机数组，逆序数是 O ( n 2 ) O(n^2) O(n2) 的，而如果采用“交换相邻元素”的办法来消除逆序，每次正好只消除一个，因此必须执行 O ( n 2 ) O(n^2) O(n2) 的交换次数，这就是为啥冒泡、插入等算法只能到平方级别的原因，反过来，基于交换元素的排序要想突破这个下界，必须执行一些比较，交换相隔比较远的元素，使得一次交换能消除一个以上的逆序，希尔、快排、堆排等等算法都是交换比较远的元素，只不过规则各不同罢了。原文链接
1.4 归并排序
思想
归并排序实质上就是把数组分成多个子数组，然后分别进行排序，待所有子数组都有序后，再将排序的结果归并到一个数组中。
- 将数组一分为2，采用分治的思想进行子数组排序
- 合并子数组。
代码
//v1 public class MergeSort extends Sort { public int[] aux; /** * 归并排序-归并数组的左右两边 * * @param arr 数组 * @param lo 最低位 （索引，从0开始算） * @param mid 中间位（索引） * @param hi 最高位（索引） */ public void merge(int[] arr, int lo, int mid, int hi) { //复制辅助数组 for (int k = lo; k <= hi; k++) { aux[k] = arr[k]; } int i = lo; int j = mid + 1; for (int k = lo; k <= hi; k++) { //若最低位 if (i > mid) { //左半边用尽（取右半边的元素）、 arr[k] = aux[j++]; } else if (j > hi) { // 右半边用尽（取左半边的元素）、 arr[k] = aux[i++]; } else if (less(aux[i], aux[j])) { // 右半边的当前元素大于等于左半边的当前元素（取左半边的元素）。 arr[k] = aux[i++]; } else { // 右半边的当前元素小于左半边的当前元素（取右半边的元素） arr[k] = aux[j++]; } } } /** * 排序 * * @param arr */ @Override public void sort(int[] arr) { aux = new int[arr.length]; sort(arr, 0, aux.length - 1); } /** * 排序 * * @param arr * @param lo * @param hi */ private void sort(int[] arr, int lo, int hi) { if (hi <= lo) { return; } int mid = lo + (hi - lo) / 2; sort(arr, lo, mid); sort(arr, mid + 1, hi); merge(arr, lo, mid, hi); } } //v2-20240117 package com.book1.chapter2.sort.demo; import com.book1.chapter2.sort.Sort; public class MergeSort2 extends Sort { private int[] aux; @Override public void sort(int[] arr) { //拆分数组 //将数组归并 aux = new int[arr.length]; sort(arr, 0, arr.length - 1); } private void sort(int[] arr, int lo, int hi) { if (lo >= hi) { return; } int m = lo + (hi - lo) / 2; sort(arr, lo, m); sort(arr, m + 1, hi); merge(arr, lo, m, hi); } /** * 合并两个数组 * * @param arr * @param lo * @param m * @param hi */ private void merge(int[] arr, int lo, int m, int hi) { //复制数组 for (int i = lo; i <= hi; i++) { aux[i] = arr[i]; } int i = lo; int j = m + 1; // for (int k = 0; k <= hi; k++) { //error：此处需要注意最终合并的数组是从lo开始的，lo不一定为0 for (int k = lo; k <= hi; k++) { if (i > m) { //左侧数组已遍历完了，直接从右侧数组赋值 // arr[k] = aux[j++];//error:漏掉指针j自增 arr[k] = aux[j++]; } else if (j > hi) { //右侧数组已遍历完了，直接从左侧数组赋值 // arr[k] = aux[i]; //error:漏掉指针i自增 arr[k] = aux[i++]; // } else if (less(arr[i], arr[j])) { //此处一定不能使用arr，因为循环中arr数组中的元素一直在变！ } else if (less(aux[i], aux[j])) { //取两个子数组中最小的，从小到大排序 arr[k] = aux[i++]; } else { arr[k] = aux[j++]; } } } }1.5 快速排序
思想
快速排序也是采用“双指针”的思想。
- 找到切分点j；
- 随机选择一个元素索引k（示例中采用的是数组中的第一个元素）；
- 将数组首部第二个元素的位置设定为指针i，数组尾部设定为指针j；
- i指针从左往右扫描，找到一个大于arr[k]的元素；
- j指针从右往左扫描，找到一个小于arr[k]的元素；
- 交换3、4所选的元素；
- 继续扫描直到 指针i与j相遇；
- 将k与j互换，保证k之前的都是小于arr[k]的元素，k之后的都是大于arr[k]的元素。
- 将元数组从j的位置切分为两个数组，分别进行1~7，以此类推
代码
//v1 public class QuickSort extends Sort { @Override public void sort(int[] arr) { sort(arr, 0, arr.length - 1); } public void sort(int[] arr, int lo, int hi) { if (lo >= hi) { return; } int mid = partition(arr, lo, hi); sort(arr, lo, mid - 1); sort(arr, mid + 1, hi); } private int partition(int[] arr, int lo, int hi) { int val = arr[lo]; int i = lo; int j = hi + 1; while (true) { //找到左边小于val的数 while (less(arr[++i], val)) { if (i == hi) { break; } } //找到右边大于val的数 while (less(val, arr[--j])) { if (j == lo) { break; } } //若左右指针交错开，则跳出循环 if (i >= j) { break; } //交换 exchange(arr, i, j); } //交换val与右指针j(此处一定不能交换左指针i，为什么？TODO) exchange(arr, lo, j); return j; } } //v2-20240117 public class QuickSort2 extends Sort { @Override public void sort(int[] arr) { sort(arr, 0, arr.length - 1); } private void sort(int[] arr, int lo, int hi) { if (lo >= hi) { return; } //1.任意选择一个索引k // int k = 0; // error:此处应该取子数组的最低点lo int k = lo; // int i = 0; // error:问题同上 int i = lo; // int j = arr.length; // error：此处应该取最高点值+1，因为后面会先执行--j，再进行比较 int j = hi + 1; while (true) { //2.将头指针i从左往右移动，找到arr[i]>arr[k]的位置 while (less(arr[++i], arr[k])) {// if (i >= lo) { success:为什么这里不能用==？由于此处是每次变化量为1，所以是可以的哦 if (i == hi) { break; } } //3.将尾指针j从右往左移动，找到arr[j] while (less(arr[k], arr[--j])) {// if (j <= lo) { success:为什么这里不能用==？由于此处是每次变化量为1，所以是可以的哦 if (j == lo) { break; } } //若i>=j则退出 // if (i >= j) { // 此处是否可以用==？ // 不可以，因为i(右移找到大于arr[k]的元素索引)与j(左移找到小于arr[k]的元素索引)交错开时，它俩的差不一定刚好为0 if (i >= j) { break; } //4.交换i与j位置的元素 exchange(arr, i, j); //5.继续移动 } //退出循环时，交换k与j位置的元素。此处为什么不能交换i与k的位置，而要交换j与k的位置？详见下面的问答1 exchange(arr, j, k); //切分的点即是j，分成两个数组“分治” sort(arr, lo, j - 1); sort(arr, j + 1, hi); } }问答
-
此处为什么不能交换i与k的位置，而要交换j与k的位置？
我们先来看示例：
假设我们对数组[6,1,7,3,9]进行快速排序。
- 初始化k = 0
- i：从左往右找到大于arr[k]的元素索引为2，即元素7的位置。
- j：从右往左找到小于arr[k]的元素索引为3，即元素3的位置。
- 交换i与j，则数组变为：6,1,3,7,9，
- 继续循环后i=3，j=2，不满足交换条件，退出循环。
- 若交换k与i，则数组变为：7，1，3，6，9，造成逻辑错误。
那为什么交换j就可以呢？
因为退出循环后，索引i的元素可能大于或等于arr[k]，而索引j的元素可能小于或等于arr[k]，为了保证k左边的元素均小于等于arr[k]，我们当然要选择与arr[j]交换位置，最差的结果也不过是j等于k时，元素与自身交换位置罢了。
网上有的文章说是跟步骤2和步骤3的顺序有关系，经验证，与顺序无丝毫关系！
（不理解的小伙伴可以在评论区踢我，有问必答。）
未完待续 ~ 欢迎点赞或评论区催更！
如果这篇文章对你有用的话，本人深感荣幸！
- 究其原因，是由于步骤1遍历了一遍数组，而未对下次扫描提供有效信息。（成本不低，有效产出太少！）