超详细排序汇总--插入排序类，选择排序类，交换排序类，归并排序，非比较排序

博客中所有代码均在leetcode912. 排序数组中执行

（一）插入排序类

1、直接插入排序

1）思路

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置后将array[i]插入，原来位置上的元素顺序后移

2）特性分析

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：完全逆序时最坏O(N^2)，完全顺序最好 O(N) 
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

3）代码

class Solution {
public://插入排序vector<int> sortArray(vector<int>& nums) {for(int i = 1; i < nums.size(); i++){int end = i - 1;int tmp = nums[i];while(end >= 0){if(nums[end] > tmp){nums[end+1] = nums[end];end--;}else break;}nums[end+1] = tmp;}return nums;}
};

4）leetcode运行结果 

 当数据量为50000时会超时 

2、希尔排序 

1）思路 

根据直接插入排序中接近有序时排序效率越高的特点，先对序列进行分组，对每一组进行预排序，最后再实施直接插入排序。

具体方法为：先选定一个整数gap，把待排序文件中所有记录分成个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，缩小gap值，重复上述分组和排序的工作。当gap=1时，所有记录在统一组内排好序。

2）特性分析

希尔排序的特性总结:

1. 希尔排序是对直接插入排序的优化。
2. 当gap>1时都是预排序，目的是让数组更接近于有序。当gap ==1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定。按照下边图片中的方法取gap，得时间复杂度为O(n^1.25)~O(1.6*n^1.25)。
4. 稳定性：不稳定。

3）代码

class Solution {
public://希尔排序vector<int> sortArray(vector<int>& nums) {int len = nums.size();int gap = nums.size() / 2;while(gap >= 1){for(int i = gap; i < len; i++){int end = i - gap;int tmp = nums[i];while(end >= 0){if(nums[end] > tmp){nums[end+gap] = nums[end];end-=gap;}else break;}nums[end+gap] = tmp;}gap /= 2;}return nums;}
};

4）leetcode运行结果 

（二）选择排序类

1、直接选择排序

1）思路 

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。 

1. 在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
2. 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
3. 在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

2）特性分析

直接选择排序的特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：最小最大均为O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定 

3）代码

一次选一个数最小

class Solution {
public://直接选择排序vector<int> sortArray(vector<int>& nums) {int len = nums.size();for(int i = 0; i < nums.size()-1; i++){int minNum = nums[i];int idx = i;for(int j = i+1; j < nums.size(); j++){if(minNum > nums[j]){minNum = nums[j];idx = j;}  }swap(nums[i],nums[idx]);}return nums;}
};

一次选两个数最小最大（最后交换的时候有一个坑）

class Solution {
public://直接选择排序vector<int> sortArray(vector<int>& nums) {int left = 0, right = nums.size()-1;while(left < right){int minIdx = left, maxIdx = left;for(int i = left + 1; i <= right; i++){if(nums[minIdx] > nums[i]) minIdx = i;if(nums[maxIdx] < nums[i])maxIdx = i;}swap(nums[left], nums[minIdx]);//如果left与maxIdx重叠if(maxIdx == left) swap(nums[right],nums[minIdx]);else swap(nums[right],nums[maxIdx]);left++,right--;}return nums;}
};

4）leetcode运行结果 

当数据量为50000时会超时 

2、堆排序

1）思路 

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。 

2）特性分析

堆排序的特性总结：

1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)--> 每一层从下往上遍历直到根节点需要高度logN，每一层填满系数为N，故为N*logN
3. 空间复杂度：O(1)
4. 稳定性：不稳定 

3）代码

class Solution {
public://堆排序void down(int u, vector<int>& nums, int len) {int t = u;int leftChild = u * 2 + 1;int rightChild = u * 2 + 2;if (leftChild < len && nums[leftChild] > nums[t]) t = leftChild;if (rightChild < len && nums[rightChild] > nums[t]) t = rightChild;if (t != u) {swap(nums[t], nums[u]);down(t, nums, len); // 继续向下递归}}vector<int> sortArray(vector<int>& nums) {// 建堆 (从最后一个非叶子节点开始下沉)for (int i = nums.size() / 2 - 1; i >= 0; i--) down(i, nums, nums.size());int len = nums.size();for (int i = nums.size() - 1; i > 0; i--) {swap(nums[0], nums[i]); // 堆顶元素和当前堆末尾元素交换len--;                  // 缩小堆的范围down(0, nums, len);     // 重新调整堆}return nums;}
};

