排序
20221015114004
冒泡排序（Bubble Sort）（稳定排序）（超出时间限制）
比较相邻元素，如果第一个比第二个大，则交换。
时间复杂度$n^2$，空间复杂度1
代码：
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
// bubbleSort
int n = nums.size();
for (int i = 0; i < n - 1; ++i) {
bool flag = false;
for (int j = 0; j < n - 1 - i; ++j) {
if (nums[j] > nums[j + 1]) {
swap(nums[j], nums[j + 1]);
flag = true;
}
}
if (flag == false) break; //无交换，代表当前序列已经最优
}
return nums;
}
};
选择排序（Select Sort）（非稳定排序）（超出时间限制）
依次给每个位置选择当前位置及以后最小的元素（交换当前元素与之后最小元素的位置）。
不稳定举例：
排序前：5, 5*, 1, 7
排序后：1, 5*, 5, 7
时间复杂度$n^2$，空间复杂度1
代码：
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
// selectSort 选择排序
int minIndex;
int n = nums.size();
for (int i = 0; i < n - 1; ++i) {
minIndex = i;
for (int j = i + 1; j < n; ++j) {
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
swap(nums[i], nums[minIndex]);
}
return nums;
}
};
插入排序（Insect Sort）（稳定排序）（超出时间限制）
在前 1~i - 1元素有序的情况下，（依次）将第 i 个元素插入前面已经有序的小序列，使其有序。使用哨兵减少比较
时间复杂度$n^2$，空间复杂度1
代码：
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
int i, j;
for (i = 2; i <= nums.size(); i++) {
if (nums[i] < nums[i - 1]) {
nums[0] = nums[i]; //nums[0]为哨兵
for (j = i - 1; nums[0] < nums[j]; j--) {
nums[j + 1] =nums[j];
}
nums[j + 1] = nums[0];
}
}
return nums;
}
};
插入排序在此基础上也可以将搜索和移动分开，使用二分查找先找到要插入位置，然后再移动
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
int i, j, low, high, mid;
for (i = 2; i <= nums.size(); i++) {
nums[0] = nums[i];
low = 1; high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (nums[mid] > nums[0]) high = mid - 1;
else low = mid + 1;
}
for (j = i - 1; j > high + 1; j--)
nums[j + 1] = nums[j];
nums[high + 1] = nums[0];
}
return nums;
}
};
希尔排序（Shell Sort）（非稳定排序）
改进的插入排序（优化：原数组的一个元素距离正确位置很远的情况）
先让间隔 h 的元素有序，在使得间隔为 h / 2，一直缩小，一直到 h = 1（此时数组有序）。
时间复杂度介于nlogn和$n^2$之间，空间复杂度1
代码：
class Solution {
void shellSort(vector<int>&nums, int gap, int i) {
int j, tmp = nums[i];
for (j = i - gap; j >= 0 && tmp < nums[j]; j -= gap) {
// 依次后移
nums[j + gap] = nums[j];
}
nums[j + gap] = tmp;
}
public:
vector<int> sortArray(vector<int>& nums) {
int n = nums.size();
// 分组，最开始时，间隔 gap 为数组的一半
for (int gap = n / 2; gap >= 1 ; gap /= 2) {
// 对各个分组进行插入分组
for (int i = gap; i < n; ++i) {
shellSort(nums, gap, i);
}
}
return nums;
}
};
归并排序（Merge Sort）（稳定排序）
将无序数组拆分，排序后再合并成大的有序数组。
时间复杂度nlogn，空间复杂度n
代码：
class Solution {
vector<int> tmp;
void merge (vector<int>& nums, int low, int mid, int high) {
for (int k = low; k <= high; k++) {
tmp[k] = nums[k];
}
int i, j;
for (i = low, j = mid + 1, k = i; i <= mid && j <=high; k++) {
if (tmp[i] <= tmp[j]) {
nums[k] = tmp[i++];
} else {
nums[k] = tmp[j++];
}
}
while (i <= mid) nums[k++] = tmp[i++];
while (j <= high) nums[k++] = tmp[j++];
}
public:
vector<int> mergeSort(vector<int>& nums, int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
mergeSort(nums, low, mid + 1);
mergeSort(nums, mid + 1, high);
merge(nums, low, mid, high);
}
}
};
快速排序（Quick Sort）（非稳定排序）
随机选取一个数（x = rand() % len + startIndex）作为基准；
把比基准小的数交换到前面，比基准大的数交换到后面；
对左右区间递归重复。
时间复杂度nlogn，空间复杂度logn
代码：
class Solution {
void quickSort(vector<int>&nums, int startIndex, int endIndex) {
if (startIndex >= endIndex) return;
int x = rand() % (endIndex - startIndex + 1) + startIndex; // 基于随机的原则
swap(nums[startIndex], nums[x]);
int firstNum = nums[startIndex];
int l = startIndex, r = endIndex;
while (l < r) {
// 从后往前走，将比第一个小的移到前面
while (l < r && nums[r] >= firstNum) --r;
if (l < r) {
nums[l] = nums[r];
}
// 从前往后走，将比第一个大的移到后面
while (l < r && nums[l] <= firstNum) ++l;
if (l < r) {
nums[r] = nums[l];
}
}
nums[l] = firstNum;
// 自顶向下
quickSort(nums, startIndex, l - 1);
quickSort(nums, l + 1, endIndex);
}
public:
vector<int> sortArray(vector<int>& nums) {
int n = nums.size();
quickSort(nums, 0, n - 1);
return nums;
}
};
堆排序（Heap Sort）（非稳定排序）
先在原先数组的基础上构造大根堆（时间复杂度nlogn）；
再依次弹出最大元素（每次弹出的时间复杂度为logk，k为当前大根堆中元素数目）。
时间复杂度nlogn，空间复杂度1
代码：
class Solution {
void buildMaxHeap(vector<int>& nums) {
int n = nums.size();
for (int i = (n - 1) / 2; i >= 0; --i) {
maxHeapify(nums, i, n);
}
}
void maxHeapify(vector<int>& nums, int i, int n) {
while (i * 2 + 1 < n) {
// 代表当前 i 节点的左右儿子；
// 超出数组大小则代表当前 i 节点为叶子节点，不需要移位
int lSon = 2 * i + 1;
int rSon = 2 * i + 2;
int large = i;
if (lSon < n && nums[lSon] > nums[i]) large = lSon;
if (rSon < n && nums[rSon] > nums[large]) large = rSon;
if (large != i) {
swap(nums[i], nums[large]);
// 迭代判断对应子节点及其儿子节点的大小关系
i = large;
} else {
break;
}
}
}
public:
vector<int> sortArray(vector<int>& nums) {
// heapSort 堆排序
int n = nums.size();
// 将数组整理成大根堆
buildMaxHeap(nums);
for (int i = n - 1; i >= 1; --i) {
// 依次弹出最大元素，放到数组最后，当前排序对应数组大小 - 1
swap(nums[0], nums[i]);
--n;
maxHeapify(nums, 0, n);
}
return nums;
}
};
计数排序（Count Sort）（稳定排序）
创建数组 counts，用于统计原数组 nums 中各元素值的出现次数；
再依次将元素值赋值到 nums 中对应位置。
计数排序，时间复杂度n + k，空间复杂度k（k = maxNum - minNum + 1）
代码：
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
// CountSort 计数排序
int n = nums.size();
int minNum = INT_MAX, maxNum = INT_MIN;
// 找到数组中的最小和最大元素
for (int i = 0; i < n; ++i) {
if (nums[i] < minNum) minNum = nums[i];
if (nums[i] > maxNum) maxNum = nums[i];
}
// 构造计数数组
vector<int> counts(maxNum - minNum + 1, 0);
for (int i = 0; i < n; ++i) {
++counts[nums[i] - minNum];
}
// 计数排序
int index = 0;
for (int i = 0; i < counts.size(); ++i) {
while (counts[i] != 0) {
nums[index++] = i + minNum;
counts[i]--;
}
}
return nums;
}
};
桶排序（Bucket Sort）（稳定排序）
将原数组的元素分到有限数量的桶里（大编号桶里的所有元素均大于小编号桶里的任意元素）；
分别对每个桶进行排序；
依次合并。
时间复杂度n + k，空间复杂度n + k（k为桶的数量）
代码：
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
// BucketSort 桶排序
int n = nums.size();
// 获取数组的最小值和最大值
int maxNum = nums[0], minNum = nums[0];
for (int i = 1; i < n; ++i) {
if (nums[i] > maxNum) maxNum = nums[i];
if (nums[i] < minNum) minNum = nums[i];
}
// 初始化桶
int bucketNum = 5, bucketSize = (maxNum - minNum) / bucketNum + 1;
vector<vector<int>> buckets(bucketNum, vector<int>(0));
// 小至大分桶
for (int num : nums) {
int bucketIndex = (num - minNum) / bucketSize;
buckets[bucketIndex].emplace_back(num);
}
// 桶内排序
for (int i = 0; i < buckets.size(); ++i) {
sort(buckets[i].begin(), buckets[i].end());
}
// 从桶中依次取数
int index = 0;
for (auto& bucket : buckets) {
for (int num : bucket) {
nums[index++] = num;
}
}
return nums;
}
};
基数排序（Radix Sort）（稳定排序）
对数组中所有数依次按由低到高的位数进行多次排序；
每次排序都基于上次排序的结果。
（相对位置顺序保持不变）
例：原始数组 1，23，21，11，32
第一次排序后 1，21，11，32，23
第二次排序后 1，11，21，23，32
时间复杂度n x k，空间复杂度k（k为最大元素的位数）
代码：
class Solution {
vector<int> counts;
void radixSort(vector<int>& nums, vector<int>& tmp, int divisor) {
int n = nums.size();
counts = vector<int>(10, 0);
// 统计个、十、百、千、万上对应 0 ~ 9 的出现次数
for (int i = 0; i < n; ++i) {
int x = (nums[i] / divisor) % 10;
++counts[x];
}
// 前缀和
for (int i = 1; i <= 9; ++i) {
counts[i] += counts[i - 1];
}
// 从后向前赋值
for (int i = n - 1; i >= 0; --i) {
int x = (nums[i] / divisor) % 10;
int index = counts[x] - 1;
tmp[index] = nums[i];
--counts[x];
}
}
public:
vector<int> sortArray(vector<int>& nums) {
// RadixSort 基数排序
int n = nums.size();
// 预处理，让所有的数都大于等于0
for (int i = 0; i < n; ++i) {
nums[i] += 50000; // 50000为最小可能的数组大小
}
// 找出最大的数字，并获得其最大位数
int maxNum = nums[0];
for (int i = 0; i < n; ++i) {
if (nums[i] > maxNum) {
maxNum = nums[i];
}
}
int num = maxNum, maxLen = 0;
while (num) {
++maxLen;
num /= 10;
}
// 基数排序，低位优先
int divisor = 1;
vector<int> tmp(n, 0);
for (int i = 0; i < maxLen; ++i) {
radixSort(nums, tmp, divisor);
swap(tmp, nums);
divisor *= 10;
}
// 减去预处理量
for (int i = 0; i < n; ++i) {
nums[i] -= 50000;
}
return nums;
}
};
