比较插入、交换、选择、归并、快速、堆、桶和基数排序的过程、复杂度与稳定性,掌握各算法每趟排序后的特征。

# 一、排序的基本概念

排序是按关键字次序重新排列记录。若排序前关键字相同的记录在排序后仍保持原有相对次序,则称排序算法稳定;否则不稳定。稳定性是算法属性,应结合具体实现判断。

内部排序的全部待排序记录都能放入内存。比较排序只依据关键字间比较,任意输入的比较排序最坏情况需要 Ω(nlog⁡n)\Omega(n\log n) 次比较;计数、桶、基数等分布排序利用关键字范围或位结构,在满足额外条件时可达到线性时间。

# 二、插入排序

# 1. 直接插入排序

维护一个有序前缀,每趟取下一个记录,从右向左查找插入位置并后移较大元素。若相等元素不被越过,算法稳定。

1
2
3
4
5
6
7
8
9
10
11
void InsertionSort(int data[], int n) {
for (int i = 1; i < n; i++) {
int key = data[i];
int j = i - 1;
while (j >= 0 && data[j] > key) {
data[j + 1] = data[j];
j--;
}
data[j + 1] = key;
}
}

最好情况(原序列有序)为 O(n)O(n);平均和最坏情况为 O(n2)O(n^2);辅助空间为 O(1)O(1)。适合规模较小或大部分有序的数据。

# 2. 折半插入排序

折半插入排序用二分查找在有序前缀中确定插入位置,关键字比较次数降为 O(nlog⁡n)O(n\log n);但仍需移动后缀元素,最坏移动次数为 O(n2)O(n^2),总时间仍为 O(n2)O(n^2)。将新元素插到相等元素之后可保持稳定。

# 三、交换排序

# 1. 冒泡排序

每趟比较相邻元素并交换逆序对,升序排序时最大元素逐趟移动到未排序区末尾。若一趟没有发生交换,可提前结束。采用严格大于时相等元素不交换,算法稳定;加提前结束标志后最好时间为 O(n)O(n),平均和最坏为 O(n2)O(n^2),空间为 O(1)O(1)。

# 2. 快速排序

快速排序先选择基准并进行分区,使较小元素在左、较大元素在右,再递归排序两个子区间。分区完成后基准位于最终位置,但左右子区间内部可能仍未排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
static void Swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

void QuickSort(int data[], int low, int high) {
if (low >= high) {
return;
}

int i = low;
int j = high;
int pivot = data[low + (high - low) / 2];

while (i <= j) {
while (data[i] < pivot) {
i++;
}
while (data[j] > pivot) {
j--;
}
if (i <= j) {
Swap(&data[i], &data[j]);
i++;
j--;
}
}

if (low < j) {
QuickSort(data, low, j);
}
if (i < high) {
QuickSort(data, i, high);
}
}

平均时间为 O(nlog⁡n)O(n\log n),最坏为 O(n2)O(n^2);原地分区不计递归栈时只需 O(1)O(1) 额外空间,递归栈平均为 O(log⁡n)O(\log n)、最坏为 O(n)O(n)。交换可能改变相等记录的相对次序,通常不稳定。

# 四、选择排序

简单选择排序每趟从未排序区选出最小关键字,与未排序区首元素交换。每趟选出的元素已经处于最终位置;比较次数始终为 Θ(n2)\Theta(n^2),交换次数最多 n−1n-1 次。跨越交换可能改变相等记录的次序,因此通常不稳定;空间为 O(1)O(1)。

# 五、希尔排序

希尔排序按增量 gap 将元素分成若干间隔子序列,对各子序列分别做插入排序,再逐步缩小 gap,最终令 gap 为 11。早期的大增量先移动距离较远的元素,使最后一趟普通插入排序处理近乎有序的序列。

希尔排序不稳定。其时间复杂度依赖增量序列;采用简单折半增量时最坏为 O(n2)O(n^2),不能在未给出增量序列时笼统声称固定的最优复杂度。

# 六、归并排序

归并排序将序列递归分成两半,分别排序,再线性合并两个有序序列。合并时若两边关键字相等,先取左边记录可保持稳定。

时间复杂度为 O(nlog⁡n)O(n\log n),通常需要 O(n)O(n) 辅助数组。自底向上的非递归版本按子序列长度 1,2,4,…1,2,4,\ldots 逐趟归并。

# 七、堆排序

大根堆是完全二叉树,任一父结点关键字不小于孩子。用数组从 00 开始存储时,结点 ii 的左孩子下标为 2i+12i+1,右孩子为 2i+22i+2。堆排序流程:

  1. 从最后一个非叶子结点开始,自底向上调整为大根堆。
  2. 交换堆顶和当前末尾元素,最大关键字进入最终位置。
  3. 缩小堆的有效范围,对根重新向下调整。
  4. 重复直到剩一个元素。