4）leetcode运行结果 

（三）交换排序类

1、冒泡排序

1）思路 

通过多次遍历待排序的列表，从头到尾依次比较相邻的两个元素，如果前面的元素比后面的元素大，就交换它们的位置。每次遍历后，最大的元素会“冒泡”到最后的位置，直到整个列表有序为止。

2）特性分析

冒泡排序的特性总结：

1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)，经优化后若有序可为O(N)
3. 空间复杂度：O(1)
4. 稳定性：稳定 

3）代码

class Solution {
public://冒泡排序vector<int> sortArray(vector<int>& nums) {for(int i = 0; i < nums.size(); i++)//决定遍历次数，从后往前确定排序好的数for(int j = 1; j < nums.size() - i; j++)//两两比较，将最大的数向后移if(nums[j-1] > nums[j]) swap(nums[j-1],nums[j]);return nums;}
};

优化版

class Solution {
public://冒泡排序vector<int> sortArray(vector<int>& nums) {for(int i = 0; i < nums.size(); i++){int exchange = 0;for(int j = 1; j < nums.size() - i; j++)if(nums[j-1] > nums[j]) exchange = 1, swap(nums[j-1],nums[j]);if(exchange == 0) break;}return nums;}
};

4）leetcode运行结果 

当数据量为50000时会超时 

2、快速排序

1）思路 

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。 

a）hoare法

选取最左位置元素作为key值，从右往左遍历，当元素小于key时停止，再从左往右遍历，至当前元素大于key为止，交换两个元素，继续遍历。

左边做key右边先走原因：保证最后两者相遇位置一定比key值小or 相遇位置就是key的位置

1. R找到小，L找大没有找到，L遇到R；
2. R找小，没有找到，直接遇到L，要么就是一个比key小的位置或者直接到keyi

缺点：

如果 nums 已经有序（例如 [1, 2, 3, 4, 5]），在使用上述快速排序算法时可能会出现 性能下降 的问题，具体表现为时间复杂度从预期的平均 O(n log n) 退化为最坏的 O(n^2)。

原因：

• 当数组已经有序时，选择第一个元素作为基准元素（pivot）会导致非常不平衡的分区。例如，在有序数组 [1, 2, 3, 4, 5] 中，如果 pivot 总是选择最左边的元素 1，分区后的数组将是 [1] 和 [2, 3, 4, 5]，这意味着每次分区后只有一个元素被“正确”地放置，而剩下的数组依然有 n-1 个元素需要继续排序。

• 由于每次分区都非常不平衡（一个部分只有一个元素，另一个部分有 n-1 个元素），递归的深度会变成 n，从而导致时间复杂度退化为 O(n^2)。

解决方法：

1. 随机选择基准元素：为了避免最坏情况，可以在每次分区前随机选择一个元素作为基准元素，减少有序数组导致的最坏情况发生的概率。

2. 三数取中法：通过取 left、right 和中间位置 mid 这三个位置的元素，选择其中的中位数作为基准元素，这种方式也能有效减少在已经有序的数组上退化的概率。

b）挖坑法

c）前后指针法

核心思想：把比key大的值往右翻，比key小的值，翻到左边 

步骤：

1. cur找到比key小的值，++prev，cur和prev位置的值交换，++cur
2. cur找到比key大的值，++cur

说明： 

prev要么紧跟着cur(prev下一个就是cur)

prev跟cur中间间隔着比key大的一段值区间

d）小区间优化：

当子区间长度小于某个阈值时，使用插入排序对剩余元素进行排序。

e）非递归法

递归调用可能导致的栈溢出问题，下边使用非递归法。

1. 栈里面取一段区间，单趟排序
2. 单趟分割子区间入栈
3. 子区间只有一个值或者不存在就不入栈

2）特性分析

快速排序的特性总结：

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定 

3）代码

当前三种方法均使用递归法实现。非递归法在该部分最后（使用前后指针法+栈实现）

a）hoare法

以最左端元素作为key值

class Solution {
public://快速排序void quickSort(vector<int>& nums,int left, int right){if(left >= right) return;int i = left, j = right;int key = left;while(i < j){// 从右向左找小于基准的元素while(i < j && nums[j] >= nums[key]) j--;// 从左向右找大于基准的元素while(i < j && nums[i] <= nums[key]) i++;if(i < j) swap(nums[i],nums[j]);}// 最后将基准元素放到中间位置swap(nums[key],nums[i]);key = i;// 递归处理基准元素左右两侧的部分quickSort(nums,left,key-1);quickSort(nums,key+1,right);}vector<int> sortArray(vector<int>& nums) {quickSort(nums, 0, nums.size() - 1);return nums;}
};

