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)。