刷题 排序算法

912. 排序数组

注意这道题目所有 O(n^2) 复杂度的算法都会超过时间限制，只有 O(nlogn) 的可以通过

• 快速排序空间复杂度为 O(logn)是由于递归的栈的调用
• 归并排序空间复杂度为 O(n) 是由于需要一个临时数组 (当然也需要栈的调用，但是 O(logn) < O(n) 的忽略了)

基于插入的排序算法

直接插入排序

类似于打扑克牌的操作 直接插入排序(算法过程, 效率分析, 稳定性分析)

• 时间复杂度：最好情况 O(n), 最坏情况 O(n^2)
• 空间复杂度：O(1)
• 稳定性：是稳定的

class Solution {
public:vector<int> sortArray(vector<int>& nums) {// 插入排序for (int i = 1; i < nums.size(); ++i) {int cur_val = nums[i];int j = i - 1;while (j >= 0 && nums[j] > cur_val) {	// 寻找插入位置nums[j + 1] = nums[j];--j;}nums[j + 1] = cur_val;}return nums;}
};

折半插入排序

直接插入排序是使用 顺序查找的方法，从后往前寻找插入的位置
同理我们也可以使用二分查找的方式来寻找插入的位置
折半查找减少了比较的次数，将比较操作的时间复杂度降低为 O(logn)，但没有减少移动的次数，整体时间复杂度还是 O(n^2)

• 时间复杂度：最好情况 O(n), 最坏情况 O(n^2)
• 空间复杂度：O(1)
• 稳定性：是稳定的

class Solution {
public:int binarySearch(vector<int> nums, int right, int target) {// 找到第一个大于 target 的值int left = 0;// 使用左闭右闭区间while (left <= right) { // 区间不为空int mid = left + (right - left) / 2;// 循环不变量// nums[left - 1] <= target// nums[right + 1] > targetif (nums[mid] <= target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1;}}return left;}vector<int> sortArray(vector<int>& nums) {// 折半插入排序for (int i = 1; i < nums.size(); ++i) {int cur_val = nums[i];int insert_pos = binarySearch(nums, i - 1, cur_val);for (int j = i - 1; j >= insert_pos; --j) {nums[j + 1] = nums[j]; }nums[insert_pos] = cur_val;}return nums;}
};

希尔排序 - 插入排序的改进 - 缩小增量排序

插入排序在序列基本有序时效率较高

基于这个特点，希尔排序就是对数组分组进行插入排序，分组的组数就是 d，也即增量，一种简单的增量序列就是从 num.size() / 2 开始，一直缩小到 1，当然也可以采用其他的增量序列

• 时间复杂度：最好情况 O(n), 最坏情况 O(n^2)，平均复杂度 O(n^1.3)(了解即可)
• 空间复杂度：O(1)
• 稳定性：不稳定的

class Solution {
public:vector<int> sortArray(vector<int>& nums) {for (int d = nums.size() / 2; d >= 1; --d) {// 分组插入排序for (int k = 0; k < d; ++k) {// 组内进行插入排序for (int i = k + d; i < nums.size(); i += d) {int cur_val = nums[i];int j = i - d;while (j >= 0 && nums[j] > cur_val) {nums[j + d] = nums[j];j -= d;}nums[j + d] = cur_val;}}}return nums;}
};

基于交换的排序算法

冒泡排序

• 时间复杂度：最好情况 O(n), 最坏情况 O(n^2)
• 空间复杂度：O(1)
• 稳定性：稳定

class Solution {
public:vector<int> sortArray(vector<int>& nums) {// 冒泡排序for (int i = nums.size() - 1; i >= 1; --i) {bool swapped = false;for (int j = 0; j < i; ++j) {if (nums[j] > nums[j + 1]) {swap(nums[j], nums[j + 1]);swapped = true;}}if (!swapped) { // 没有发生交换，说明代码已经有序break;}}return nums;}
};

快速排序 图解 - 分治法

步骤：

• 随机选取一个位置 nums[i] = x
• 将大于 x 的值都移到 nums[i] 的左边，小于 x 的值都移动到 nums[i] 的右边
• 对 nums[0 ~i -1] 和 nums[i + 1 ~ n -1] 分别进行快速排序
• …

步骤中的核心问题：如何 将大于 x 的值都移到 nums[i] 的左边，小于 x 的值都移动到 nums[i] 的右边?

• 时间复杂度：最好情况 O(n), 最坏情况 O(n^2)
• 空间复杂度：O(1)
• 稳定性：稳定

class Solution {
public:void quickSort(vector<int>& nums, int left, int right) {if (left >= right) return; // 递归终止条件int p = partition(nums, left, right);quickSort(nums, left, p - 1);quickSort(nums, p + 1, right);}int partition(vector<int>& nums, int left, int right) {int p = left + rand() % (right - left + 1); // 生成 [left ~ right] 区间内的随机数swap(nums[p], nums[right]); // 将 pivot 和末尾值交换int i = left;// 维护的区间： [left, i) 区间内的值小于等于 nums[right]// [j, right) 区间内的值大于 nums[right]for (int j = left; j < right; ++j) {if (nums[j] <= nums[right]) {// 此时不满足我们对区间的要求了// 调整区间使其满足要求// {nums[left] ... nums[i-1]} {[nums[i] ... nums[j]]}swap(nums[i], nums[j]);++i;// --> {nums[left] ... nums[i-1] nums[j]} { ... nums[i]]}}}swap(nums[i], nums[right]);return i;}vector<int> sortArray(vector<int>& nums) {srand(time(0));     // 以当前时间为随机数种子quickSort(nums, 0, nums.size() - 1);return nums;}
};

但是上面这段代码提交还是会超过时间限制，由于当前的快速排序在处理包含大量相同元素的数组时，表现不佳。快速排序在最坏情况下的时间复杂度是 O(n^2)

使用三向切分的快速排序

三向切分是对标准快速排序的一种改进，特别适用于处理大量重复元素的情况。它将数组分为三个部分：

• 小于基准的部分
• 等于基准的部分
• 大于基准的部分

通过三向切分，可以避免在处理大量重复元素时退化为 O(n²)，使得时间复杂度保持在 O(n log n)。

class Solution {
public:void quickSort3Way(vector<int>& nums, int left, int right) {if (left >= right) return; // 递归终止条件int pivot = nums[left + rand() % (right - left + 1)]; // 选取随机基准int lt = left, i = left, gt = right;  // 初始化 lt、i、gt 指针// [left ~ lt) 小于 pivot// [lt, gt] 等于 pivot// [gt + 1, right] 大于 pivot while (i <= gt) {if (nums[i] < pivot) {swap(nums[lt], nums[i]);++lt;++i;} else if (nums[i] > pivot) {swap(nums[i], nums[gt]);--gt;   // 不能++i，因为换下来的这个数的值还没有跟 pivot 比较过} else {++i;}}// 递归处理小于和大于基准的部分quickSort3Way(nums, left, lt - 1);quickSort3Way(nums, gt + 1, right);}vector<int> sortArray(vector<int>& nums) {srand(time(0));  // 只需初始化一次随机数种子quickSort3Way(nums, 0, nums.size() - 1);return nums;}
};

选择排序

简单选择排序

• 时间复杂度：最好情况 O(n), 最坏情况 O(n^2)
• 空间复杂度：O(1)
• 稳定性：不稳定

不稳定性分析：
假设有一个数组 [4a, 2, 4b, 3]，其中 4a 和 4b 是两个相同值的元素，但具有不同的初始顺序。

• 第一轮：选择 2 作为最小元素，然后与 4a 交换，数组变为 [2, 4a, 4b, 3]。

• 第二轮：选择 3 作为最小元素，然后与 4a 交换，数组变为 [2, 3, 4b, 4a]。 注意此时 4a 和 4b 的相对顺序已经被改变：原本 4a 在 4b 之前，现在 4a被排在了 4b 之后。

因此，选择排序是不稳定的，因为它改变了相同值元素的初始顺序。

class Solution {
public:vector<int> sortArray(vector<int>& nums) {// 选择排序for (int i = 0; i < nums.size() - 1; ++i) {int min_idx = i;for (int j = i + 1; j < nums.size(); ++j) {if (nums[j] < nums[i]) {min_idx = j;            // 最小值的索引}}swap(nums[i], nums[min_idx]);   // 和最小值进行交换}return nums;}
};

堆排序 - 堆 - 完全二叉树 - 顺序存储

class Solution {
public:// 堆化函数：调整以 i 为根的子树，n 为堆的大小void heapify(vector<int>& nums, int n, int i) {int largest = i;      // 初始化为根节点int left = 2 * i + 1; // 左孩子int right = 2 * i + 2; // 右孩子// 如果左孩子比根节点大if (left < n && nums[left] > nums[largest]) {largest = left;}// 如果右孩子比当前最大值还大if (right < n && nums[right] > nums[largest]) {largest = right;}// 如果最大值不是根节点，交换并继续堆化if (largest != i) {swap(nums[i], nums[largest]);// 递归对受影响的子树进行堆化heapify(nums, n, largest);}}vector<int> sortArray(vector<int>& nums) {int n = nums.size();// 从最后一个非叶子节点开始建堆，调整整个堆for (int i = n / 2 - 1; i >= 0; --i) {heapify(nums, n, i);}// 逐一将堆顶元素与末尾元素交换，并重新调整堆for (int i = n - 1; i > 0; --i) {// 将当前堆顶（最大值）与末尾元素交换swap(nums[0], nums[i]);// 重新对剩下的部分进行堆化heapify(nums, i, 0);}return nums;}
};

归并排序

可以将排序问题分解成 将左半边排序 + 将右半边排序 + 合并左右两侧

• 时间复杂度： O(n log n)
• 空间复杂度：O(n) （源于临时数组）
• 稳定性：稳定

class Solution {
public:void mergeArray(vector<int> &nums, vector<int>& tmp, int left, int right) {if (right == left) return;              // 递归终止条件int mid = left + (right - left) / 2;mergeArray(nums, tmp, left, mid);       // 对左半边进行排序mergeArray(nums, tmp, mid + 1, right);  // 对右半边进行排序// 重要优化：如果左右两部分已经有序，可以跳过合并if (nums[mid] <= nums[mid + 1]) return;// 左右两侧均已完成排序，对二者进行合并int i = left, j = mid + 1, k = left;while (i <= mid && j <= right) {if (nums[i] <= nums[j]) {tmp[k++] = nums[i++]; } else {tmp[k++] = nums[j++];}}while (i <= mid) {tmp[k++] = nums[i++];}while (j <= right) {tmp[k++] = nums[j++];}copy(tmp.begin() + left, tmp.begin() + right + 1, nums.begin() + left);}vector<int> sortArray(vector<int>& nums) {vector<int> tmp(nums.size(), 0);mergeArray(nums, tmp, 0, nums.size() - 1);return nums;}
};