随机选元素作为key值

class Solution {
public://快速排序void quickSort(vector<int>& nums,int left, int right){if(left >= right) return;int i = left, j = right;// 随机选择一个基准元素并与左边界元素交换int pivotIndex = left + rand() % (right - left + 1);swap(nums[left], nums[pivotIndex]);int key = left;while(i < j){// 从右向左找小于基准的元素while(i < j && nums[j] >= nums[key]) j--;// 从左向右找大于基准的元素while(i < j && nums[i] <= nums[key]) i++;if(i < j) swap(nums[i],nums[j]);}// 最后将基准元素放到中间位置swap(nums[key],nums[i]);key = i;// 递归处理基准元素左右两侧的部分quickSort(nums,left,key-1);quickSort(nums,key+1,right);}vector<int> sortArray(vector<int>& nums) {quickSort(nums, 0, nums.size() - 1);return nums;}
};

三数取中选key值 

class Solution {
public:// 获取三数中值的下标int getMiddleIndex(int left, int right, vector<int>& nums) {int middle = left + (right - left) / 2;int a = nums[left];int b = nums[middle];int c = nums[right];// 比较三者之间的大小，直接返回中间值的下标if ((a <= b && b <= c) || (c <= b && b <= a)) {return middle;} else if ((b <= a && a <= c) || (c <= a && a <= b)) {return left;} else {return right;}}//快速排序void quickSort(vector<int>& nums,int left, int right){if(left >= right) return;int i = left, j = right;// 三数取中选元素int pivotIndex = getMiddleIndex(left,right,nums);swap(nums[left], nums[pivotIndex]);int key = left;while(i < j){// 从右向左找小于基准的元素while(i < j && nums[j] >= nums[key]) j--;// 从左向右找大于基准的元素while(i < j && nums[i] <= nums[key]) i++;if(i < j) swap(nums[i],nums[j]);}// 最后将基准元素放到中间位置swap(nums[key],nums[i]);key = i;// 递归处理基准元素左右两侧的部分quickSort(nums,left,key-1);quickSort(nums,key+1,right);}vector<int> sortArray(vector<int>& nums) {quickSort(nums, 0, nums.size() - 1);return nums;}
};

b）挖坑法

class Solution {
public:// 快速排序 -- 挖坑法void quickSort(vector<int>& nums, int left, int right) {if (left >= right) return; // 递归结束条件，当左边界大于右边界时结束int i = left, j = right;int position = left; // 记录"坑"的位置int key = nums[left]; // 基准元素，取当前范围的第一个元素作为基准while (i < j) {// 从右向左寻找小于基准元素的元素while (i < j && nums[j] >= key) j--;if (i < j) {nums[position] = nums[j]; // 把找到的小于基准的元素填入"坑"中position = j; // 更新"坑"的位置}// 从左向右寻找大于基准元素的元素while (i < j && nums[i] <= key) i++;if (i < j) {nums[position] = nums[i]; // 把找到的大于基准的元素填入"坑"中position = i; // 更新"坑"的位置}}// 最后将基准元素放到"坑"的位置nums[position] = key;// 递归处理基准元素左右两侧的部分quickSort(nums, left, position - 1);quickSort(nums, position + 1, right);}// 对外接口，调用快速排序vector<int> sortArray(vector<int>& nums) {quickSort(nums, 0, nums.size() - 1);return nums;}
};

c）前后指针法

class Solution {
public:// 快速排序 -- 前后指针法void quickSort(vector<int>& nums, int left, int right) {if (left >= right) return; // 递归结束条件，当左边界不小于右边界时结束int key = nums[left];int pre = left, cur = left + 1;while (cur <= right) {if (nums[cur] < key) swap(nums[++pre], nums[cur]);cur++;}swap(nums[pre], nums[left]);// 递归处理基准元素左右两侧的部分quickSort(nums, left, pre - 1);quickSort(nums, pre + 1, right);}// 对外接口，调用快速排序vector<int> sortArray(vector<int>& nums) {quickSort(nums, 0, nums.size() - 1);return nums;}
};

d）小区间优化：

