排序算法

排序是算法学习的基石,不同算法在时间、空间、稳定性上各有取舍,理解其内部机制有助于在实际场景中做出最优选择。

简单排序:O(n²)

• 冒泡排序:反复比较相邻元素并交换,每轮将最大元素冒泡到末尾。最好情况(已有序)可加标志位优化到 O(n),稳定。
• 插入排序:将数组分为已排序与未排序两部分,从未排序部分取元素向前找到插入位置。对近乎有序的数据非常高效,稳定。
• 选择排序:每轮从未排序部分选出最小元素,与未排序部分的第一个元素交换。不稳定(交换会跨越相等的元素),无论数据如何均为 O(n²)。

高级排序:O(n log n)

• 归并排序:基于分治,递归地将数组对半拆分,合并两个有序子数组。稳定,时间恒为 O(n log n),但需要 O(n) 额外空间。
• 快速排序:选取一个基准(pivot),将数组划分为小于与大于基准的两部分,递归排序。平均 O(n log n),最坏 O(n²)(可通过随机化或三数取中避免),不稳定,原地排序。
• 堆排序:将数组视为完全二叉堆,反复取堆顶(最大元素)与末尾元素交换并下沉。时间 O(n log n),原地,不稳定。

线性排序:O(n)

• 计数排序:仅适用于范围较小的整数,统计每个值出现次数后按序还原,时间 O(n + k),稳定。
• 桶排序:将元素分到若干区间桶中,桶内排序后合并,适合均匀分布的数据。
• 基数排序:按位数从低到高(或高到低)进行多轮稳定排序(常用计数排序作为子过程),适合定长关键字(如整数、字符串)。

复杂度与稳定性对比

算法	最好	平均	最坏	空间	稳定性
冒泡排序	O(n)	O(n²)	O(n²)	O(1)	稳定
插入排序	O(n)	O(n²)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(n²)	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²)	O(log n)	不稳定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定
计数排序	O(n + k)	O(n + k)	O(n + k)	O(k)	稳定
桶排序	O(n)	O(n + k)	O(n²)	O(n + k)	稳定
基数排序	O(d·n)	O(d·n)	O(d·n)	O(n + k)	稳定

稳定性指相等元素的相对顺序在排序后是否保持。在多关键字排序(如先按部门再按工资)或作为更复杂算法的子步骤时,稳定性往往是关键要求。