比较插入、交换、选择、归并、快速、堆、桶和基数排序的过程、复杂度与稳定性,掌握各算法每趟排序后的特征。
# 一、排序的基本概念排序是按关键字次序重新排列记录。若排序前关键字相同的记录在排序后仍保持原有相对次序,则称排序算法稳定;否则不稳定。稳定性是算法属性,应结合具体实现判断。
内部排序的全部待排序记录都能放入内存。比较排序只依据关键字间比较,任意输入的比较排序最坏情况需要 Ω ( n log n ) \Omega(n\log n) Ω ( 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 ( n ) ;平均和最坏情况为 O ( n 2 ) O(n^2) O ( n 2 ) ;辅助空间为 O ( 1 ) O(1) O ( 1 ) 。适合规模较小或大部分有序的数据。
# 2. 折半插入排序折半插入排序用二分查找在有序前缀中确定插入位置,关键字比较次数降为 O ( n log n ) O(n\log n) O ( n log n ) ;但仍需移动后缀元素,最坏移动次数为 O ( n 2 ) O(n^2) O ( n 2 ) ,总时间仍为 O ( n 2 ) O(n^2) O ( n 2 ) 。将新元素插到相等元素之后可保持稳定。
# 三、交换排序# 1. 冒泡排序每趟比较相邻元素并交换逆序对,升序排序时最大元素逐趟移动到未排序区末尾。若一趟没有发生交换,可提前结束。采用严格大于时相等元素不交换,算法稳定;加提前结束标志后最好时间为 O ( n ) O(n) O ( n ) ,平均和最坏为 O ( n 2 ) O(n^2) O ( n 2 ) ,空间为 O ( 1 ) 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 ( n log n ) O(n\log n) O ( n log n ) ,最坏为 O ( n 2 ) O(n^2) O ( n 2 ) ;原地分区不计递归栈时只需 O ( 1 ) O(1) O ( 1 ) 额外空间,递归栈平均为 O ( log n ) O(\log n) O ( log n ) 、最坏为 O ( n ) O(n) O ( n ) 。交换可能改变相等记录的相对次序,通常不稳定。
# 四、选择排序简单选择排序每趟从未排序区选出最小关键字,与未排序区首元素交换。每趟选出的元素已经处于最终位置;比较次数始终为 Θ ( n 2 ) \Theta(n^2) Θ ( n 2 ) ,交换次数最多 n − 1 n-1 n − 1 次。跨越交换可能改变相等记录的次序,因此通常不稳定;空间为 O ( 1 ) O(1) O ( 1 ) 。
# 五、希尔排序希尔排序按增量 gap 将元素分成若干间隔子序列,对各子序列分别做插入排序,再逐步缩小 gap,最终令 gap 为 1 1 1 。早期的大增量先移动距离较远的元素,使最后一趟普通插入排序处理近乎有序的序列。
希尔排序不稳定。其时间复杂度依赖增量序列;采用简单折半增量时最坏为 O ( n 2 ) O(n^2) O ( n 2 ) ,不能在未给出增量序列时笼统声称固定的最优复杂度。
# 六、归并排序归并排序将序列递归分成两半,分别排序,再线性合并两个有序序列。合并时若两边关键字相等,先取左边记录可保持稳定。
时间复杂度为 O ( n log n ) O(n\log n) O ( n log n ) ,通常需要 O ( n ) O(n) O ( n ) 辅助数组。自底向上的非递归版本按子序列长度 1 , 2 , 4 , … 1,2,4,\ldots 1 , 2 , 4 , … 逐趟归并。
# 七、堆排序大根堆是完全二叉树,任一父结点关键字不小于孩子。用数组从 0 0 0 开始存储时,结点 i i i 的左孩子下标为 2 i + 1 2i+1 2 i + 1 ,右孩子为 2 i + 2 2i+2 2 i + 2 。堆排序流程:
从最后一个非叶子结点开始,自底向上调整为大根堆。 交换堆顶和当前末尾元素,最大关键字进入最终位置。 缩小堆的有效范围,对根重新向下调整。 重复直到剩一个元素。 建堆时间为 O ( n ) O(n) O ( n ) ,其后每次删除堆顶调整为 O ( log n ) O(\log n) O ( log n ) ,总时间为 O ( n log n ) O(n\log n) O ( n log n ) ;原地空间为 O ( 1 ) 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) O ( n + k ) ,但取决于分布、桶数 k k k 和桶内排序方法;空间通常为 O ( n + k ) O(n+k) O ( n + k ) 。稳定性也取决于桶内排序与分配方式。
# 2. 基数排序基数排序按关键字的每一位或每一组字符进行多趟稳定排序。低位优先(LSD)从最低有效位向高位处理,每一趟都必须稳定,才能保留前面较低位的次序;高位优先(MSD)从最高位递归分组,适合字符串或变长键。
若有 n n n 个记录、d d d 位关键字、每位基数为 k k k ,LSD 配合计数分配的时间和辅助空间通常为 O ( d ( n + k ) ) O(d(n+k)) O ( d ( n + k ) ) 、O ( n + k ) O(n+k) O ( n + k ) 。适用前提是关键字能分解为有限位,且每位的稳定排序代价可控。
# 九、排序算法特征对比算法 最好时间 平均时间 最坏时间 额外空间 稳定 直接插入 O ( n ) O(n) O ( n ) O ( n 2 ) O(n^2) O ( n 2 ) O ( n 2 ) O(n^2) O ( n 2 ) O ( 1 ) O(1) O ( 1 ) 是 折半插入 比较 O ( n log n ) O(n\log n) O ( n log n ) ,移动可为 O ( n ) O(n) O ( n ) O ( n 2 ) O(n^2) O ( n 2 ) O ( n 2 ) O(n^2) O ( n 2 ) O ( 1 ) O(1) O ( 1 ) 是 冒泡(有提前结束) O ( n ) O(n) O ( n ) O ( n 2 ) O(n^2) O ( n 2 ) O ( n 2 ) O(n^2) O ( n 2 ) O ( 1 ) O(1) O ( 1 ) 是 简单选择 O ( n 2 ) O(n^2) O ( n 2 ) O ( n 2 ) O(n^2) O ( n 2 ) O ( n 2 ) O(n^2) O ( n 2 ) O ( 1 ) O(1) O ( 1 ) 否 希尔 依增量序列而定 依增量序列而定 简单折半增量为 O ( n 2 ) O(n^2) O ( n 2 ) O ( 1 ) O(1) O ( 1 ) 否 快速 O ( n log n ) O(n\log n) O ( n log n ) O ( n log n ) O(n\log n) O ( n log n ) O ( n 2 ) O(n^2) O ( n 2 ) 平均 O ( log n ) O(\log n) O ( log n ) ,最坏 O ( n ) O(n) O ( n ) 栈 否 堆 O ( n log n ) O(n\log n) O ( n log n ) O ( n log n ) O(n\log n) O ( n log n ) O ( n log n ) O(n\log n) O ( n log n ) O ( 1 ) O(1) O ( 1 ) 否 归并 O ( n log n ) O(n\log n) O ( n log n ) O ( n log n ) O(n\log n) O ( n log n ) O ( n log n ) O(n\log n) O ( n log n ) O ( n ) O(n) O ( n ) 是 桶 依分布而定 均匀分布时可达 O ( n + k ) O(n+k) 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 ( d ( n + k ) ) O(d(n+k)) O ( d ( n + k ) ) O ( n + k ) O(n+k) O ( n + k ) 是,逐位排序需稳定
# 十、各算法每趟特征算法 一趟完成后可以确定的性质 冒泡 当前最大(升序时)元素到达未排序区末端 选择 当前最小元素到达未排序区首端并固定 插入 已排序前缀扩大一个元素,但前缀中旧元素可能移动 希尔 每个间隔为 gap 的子序列有序 快速 基准元素到达最终位置 堆 当前堆顶元素到达有效区末端并固定 归并 相邻有序段合并为更长有序段 基数 LSD 当前位有序,同时保留此前低位的次序
# 十一、考场检查清单比较排序的 Ω ( n log n ) \Omega(n\log n) Ω ( n log n ) 下界针对任意输入;分布排序靠关键字取值条件突破该下界。 稳定性要看相等关键字的相对次序是否会改变。 快速排序每趟固定的是基准位置,不是整个左右区间已经有序。 堆排序每趟固定一个堆顶元素;建堆总体为 O ( n ) O(n) O ( n ) 。 基数排序各位排序必须稳定;桶排序复杂度依赖数据分布和桶内算法。 希尔排序复杂度必须与增量序列一起说明。