class Solution {
public://插入排序void insertSort(vector<int>& nums, int left , int right) {for(int i = left+1; i <= right; i++){int end = i - 1;int tmp = nums[i];while(end >= left){if(nums[end] > tmp){nums[end+1] = nums[end];end--;}else break;}nums[end+1] = tmp;}}// 快速排序 -- 前后指针法void quickSort(vector<int>& nums, int left, int right) {if (left >= right) return; // 递归结束条件，当左边界不小于右边界时结束int key = nums[left];int pre = left, cur = left + 1;while (cur <= right) {if (nums[cur] < key) swap(nums[++pre], nums[cur]);cur++;}swap(nums[pre], nums[left]);if(pre - left > 16)//设定阈值为16quickSort(nums, left, pre - 1);//快速排序elseinsertSort(nums,left,pre-1);//直接插入排序if(right - pre > 16)quickSort(nums, pre + 1, right);//快速排序else insertSort(nums,pre+1,right);//直接插入排序}// 对外接口，调用快速排序vector<int> sortArray(vector<int>& nums) {quickSort(nums, 0, nums.size() - 1);return nums;}
};

e）非递归法

class Solution {
public:typedef pair<int,int> PII;vector<int> sortArray(vector<int>& nums) {stack<PII> s;s.push({0,nums.size()-1});while(!s.empty()){int left = s.top().first;int right = s.top().second;s.pop();if(left >= right) continue;int pre = left, cur = left+1;int keyIdx = left;while(cur <= right){if(nums[cur] < nums[keyIdx]) swap(nums[cur],nums[++pre]);cur++;}swap(nums[pre],nums[keyIdx]);s.push({pre+1,right});s.push({left,pre-1});}return nums;}
};

4）leetcode运行结果 

a）hoare法 

以最左端元素作为key值结果：

数据量为50000时会超时

随机选元素作为key值结果： 

三数取中选key值方法结果：
 

b）挖坑法

c）前后指针法

数据量为50000时会超时

（四）归并排序

1、归并排序

1）思路 

该算法是采用分治法（Divide andConquer）的一个非常典型的应用。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

合并思路：依次比较，小的尾插到新空间

非递归法思路：

gap表示子数组中元素个数。从gap=1的子数组开始，每次将相邻的两个子数组合并为一个较大的有序子数组。然后将合并后的子数组的大小加倍（即gap*=2），再次进行合并。这个过程一直持续，直到合并后的子数组的大小大于或等于整个数组的大小为止。

出现的问题及其解决方法：

1. end1越界了怎么办-->不归并了
2. end1没有越界，begin2越界了怎么办? -->跟1一样处理
3. end1、begin没有越界，end2越界了怎么办？-->继续归并，修正end2

2）特性分析

归并排序的特性总结：

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定 

3）代码

a）递归法 