建堆时间为 O(n)O(n),其后每次删除堆顶调整为 O(log⁡n)O(\log n),总时间为 O(nlog⁡n)O(n\log n);原地空间为 O(1)O(1),通常不稳定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void SiftDown(int data[], int root, int end) {
int child = 2 * root + 1;
while (child < end) {
if (child + 1 < end && data[child] < data[child + 1]) {
child++;
}
if (data[root] >= data[child]) {
return;
}
Swap(&data[root], &data[child]);
root = child;
child = 2 * root + 1;
}
}

void HeapSort(int data[], int n) {
for (int i = n / 2 - 1; i >= 0; i--) {
SiftDown(data, i, n);
}
for (int end = n - 1; end > 0; end--) {
Swap(&data[0], &data[end]);
SiftDown(data, 0, end);
}
}

# 八、分布排序

# 1. 桶排序

桶排序按关键字范围把记录分配到多个桶中,对各桶分别排序,再按桶序连接结果。它适合值域已知且记录分布较均匀的场景;若数据集中在少数桶,桶内排序仍可能成为瓶颈。时间可达期望 O(n+k)O(n+k),但取决于分布、桶数 kk 和桶内排序方法;空间通常为 O(n+k)O(n+k)。稳定性也取决于桶内排序与分配方式。

# 2. 基数排序

基数排序按关键字的每一位或每一组字符进行多趟稳定排序。低位优先(LSD)从最低有效位向高位处理,每一趟都必须稳定,才能保留前面较低位的次序;高位优先(MSD)从最高位递归分组,适合字符串或变长键。

若有 nn 个记录、dd 位关键字、每位基数为 kk,LSD 配合计数分配的时间和辅助空间通常为 O(d(n+k))O(d(n+k))、O(n+k)O(n+k)。适用前提是关键字能分解为有限位,且每位的稳定排序代价可控。

# 九、排序算法特征对比

算法最好时间平均时间最坏时间额外空间稳定
直接插入O(n)O(n)O(n2)O(n^2)O(n2)O(n^2)O(1)O(1)是
折半插入比较 O(nlog⁡n)O(n\log n),移动可为 O(n)O(n)O(n2)O(n^2)O(n2)O(n^2)O(1)O(1)是
冒泡(有提前结束)O(n)O(n)O(n2)O(n^2)O(n2)O(n^2)O(1)O(1)是
简单选择O(n2)O(n^2)O(n2)O(n^2)O(n2)O(n^2)O(1)O(1)否
希尔依增量序列而定依增量序列而定简单折半增量为 O(n2)O(n^2)O(1)O(1)否
快速O(nlog⁡n)O(n\log n)O(nlog⁡n)O(n\log n)O(n2)O(n^2)平均 O(log⁡n)O(\log n),最坏 O(n)O(n) 栈否
堆O(nlog⁡n)O(n\log n)O(nlog⁡n)O(n\log n)O(nlog⁡n)O(n\log n)O(1)O(1)否
归并O(nlog⁡n)O(n\log n)O(nlog⁡n)O(n\log n)O(nlog⁡n)O(n\log n)O(n)O(n)是
桶依分布而定均匀分布时可达 O(n+k)O(n+k)依桶内排序而定通常 O(n+k)O(n+k)依实现而定
基数O(d(n+k))O(d(n+k))O(d(n+k))O(d(n+k))O(d(n+k))O(d(n+k))O(n+k)O(n+k)是,逐位排序需稳定

# 十、各算法每趟特征

算法一趟完成后可以确定的性质
冒泡当前最大(升序时)元素到达未排序区末端
选择当前最小元素到达未排序区首端并固定
插入已排序前缀扩大一个元素,但前缀中旧元素可能移动
希尔每个间隔为 gap 的子序列有序
快速基准元素到达最终位置
堆当前堆顶元素到达有效区末端并固定
归并相邻有序段合并为更长有序段
基数 LSD当前位有序,同时保留此前低位的次序

# 十一、考场检查清单

  1. 比较排序的 Ω(nlog⁡n)\Omega(n\log n) 下界针对任意输入;分布排序靠关键字取值条件突破该下界。
  2. 稳定性要看相等关键字的相对次序是否会改变。
  3. 快速排序每趟固定的是基准位置,不是整个左右区间已经有序。
  4. 堆排序每趟固定一个堆顶元素;建堆总体为 O(n)O(n)。
  5. 基数排序各位排序必须稳定;桶排序复杂度依赖数据分布和桶内算法。
  6. 希尔排序复杂度必须与增量序列一起说明。
更新于 阅读次数 次

请我喝[茶]~( ̄▽ ̄)~*

梦前辈 微信支付

微信支付

梦前辈 支付宝

支付宝