Sort
算法 | 是否原地 | 是否稳定 | 平均 | 最好 | 最坏 | 基于比较 |
冒泡 | 是 | 是 | O(n^2) | O(n) | O(n^2) | 是 |
插入 | 是 | 是 | O(n^2) | O(n) | O(n^2) | 是 |
选择 | 是 | 否 | O(n^2) | O(n^2) | O(n^2) | 是 |
归并 | 否: O(n) | 是 | O(nlogn) | O(nlogn) | O(nlogn) | 是 |
快速 | 是 | 否 | O(nlogn) | O(nlogn) | O(n^2) | 是 |
堆 | 是 | 否 | O(nlogn) | O(nlogn) | O(nlogn) | 是 |
计数 | 否 | 是 | | O(n+k), k数据范围 | | 否 |
桶 | 否 | 是 | | O(n) | | 否 |
基数 | 否 | 是 | | O(dn), d位数 | | 否 |
评价排序算法的维度：
- 1.时间复杂度：最好、最坏、平均，以及对应的原始数据类型。
- 2.时间复杂度的系数、常数、低阶，时间复杂度反应的是随数据规模 n 增大的增长趋势，一般是在 n 很大的情况下得出。但是在实际中，n 可能不是很大，所以在同一个阶时间复杂度下，需要考虑系数、常数、低阶。
- 3.比较次数与交换（移动）次数的分析。
- 4.内存消耗。原地排序（sorted in place）指空间复杂度为 O(1) 的排序算法。
- 5.稳定性，如果待排序的序列中存在值相等的元素，经过排序之后，相等的元素之间原有的先后顺序不变。实际中，我们是根据对象的某个 field 来排序，对象还有其它 field，所以需要分析稳定性。例子：订单有时间和金额，希望 order by amount, time ，那么先对时间排序，然后用稳定的排序算法对金额排序，得到的结果就是金额从小到大，相同金额从早到晚。
描述：冒泡排序仅会操作相邻的两个元素，比较两个相邻元素，若不满足大小关系，则交换。每次冒泡会让一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序。
优化：当某次冒泡没有数据交换时，则完成排序。
public void sort(Integer[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
boolean exchanged = false;
for (int j = 1; j < n - i; j++) {
if (nums[j - 1] > nums[j]) {
exchanged = true;
exchange(nums, j - 1, j);
}
}
if (!exchanged) {
break;
}
}
}
private void exchange(Integer[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
原地排序：只需要常量级的额外空间。
稳定排序：当相邻两个元素相等时，不交换就行。
最好时间复杂度：若数据本来有序，则只需要一次冒泡，所以最好为 O(n)。
最坏时间复杂度：若数据刚好为逆序，则要进行 n 次冒泡，所以最坏为 O(n^2)。
平均时间复杂度：
有序度是数组中具有有序关系的元素对的个数，有序元素对定义：
a[i] <= a[j], i < j。如2, 4, 3, 1, 5, 6有序度为4 + 2 + 2 + 2 + 1 = 11 。完全有序的数组的有序度叫满有序度(n * (n - 1) / 2)。逆序度 = 满有序度 - 有序度。冒泡有两个比较和交换两个操作，每次交换，有序度加1，所以
交换次数 = 逆序度。平均交换次数n * (n - 1) / 4，比较次数 > 交换次数，时间复杂度上限 O(n^2)，所以平均时间复杂度 O(n^2)。注意此种平均时间复杂度分析并不严格。
描述：将数组分为两个区域，已排序和未排序，初始已排序为第一个元素。每次取未排序的第一个元素，在已排序中找到合适位置插入。
public void sort(Integer[] nums) {
int n = nums.length;
for (int i = 1; i < n; i++) {
int tmp = nums[i];
int j;
for (j = i - 1; j >= 0; j--) {
if (tmp < nums[j]) {
nums[j + 1] = nums[j];
} else {
break;
}
}
nums[j + 1] = tmp;
}
}
特点：包含比较和移动两种操作。移动次数等于逆序度。
原地排序：不需要额外存储空间。
稳定排序：当两个元素相等时，将后面插入的元素放到前面出现的元素后面，就可以保证顺序不变。
最好时间复杂度：如数据本来有序，则不需要搬动任何数据，查找插入位置时从尾到头，则每次只需要比较一次，所以最好为 O(n)。
最坏时间复杂度：如果数据是倒序的，每次都要移动有序区域的所有数据，所以最坏为 O(n^2)。
平均时间复杂度：在有序数组中插入一个数据的平均时间复杂度为 O(n)，所以插入排序的平均时间复杂度为 O(n^2)。
为什么插入排序比冒泡排序更好？冒泡和插入的交换或移动次数是固定的，等于逆序度。但是冒泡一次交换需要三个操作，差插入一次移动仅需一个操作。
插入排序优化：希尔排序，开始用大的步长，最后一次就是普通的插入，但是基本已经排好序。用大的步长是每次可以移动较大的位置。
描述：将数组分为两个区域，已排序和未排序，初始已排序为空，每次找到未排序的最小元素，放入已排序的末尾，即与未排序的第一个元素交换。
public void sort(Integer[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
int min = nums[i];
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (nums[j] < min) {
min = nums[j];
minIndex = j;
}
}
int tmp = nums[i];
nums[i] = min;
nums[minIndex] = tmp;
}
}
原地排序：不需要额外存储空间。
最好、最坏、平均时间复杂度：都是 O(n^2)。
不稳定排序：每次都从未排序区域中找到最小，与未排序区域的第一个元素交换，破坏了稳定性。
冒泡排序与选择排序仅用作理论，实际中基本不用，而插入排序有时会用到。
若是链表实现，冒泡排序的交换操作更加复杂；插入排序不需要移动，直接插入；选择排序的交换同样比较复杂。
描述：采用分治的思想。先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并。
public void sort(Integer[] nums) {
mergeSort(nums, 0, nums.length - 1);
}
private void mergeSort(Integer[] nums, int p, int r) {
if (p >= r) {
return;
}
int q = (p + r) / 2;
mergeSort(nums, p, q);
mergeSort(nums, q + 1, r);
merge(nums, p, r);
}
private void merge(Integer[] nums, int p, int r) {
int q = (p + r) / 2;
int[] tmp = new int[r - p + 1];
int i = p, j = q + 1, cur = 0;
while (i <= q && j <= r) {
if (nums[i] <= nums[j]) {
tmp[cur++] = nums[i++];
} else {
tmp[cur++] = nums[j++];
}
}
for (; i <= q; i++) {
tmp[cur++] = nums[i];
}
for (; j <= r; j++) {
tmp[cur++] = nums[j];
}
cur = 0;
for (int k = p; k <= r; k++) {
nums[k] = tmp[cur++];
}
}
递推公式：
merge_sort(p, r) = merge(merge_sort(p, q), merge_sort(q + 1, r))终止条件：
p >= r；其中，q = (p + r) / 2。稳定排序：关键看 merge 操作，在 merge 过程中，把 A[p, q] 中的元素先放入临时数组，那么值相同的元素保证了顺序不变，所以归并排序是稳定的。
最好、最坏、平均时间复杂度：都是 O(nlogn)，分析过程如下：
// 假设对 n 个元素进行归并排序 时间为 T(n)，那么两个子数组进行归并排序的时间都是 T(n/2)，
// merge 操作的时间复杂度是 O(n)，所以递推公式如下
T(1)=C
T(n)=2*T(n/2)+K
其中 K 为将两个子问题合并所需时间，
K = O(n)。所以归并时间复杂度为 O(nlogn)，与原始数据有序程度无关。非原地排序： 合并操作需要一个临时数组，最大为 n，所以归并排序的空间复杂度为 O(n)。
描述：快排也是分治思想，将 A[p, r] 排序，选择 p 到 r 之间任意一个数据作为 pivot（分区点），将小于pivot 的放到左边，大于 pivot 的放到右边，pivot 放到中间。
public void sort(Integer[] nums) {
_sort(nums, 0, nums.length - 1);
}
private void _sort(Integer[] nums, int p, int q) {
if (p >= q) {
return;
}
int r = partition(nums, p, q);
_sort(nums, p, r - 1);
_sort(nums, r + 1, q);
}
// 快排的分区函数类似选择排序：将数组分为两个区域，初始已处理为空，
// 每次从未处理选一个与 pivot 比较，若小于pivot，则放入已处理末尾，即与未处理的第一个元素交换。
private int partition(Integer[] nums, int p, int q) {
int i = p;
int pivot = nums[q];
for (int j = p; j < q; j++) {
if (nums[j] < pivot) {
int tmp = nums[j];
nums[j] = nums[i];
nums[i++] = tmp;
}
}
nums[q] = nums[i];
nums[i] = pivot;
return i;
}
递推公式：
quick_sort(p, r) = quick_sort(p, q - 1) + quick_sort(q + 1, r)终止条件：
p >= r不稳定排序：快速排序涉及交换，所以不稳定。
原地排序：分区函数不需要额外空间。
时间复杂度 分析：大部分情况是 O(nlogn)，O(n^2) 的概率非常小，可以合理选择 pivot 来降低概率。最坏情况即数组已经有序，选择最后一个元素作为 pivot，则时间复杂度为 O(n^2)。.
T(1) = C
T(n) = 2 * T(n / 2) + n
归并排序与快速排序的区别：归并是由下到上，先处理子问题，再合并；快速是由上到下，先分区，再处理子问题。
思路：将数组 A[0:n-1] 最后一个元素 A[n-1] 作为 pivot，原地分区，分成了 A[0: p - 1], A[p], A[p + 1: n - 1]，若 p + 1 = K，则 A[p] 就是要求解的，否则按上述思路继续查找。
时间复杂度：n + n / 2 + n / 4 + n / 8 + ... + 1 = 2n - 1，为 O(n)。
线性排序时间复杂度是线性 O(n) 的：桶排序、计数排序、基数排序。能做到线性，原 因都是非基于比较，不涉及元素之间比较操作。
线性排序对数据的要求很严苛，都有各自的适用场景。
描述：将排序的数据分到几个有序的桶中，每个桶内单独排序，再按照桶的顺序依次取出。
时间复杂度：O(n)。n 个数据，m 个桶，每个桶的数据个数为 k = n / m，
O(m*k*logk) = O(n*log(n/m))，当 m 接近 n 时，log(n/m) 很小。对数据要求：1. 数据很容易划分成 m 个桶；2. 桶与桶有天然有序；3. 能够比较均匀分布在各个桶中。
适用场景：适合外部排序，数据量大，无法全部加载到内存中。
案例：10GB 的订单数据，只有几百 MB 内存，希望按照订单金额排序。1. 扫描一遍文件，得到订单金额所处范围；2. 根据范围分为 100 个桶，每个桶对应一个文件；3. 再扫描一遍，把数据分到 100 个文件中，若分布均匀，每个文件大约 100MB；4. 100 个文件分别放在内存中排序；5. 然后将 100 个文件依次写入到一个文件中；6. 若分布不均匀，则可以对数据比较多的小文件再次分割。
描述：需要排序的 n 个数据，仅有 k 个可能值，则可以把数据划分到 k 个桶中，每个桶内的数据值一样，桶内不需要排序。
有人认为，计数排序是特殊的桶排序。我认为不是。因为桶排序中，每个桶存放的是所有数据，每个桶单独排序；而计数排序中，每个桶中存放的是数据的个数，算法思路不一样。
流程：假设数据 A[n] 有 k 个可能值。1. 先准备一个大小为 k 的数组 C，C 的下标为数据值，C 的值为数据值的个数；2. 扫描一遍数据，得到 C；3. 对 C 顺序求和，此时 C[i] 中存放的是小于等于 i 的个数；4. 准备数组 R[n]，从后往前扫描 A[n]，若值为 i，则
R[C[i]]=i, C[i]=C[i]-1。
适用场景：数据值范围不大；只能给非负整数排序，若是其它类型，在不改变相对大小的情况下，转化为非负整数。
案例：考生满分 900 分，对高考成绩排序，则可以划分成 901 个桶。
描述：比如，对手机号排序，从低位开始，每一位分别用线性排序。要求稳定的排序。
若数据不是等长，可以补齐。
适用场景：数据可以分割出位，位有递进关系，高位比较大，则低位就不用比较了，每一位的数据范围不大，对每位就可以用线性排序了。
如何实现一个通用的、高性能的排序函数：
- 通用，所以不能选择对数据要求比较严格的线性排序。
- 小规模数据可选择 O(n^2)，大规模一般选择 O(nlogn)。
- O(nlogn) 比较多，Java 采用堆排序，C 采用快速排序。
- 归并用的少，原因是非原地。
- 解决快排在最坏情况 O(n^2) 的方式：a、首、尾、中三个数取中间值；b、随机；
- 快排递归，防止栈溢出，可以限制深度，也可以手动实现栈。
Glibc 的 qsort：
- 优先使用归并，在数据量小时。
- 数据量大，变成快排。
- 快排采用三数取中法。
- 自己在堆上实现栈。
- 当排序取件小于等于 4 时，退化为插入排序。
O(n^2) 算法不一定比 O(nlogn) 执行时间长：
- 时间复杂度反映的是增长趋势
- 但是会省略低阶、常数、系数，所以数据量小时，O(n^2) 可能会更快。
Last modified 3yr ago