class Solution {
public:vector<int> tmp;void mergeSort(vector<int>& nums, int left, int right) {if(left >= right) return;int mid = left + (right - left) / 2;mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int k = left; // 用来记录 tmp 中的索引while(begin1 <= end1 && begin2 <= end2) {if(nums[begin1] < nums[begin2]) tmp[k++] = nums[begin1++];else tmp[k++] = nums[begin2++];}while(begin1 <= end1) tmp[k++] = nums[begin1++];while(begin2 <= end2) tmp[k++] = nums[begin2++];for(int i = left; i <= right; i++) {nums[i] = tmp[i];}}vector<int> sortArray(vector<int>& nums) {tmp.resize(nums.size());  // 将 tmp 数组的大小调整为 nums 的大小mergeSort(nums, 0, nums.size() - 1);return nums;}
};

b）非递归法

class Solution {
public:vector<int> tmp;void mergeSort(vector<int>& nums, int left, int right){int n = nums.size();tmp.resize(n);// 非递归合并排序for(int gap = 1; gap < n; gap *= 2) {// 合并大小为gap的子数组for(int i = 0; i + gap < n; i += 2 * gap) {int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = min(i + 2 * gap - 1, n - 1);int idx = 0;// 合并两个子数组int k = begin1;while (begin1 <= end1 && begin2 <= end2) {if(nums[begin1] <= nums[begin2]) tmp[k++] = nums[begin1++];else tmp[k++] = nums[begin2++];}while (begin1 <= end1) tmp[k++] = nums[begin1++];while (begin2 <= end2) tmp[k++] = nums[begin2++];// 将临时数组中的排序结果拷贝回原数组for (int j = i; j <= end2; ++j) {nums[j] = tmp[j];}}}}vector<int> sortArray(vector<int>& nums) {mergeSort(nums, 0, nums.size() - 1);return nums;}
};

4）leetcode运行结果 

a）递归法结果 

b）非递归法结果：

（五）非比较排序

1、计数排序

1）思路 

1. 利用哈希原理统计相同元素出现次数，使用相对位置映射
2. 根据统计的结果将序列回收到原来的序列中

2）特性分析

计数排序的特性总结：

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(MAX(N,范围))
3. 空间复杂度：O(范围)

3）代码

class Solution {
public:vector<int> sortArray(vector<int>& nums) {int maxNum = nums[0], minNum = nums[0];for(auto x : nums){maxNum = max(maxNum,x);minNum = min(minNum,x);}int range = maxNum - minNum + 1;vector<int> hash(range,0);for(auto x : nums){hash[x-minNum]++;}int k = 0;for(int i = 0; i < range; i++){while(hash[i]--) nums[k++] = minNum + i;}return nums;}
};

4）leetcode运行结果 

2、基数排序

1）思路 

通过将整数按位数分开，分别排序来实现最终的排序。基数排序的思路可以分为以下几个步骤：

1. 确定最大数的位数：找出待排序数组中最大的数，确定其位数 d。这是为了知道需要多少轮排序。

2. 从低位到高位进行排序：从最小的位（个位）开始，对数组中的每个数进行排序。在每一轮中，利用稳定的计数排序（或桶排序）对当前位进行排序。

3. 逐位处理：依次对十位、百位等更高位进行类似的排序。每一轮排序后，数组会逐步接近最终的有序状态。

4. 完成排序：当处理完最高位时，数组已经完全有序。

举例 ：

假设有一组数字 [170, 45, 75, 90, 802, 24, 2, 66]，基数排序的过程如下：

• 第一次排序：按个位数进行排序，结果为 [170, 90, 802, 2, 24, 45, 75, 66]
• 第二次排序：按十位数进行排序，结果为 [802, 2, 24, 45, 66, 170, 75, 90]
• 第三次排序：按百位数进行排序，结果为 [2, 24, 45, 66, 75, 90, 170, 802] 最后结果是按升序排列的。

2）特性分析

基数排序的特性总结：

1. 时间复杂度：基数排序的时间复杂度为 O(d×(n+k))，其中 d 是最大数的位数，n 是数组中元素的个数，k 是桶的数量。由于 k 和 d 通常是常数，基数排序的时间复杂度接近线性。

2. 空间复杂度：空间复杂度为 O(n+k)O(n + k)O(n+k)。由于需要额外的空间来存储中间结果，因此相对于其他一些排序算法，基数排序的空间开销可能较大。

3. 稳定性：稳定

4. 适用范围：基数排序适用于数据量大且数值范围较小的场景，特别是对非负整数排序非常有效。如果处理的数值范围较大，或数据类型比较复杂（如浮点数、字符串），可能需要进行适当的转换或使用其他排序算法。

3）代码

当前代码中增加了负数的处理逻辑 

#include <vector>
#include <algorithm>
using namespace std;class Solution {
public:vector<int> sortArray(vector<int>& nums) {if (nums.empty()) return nums;// 分离正数和负数vector<int> positiveNums, negativeNums;for (int num : nums) {if (num >= 0) {positiveNums.push_back(num);} else {negativeNums.push_back(-num);  // 负数取反}}// 对正数和负数分别进行基数排序if (!positiveNums.empty()) {radixSort(positiveNums);}if (!negativeNums.empty()) {radixSort(negativeNums);// 负数取反后再排序需要恢复负号for (int& num : negativeNums) {num = -num;}// 负数部分需要从大到小排序reverse(negativeNums.begin(), negativeNums.end());}// 合并负数和正数nums = negativeNums;nums.insert(nums.end(), positiveNums.begin(), positiveNums.end());return nums;}private:void radixSort(vector<int>& nums) {int maxVal = *max_element(nums.begin(), nums.end());for (int exp = 1; maxVal / exp > 0; exp *= 10) {countingSort(nums, exp);}}void countingSort(vector<int>& nums, int exp) {int n = nums.size();vector<int> output(n);vector<int> count(10, 0);for (int i = 0; i < n; i++) {int index = (nums[i] / exp) % 10;count[index]++;}for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}for (int i = n - 1; i >= 0; i--) {int index = (nums[i] / exp) % 10;output[count[index] - 1] = nums[i];count[index]--;}for (int i = 0; i < n; i++) {nums[i] = output[i];}}
};

4）leetcode运行结果