常见排序算法包括「冒泡排序」、「插入排序」、「选择排序」、「快速排序」、「归并排序」、「堆排序」、「基数排序」、「桶排序」。如下图所示，为各排序算法的核心特性与时空复杂度总结。
稳定性
- 相等元素排序之后相对位置不变
- 稳定的排序有如冒泡排序，不稳定有如快速排序
就地性
- 排序过程中不需要使用额外的内存（辅助数组）
- 原地排序有如：冒泡排序、快速排序，非原地排序有如归并排序
自适应性
- 排序的时间复杂度不会受到排序数组的元素分布的影响
- 自适应排序有如：冒泡排序、快速排序，
比较类
- 排序根据元素之间的比较算子（大于、小于、等于）来决定元素的相对顺序
- 大多数排序都是比较类排序，非比较类排序有：基数排序和桶排序
-
内循环：使用相邻双指针 j, j+1 从左至右遍历，依次比较相邻元素大小，较大元素逐渐冒泡到右边（升序）
-
外循环：不断重复「内循环」，每轮将当前最大元素交换至剩余未排序数组最右边，直到所有元素都被交换到正确位置
当某轮内循环没有交换元素时说明已经有序，可以直接退出外循环
void bubbleSort(vector<int>& nums) {
int N = nums.size();
for (int i = 0; i < N - 1; ++ i) { // 外循环
bool flag = false;
for (int j = 0; j < N - i - 1; ++ j) { // 内循环
if (nums[j] > nums[j+1]) {
// 交换
swap(nums[j], nums[j+1]);
flag = true;
}
}
// 如果没有交换元素说明已经有序了
if (!flag) break;
}
}- 哨兵划分：以数组某个元素为基准数，将所有小于基准数的元素移到其左边，大于基准数的元素移动其右边
- 递归：对左子数组和右子数组分别递归执行哨兵划分，直到子数组长度为1
int partition(vector<int>& nums, int l, int r) {
// 以 nums[l] 作为基准数，此时需要先搜索j
int i = l, j = r;
while (i < j) {
while (i < j && nums[j] >= nums[l]) -- j;
while (i < j && nums[i] <= nums[l]) ++ i;
swap(nums[i], nums[j]);
}
// 退出循环时 i == j
swap(nums[i], nums[l]);
return i;
}
void quickSort(vector<int>& nums, int l, int r) {
if (l >= r) return;
int i = partition(nums, l, r);
quickSort(nums, l, i-1);
quickSort(nums, i+1, r);
}注意：
- 当输入数组完全有序时，选择基准数之后每次划分之后递归深度会很高，因此可以考虑 每次递归较短子数组 或者 随机选择基准数
partition函数选择nums[l]作为基准数时必须先搜索j，因为如果先搜索i的话，i结束的位置可能是nums[i] >= nums[l]，最后交换nums[i] 和 nums[l]之后会把较大的数nums[i]交换到左边，这是不对的
- 「分」：不断将数组从中点位置划分，将原数组的排序问题转化成子数组的排序问题
- 「治」：划分到子数组长度为1时开始向上合并，不断将左右两个较短排序数组合并为一个较长排序数组，直至合并至原数组时完成排序
模板写法：
// 归并两个有序数组 [l...m] [m+1...r]
void mergeSort(vector<int>& nums, int l, int m, int r) {
// 需要一个临时数组存放归并之后的数，因此不是就地排序
vector<int> tmp(r-l+1);
int i = l, j = m + 1;
int idx = 0; // tmp 数组下标
while (i <= m && j <= r) {
if (nums[i] <= nums[j]) {
tmp[idx++] = nums[i++];
} else {
tmp[idx++] = nums[j++];
}
}
while (i <= m) tmp[idx++] = nums[i++];
while (j <= r) tmp[idx++] = nums[j++];
// 最后将归并的临时数组赋值到原数组上
// tmp[0...r-l] --> nums[l...r]
for (int k = 0; k < tmp.size(); ++ k) {
nums[l+k] = tmp[k];
}
}
// 递归
void merge(vector<int>& nums, int left, int right) {
int mid = left + (right - left) / 2;
if (left < right) {
merge(nums, left, mid);
merge(nums, mid+1, right);
mergeSort(nums, left, mid, right);
}
}K 神写法：
// tmp 是中间数组 用于存储排序之前的原数组
void merge_sort(int l, int r, vector<int> &nums, int tmp[]) {
if (l >= r) {
return ;
}
int m = l + (r - l) / 2;
merge_sort(l, m, nums, tmp);
merge_sort(m+1, r, nums, tmp);
// 此时 nums 的左子数组和右子数组都是排好序的
for (int k = l; k <= r; ++ k) {
tmp[k] = nums[k];
}
// 双指针开始归并: i, j 分别指向左右子数组的开始位置
int i = l, j = m + 1, k = l;
while(i <= m && j <= r) {
if (tmp[i] <= tmp[j]) {
nums[k++] = tmp[i++];
} else {
nums[k++] = tmp[j++];
}
}
// 归并剩余元素
while(i <= m) nums[k++] = tmp[i++];
while(j <= r) nums[k++] = tmp[j++];
}首先堆中插入元素就是末尾插入，然后调整堆；堆中取元素一般就是取首元素，然后也是调整堆
// 堆的长度为 n，节点 i 开始，从顶至底堆化
void siftDown(vector<int> &nums, int n, int i) {
while (true) {
int l = 2 * i + 1;
int r = 2 * i + 2;
int p = i;
// 比父节点大就交换
if (l < n && nums[l] > nums[p]) {
p = l;
}
if (r < n && nums[r] > nums[p]) {
p = r;
}
// 如果节点 i 最大或者索引 l, r 越界就无需堆化，直接退出
if (p == i) break;
swap(nums[i], nums[p]);
i = p; // 循环向下堆化
}
}
void heapSort(vector<int> &nums) {
// 建堆操作：堆化除叶节点以外的其他所有节点
// 必须从最后一个非叶子节点开始，这种建堆的方式比较高效，复杂度为O(n)
for (int i = nums.size() / 2 - 1; i >= 0; -- i) {
siftDown(nums, nums.size(), i);
}
// 从堆中提取最大元素，循环 n-1 轮
for (int i = nums.size()-1; i > 0; -- i) {
// 交换根结点与最右叶结点（交换首元素与尾元素）
swap(nums[0], nums[i]);
// 从根节点为起点，从顶至底进行堆化
siftDown(nums, i, 0);
}
}| 题目 | 说明 | 题解 |
|---|---|---|
| 剑指 Offer 40. 最小的k个数 | 可以先排序然后返回，也可以快速排序选择到下标为k-1时直接返回 | 通过 |
| 剑指 Offer 41. 数据流中的中位数 | 大顶堆存放比较小的一半元素，小顶堆存放比较大的一半元素 | 通过 |
| 剑指 Offer 45. 把数组排成最小的数 | 注意自定义排序不能写等号，如果写快速排序时需要注意比较方式 | 通过 |
| 剑指 Offer 61. 扑克牌中的顺子 | 没有重复元素且max-min<5 | 通过 |