Back

To Top

排序概述

Sep 10, 2023

#排序 #数据结构与算法

执行效率：

最好、最坏、平均时间复杂度
时间复杂度的系数、常数、低阶
比较次数、交换（或移动）次数

空间复杂度：原地排序（Sorted in place）。原地排序算法，就是特指空间复杂度是 O(1) 的排序算法。

有序度：

有序度：有序元素对 a[i] <= a[j]，如果 i < j 的数量
满序度
- 完全有序的数组
- 对于长度为 n 的数组 满序度 = n * (n - 1) / 2
- 举例：长度 6 的数组，满序度 = 6 * (6 - 1) / 2 = 15
逆序度：逆序度 = 满序度 - 有序度

稳定性

稳定性：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

稳定：如果 a 原本在 b 前面，而 a = b，排序之后 a 仍然在 b 的前面
不稳定：如果 a 原本在 b 的前面，而 a = b，排序之后 a 可能会出现在 b 的后面

排序方法

内排序：所有排序操作都在内存中完成，占用常数内存，不占用额外内存
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行，占用额外内存

复杂度

时间复杂度：一个算法执行所耗费的时间
空间复杂度：运行完一个程序所需内存的大小

常见排序算法汇总

名词解释：

n：数据规模
k：桶的个数

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	原地排序	稳定性
冒泡排序	`O(n^2)`	`O(n)`	`O(n^2)`	`O(1)`	✔	✔
选择排序	`O(n^2)`	`O(n^2)`	`O(n^2)`	`O(1)`	✔	✘
插入排序	`O(n^2)`	`O(n)`	`O(n^2)`	`O(1)`	✔	✔
希尔排序	`O(n log n)`	`O(n(log2/2n))`	`O(n(log2/2n))`	`O(1)`	✔	✘
归并排序	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(n)`	✘	✔
快速排序	`O(n log n)`	`O(n log n)`	`O(n^2)`	`O(log n)`	✔	✘
堆排序	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(n)`	✘	✘
计数排序	`O(n + k)`	`O(n + k)`	`O(n + k)`	`O(k)`	✘	✔
桶排序	`O(n + k)`	`O(n + k)`	`O(n + k)`	`O(n + k)`	✘	✔
基数排序	`O(n * k)`	`O(n * k)`	`O(n * k)`	`O(n + k)`	✘	✔

从分类上来讲：

比较类
- 交换排序
  - 冒泡排序 Bubble Sort
  - 双向冒泡排序
  - 快速排序 Quick Sort
- 插入排序
  - 直接插入排序 Insertion Sort
  - 二分插入排序 Binary Insertion Sort
  - 希尔排序 Shell Sort
- 选择排序
  - 简单选择 Selection Sort
  - 堆 Heap Sort
- 归并排序
  - 二路归并 Two-way Merge
  - 多路归并 Muti-way Merge
非比较类（分布排序）
- 计数排序 Counting Sort（*）
- 桶排序 Bucket Sort（*）
- 基数排序 Radix Sort（*）

带（*）的排序算法需要额外的空间。

nlogn 比 n^2 快多少？

	n^2	nlogn	faster
n = 10	100	33	3
n = 100	10000	664	15
n = 1000	10^6	9966	100
n = 10000	10^8	132877	753
n = 100000	10^10	1660964	6020

参考资料

📝 JavaScript 排序算法汇总