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;}
};

折半插入排序

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;}
};

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

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;}
};

基于交换的算法>排序算法

冒泡排序

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;}
};

快速排序 图解 - 分治法

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²)，使得时间复杂度保持在 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;}
};

选择排序

简单选择排序

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;}
};

桶排序

桶排序

class Solution {
public:vector<int> sortArray(vector<int>& nums) {if (nums.empty()) {return nums;}// 找到数组中的最大值和最小值，用于确定桶的范围int minVal = *min_element(nums.begin(), nums.end());int maxVal = *max_element(nums.begin(), nums.end());// 桶的数量，选择合适的数量，通常是nums.size()int bucketCount = nums.size();// 创建桶，桶是一个二维向量，每个桶都是一个向量vector<vector<int>> buckets(bucketCount);// 分配元素到对应的桶for (int num : nums) {// 根据元素的值分配到对应的桶int bucketIndex = (num - minVal) * (bucketCount - 1) / (maxVal - minVal);buckets[bucketIndex].push_back(num);}// 对每个桶进行单独排序for (int i = 0; i < bucketCount; i++) {sort(buckets[i].begin(), buckets[i].end());}// 将所有桶中的元素合并回结果数组vector<int> sortedArray;for (const auto& bucket : buckets) {sortedArray.insert(sortedArray.end(), bucket.begin(), bucket.end());}return sortedArray;}
};

计数排序

class Solution {
public:vector<int> sortArray(vector<int>& nums) {if (nums.empty()) {return nums;}// 找到数组中的最大值和最小值int minVal = *min_element(nums.begin(), nums.end());int maxVal = *max_element(nums.begin(), nums.end());// 创建计数数组，大小为 (maxVal - minVal + 1)int range = maxVal - minVal + 1;vector<int> count(range, 0);// 计数每个元素出现的次数for (int num : nums) {count[num - minVal]++;}// 根据计数数组构造排序后的数组vector<int> sortedArray;for (int i = 0; i < range; i++) {while (count[i] > 0) {sortedArray.push_back(i + minVal);count[i]--;}}return sortedArray;}
};

基数排序

class Solution {
public:// 基数排序的主函数vector<int> sortArray(vector<int>& nums) {if (nums.empty()) {return nums;}// 找到数组中的最大值，确定最大位数int maxVal = *max_element(nums.begin(), nums.end());// 从最低位开始，对每个位进行排序for (int exp = 1; maxVal / exp > 0; exp *= 10) {countingSortByDigit(nums, exp);}return nums;}private:// 按照数字的某一位进行计数排序void countingSortByDigit(vector<int>& nums, int exp) {int n = nums.size();vector<int> output(n); // 临时数组存储排序结果vector<int> count(10, 0); // 计数数组，大小为10，因为数字位有0到9// 根据当前位 (exp) 统计每个数字出现的次数for (int i = 0; i < n; i++) {int digit = (nums[i] / exp) % 10;count[digit]++;}// 计算每个数字的累积计数，用于确定数字的最终位置for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}// 根据计数数组，将数字放入正确的位置for (int i = n - 1; i >= 0; i--) {int digit = (nums[i] / exp) % 10;output[count[digit] - 1] = nums[i];count[digit]--;}// 将排序后的数组复制回原数组for (int i = 0; i < n; i++) {nums[i] = output[i];}}
};