10. 七大排序(含四种版本快排及优化) ******
| 排序算法 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | 主要使用场景 |
|---|---|---|---|---|---|---|
| 直接插入排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 | 小规模数据或基本有序数据 |
| 希尔排序 | O(n^1.3) | O(n²) | O(n log n) | O(1) | 不稳定 | 中等规模数据，对稳定性无要求 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 | 小规模数据，交换次数最少 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 | 大规模数据，需要原地排序 |
| 冒泡排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 | 小规模数据 |
| 快速排序 | O(n log n) | O(n²) | O(n log n) | O(log n)~O(n) | 不稳定 | 大规模数据，通用排序 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 | 大规模数据，需要稳定排序 |
目录
1. 插入排序
1.1 直接插入排序
1.2 希尔排序
2. 选择排序
2.1 选择排序
2.2 堆排序
3. 交换排序
3.1 冒泡排序
3.2 快速排序
1.霍尔版本：
2.挖坑法：
3. 前后指针法(推荐)
4. 快排非递归(掌握)
3.3 快速排序的优化方法
1. 三数取中法选key
2.递归到小的子区间时，可以考虑使用插入排序
4.归并排序
1. 插入排序
1.1 直接插入排序
当插入第 i 个元素时，前面的[0, i-1] 已经排好序了，此时用 arr[i] 和 arr[i-1]、arr[i-2]......依次比较，将原来位置上的元素后移，直到找到插入位置，将元素插入。
912. 排序数组
class Solution
{
public:
vector<int> sortArray(vector<int>& nums)
{
int n = nums.size();
for(int i=1; i<n; i++)
{
int j = i-1;
int tmp = nums[i];
while(j >= 0 && tmp < nums[j]) //如果要排序的值小于前面某位置的值
{
nums[j+1] = nums[j];//前面的值向后一个位置移
j--;//继续向前找
}
nums[j+1] = tmp;//当要排序的值大于等于j位置的值，就可以放到j后面的一个位置
}
return nums;
}
};1.2 希尔排序
希尔排序的基本思想是：先选定一个gap，将待排序的数据按gap分组，对每组进行排序，当取gap=1时，数组接近有序，使用插入排序就会很快。
class Solution
{
public:
vector<int> sortArray(vector<int>& nums)
{
int n = nums.size();
for(int gap=n/2; gap>0; gap/=2)
{
for(int i=gap; i<n; i++)
{
int j = i-gap;
int x = nums[i];
while(j >= 0 && x < nums[j])
{
nums[j+gap] = nums[j];//nums[j]的值后放到 j+gap
j -= gap;
}
nums[j+gap] = x;
}
}
return nums;
}
};我们可以发现和插入排序的代码差不多，希尔排序是对直接插入排序的优化。
当 gap>1时都是预排序，目的是让数组更接近于有序。当gap = 1时，数组接近有序，在进行直接插入排序就会很快。达到优化的效果。
我们可以发现gap=1时，上面的代码就是直接插入排序的代码。
因为gap的取值方式很多，所以时间复杂度不好计算，我们记个O(N^1.3)就行。
2. 选择排序
2.1 选择排序
每次从待排序数据中选择最小(大)的那个，存放在序列的起始位置，直到全部待排序元素排完。
上图中红色的就是遍历数组中选出的当前的最小值，遍历结束后，和当时的排好序的下一个位置进行交换。
class Solution
{
public:
vector<int> sortArray(vector<int>& nums)
{
int n = nums.size();
for(int i=0; i<n-1; i++)//遍历准备交换的位置
{
int mini = i;
for(int j=i+1; j<n; j++)//找min位置
{
if(nums[j] < nums[mini])
mini = j;
}
if(mini != i)//如果最小位置不是i位置就交换，相等就没必要交换了
swap(nums[mini], nums[i]);
}
return nums;
}
};实际中很少使用，好理解但是效率不高。
2.2 堆排序
排升序-建大堆：大的数在堆顶，和最后比较小的数据交换，然后把堆顶这个小的数据向下调整，大的就放到了数组最后，最后排出来就是升序的数组。
排降序-建小堆：同理，小的在堆顶，小的一直和大的换，小的就被放到了数组最后。
上图就是从建堆-向上调整建立大堆-大堆排升序。
7. 二叉树****-CSDN博客 中有关于堆的详细介绍和实现。
class Solution
{
public:
vector<int> sortArray(vector<int>& nums)
{
//建大堆
int n = nums.size();
for(int i=(n-1)-1/2; i>=0; i--)//从i这个位置开始向前调整，可以确保每次调整时，子树已经是堆结构
{
adjustdown(nums, i, n);//向下调整需要子树都是堆
}
//堆排
for(int i=n-1; i>0; i--)
{
swap(nums[i], nums[0]);
adjustdown(nums, 0, i);
}
return nums;
}
void adjustdown(vector<int>& nums, int parent, int sz)
{
int child = parent*2+1;
while(child < sz)
{
if(child+1 < sz && nums[child+1] > nums[child])
child++;
if(nums[child] > nums[parent])
{
swap(nums[child], nums[parent]);
parent = child;
child = parent*2+1;
}
else
break;
}
}
};3. 交换排序
根据两个值的比较结果来对换两个值在序列中的位置，将大的向尾部移动，值小的向前移动。
3.1 冒泡排序
class Solution
{
public:
vector<int> sortArray(vector<int>& nums)
{
int n = nums.size();
for(int i=0; i<n-1; i++)
{
bool exchange = false;
for(int j=0; j<n-i-1; j++)//每一趟都把最大的放到最后，所以要-i，i=1时说明最后一个位置放好了
{
if(nums[j] > nums[j+1])
{
swap(nums[j], nums[j+1]);
exchange = true;
}
}
if(exchange = false)//如果某轮没有交换过，说明已经排序好了，程序可以结束了
break;
}
return nums;
}
};3.2 快速排序
任取待排序元素序列中的某元素作为基准值，按照该元素将待排序列分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，重复该过程，直到所有元素排好。
将区间按照基准值划分为左右两部分的常见方式有三种：
1.霍尔版本：
我们需要一左一右两个指针，left 指向6， right 指向8，最左边 6 做 keyi。
如果 left < right：
right一定要先走(才能保证相遇时一定比k小)，right 从右向左找比 k 小的，找到一个5，停下；
left 从左向右找比 k 大的，找到一个7，停下；
交换5和7
left < right，然后重复上面的过程，right先走找到4，left后走找到9，交换：
继续重复，right先走找比k小，找到3，left后走找比k大，没找到，与right相遇了：
然后交换 nums[keyi] 和 nums[left]，当前这个keyi的位置就排好了。
然后去 keyi 的左边和右边的区间分别走同样的快排。
class Solution
{
public:
vector<int> sortArray(vector<int>& nums)
{
int n = nums.size();
QuickSort1(nums, 0, n-1);
return nums;
}
void QuickSort1(vector<int>& nums, int left, int right)
{
if(left >= right)
return;
int begin = left, end = right;//递归要用每更新的left和right找区间
int keyi = left;
while(left < right)
{
while(left < right && nums[right] >= nums[keyi])
right--;
while(left < right && nums[left] <= nums[keyi])
left++;
swap(nums[left], nums[right]);
}
swap(nums[left], nums[keyi]);
keyi = left;
QuickSort1(nums, begin, keyi-1);
QuickSort1(nums, keyi+1, end);
}
};2.挖坑法：
和第一种差不多，只不过多了一个“坑”的中间状态
选最左边为key，key为坑，先右左移找比k小，找到就放进坑里，right指向的为新坑；
左向右移找比k大，找到就放进坑里，left指向为新坑，
left < right，重复上述过程。直到left == right时，两者相遇在坑中，坑里填最开始选的key。
class Solution
{
public:
vector<int> sortArray(vector<int>& nums)
{
int n = nums.size();
QuickSort2(nums, 0, n-1);
return nums;
}
void QuickSort2(vector<int>& nums, int left, int right)
{
if(left >= right)
return;
int begin = left, end = right;//递归要用每更新的left和right找区间
int key = nums[left];
int hole = left;
while(left < right)
{
while(left < right && nums[right] >= key)
right--;
nums[hole] = nums[right];
hole = right;
while(left < right && nums[left] <= key)
left++;
nums[hole] = nums[left];
hole = left;
}
nums[hole] = key;
QuickSort2(nums, begin, hole-1);
QuickSort2(nums, hole+1, end);
}
};3. 前后指针法(推荐)
初始时，prev指向数组开头，cur指向prev下个位置：
然后 cur 找到比 key 小的，++prev，cur 与 prev 交换：
但是如果++prev == cur，那就没必要交换了，交换了也一样，直接cur++
如果要交换，换完以后 cur++
此时cur又小于key，但是++prev == cur，cur++，cur指向7，大于key，cur++，直到指向3：
++prev ！= cur，交换他们的值：
换完以后cur++，指向4，小于key，++prev ！= cur，交换以后，cur++指向5
又小于key，++prev ！= cur，交换以后cur++
cur指向的一直大于key，一直++，直到大于right，此时交换prev指向的值和key。
完成一轮的排序，接下来还是去左区间和右区间排序，和前两种方法是一样的。
为什么可以这样直接换：
prev要么紧跟cur，要么紧跟大于key的数，既然它紧跟大于key的，说明它本身小于key，所以可以直接换。
class Solution
{
public:
vector<int> sortArray(vector<int>& nums)
{
int n = nums.size();
QuickSort3(nums, 0, n-1);
return nums;
}
void QuickSort3(vector<int>& nums, int left, int right)
{
if(left >= right)
return;
int begin = left, end = right;//递归要用每更新的left和right找区间
int keyi = left;
int prev = left, cur = prev+1;
while(cur <= right)
{
if(nums[cur] < nums[keyi] && ++prev != cur)
swap(nums[cur], nums[prev]);
cur++;
}
swap(nums[prev], nums[keyi]);
keyi = prev;
QuickSort3(nums, begin, keyi-1);
QuickSort3(nums, keyi+1, end);
}
};4. 快排非递归(掌握)
递归的问题是如果深度太深会栈溢出。
class Solution
{
public:
vector<int> sortArray(vector<int>& nums)
{
int n = nums.size();
QuickSortNR(nums, 0, n-1);
return nums;
}
//由快排前后指针改造来的单次排序分区函数
int partSort3(vector<int>& nums, int left, int right)
{
int keyi = left;
int prev = left, cur = prev+1;
while(cur <= right)
{
if(nums[cur] < nums[keyi] && ++prev != cur)
swap(nums[cur], nums[prev]);
cur++;
}
swap(nums[prev], nums[keyi]);
keyi = prev;
return keyi;
}
void QuickSortNR(vector<int>& nums, int left, int right)
{
stack<int> st;
st.push(right);
st.push(left);
while(!st.empty())
{
int begin = st.top();
st.pop();
int end = st.top();
st.pop();
int keyi = partSort3(nums, begin, end);
if(keyi + 1 < end)
{
st.push(end);
st.push(keyi+1);
}
if(begin+1 < keyi)
{
st.push(keyi-1);
st.push(begin);
}
}
}
};
解释：
int keyi = partSort3(nums, begin, end);
根据当前的begin和end进行单趟排序的同时，得出一个新keyi，下面再根据这个新的keyi划分左右区间，入栈，栈不为空就取栈中前两个数做新的begin、end单趟排序。直到栈为空，说明所有区间都排过序了。
3.3 快速排序的优化方法
1. 三数取中法选key
| 优化方法 | 时间复杂度保证 | 额外开销 | 抗极端数据能力 | 实现复杂度 |
|---|---|---|---|---|
| 随机选择 | 平均 O(nlogn) | 随机数生成 | 强 | 简单 |
| 三数取中 | 平均 O(nlogn) | 三次比较 | 更强 | 中等 |
大多数标准库（如 C++ std::sort）采用三数取中，因为它在实际数据中表现更稳定，比纯随机选择更快（减少约 5%-10% 的比较次数）。
int GetMidNumi(vector<int>& nums, int left, int right)
{
int mid = (left + right) / 2;
if (nums[left] < nums[mid])
{
if (nums[mid] < nums[right]) //left mid right
return mid;
else if (nums[left] > nums[right])
return left; //right left mid
else
return right; //left right mid
}
else // nums[left] > nums[mid]
{
if (nums[mid] > nums[right]) //right mid left
return mid;
else if (nums[left] < nums[right])
return left; //mid left right
else
return right; //mid right left
}
}
上面注释中代表的是下标对应的值的大小顺序。很明显的看出返回中间那个。
2.递归到小的子区间时，可以考虑使用插入排序
进一步优化：
结合两者（三数取中 + 小规模数组改用插入排序）是更高级的优化策略。
int PartSort3(vector<int>& nums, int left, int right)
{
int midi = GetMidNumi(nums, left, right);
if(midi != left)
swap(nums[midi], nums[left]);//最好中位数去做key值
int keyi = left;
int prev = left, cur = prev+1;
while(cur <= right)
{
if(nums[cur] < nums[keyi] && ++prev != cur)
swap(nums[cur], nums[prev]);
cur++;
}
swap(nums[prev], nums[keyi]);
keyi = prev;
return keyi;
}
void QuickSort(vector<int>& nums, int left, int right)
{
if (left >= right)
return;
// 小区间优化--小区间直接使用插入排序
if ((right - left + 1) > 10)
{
int keyi = PartSort3(nums, left, right);
QuickSort(nums, left, keyi - 1);
QuickSort(nums, keyi + 1, right);
}
else
{
InsertSort(nums+left, right - left + 1);
}
}小区间使用插入排序代替递归效率更高。
4.归并排序
归并是建立在归并操作上的一种有效的排序算法，该算法是采用分治法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序数组合成一个有序数组，称为二路归并。
class Solution
{
vector<int> tmp;
public:
vector<int> sortArray(vector<int>& nums)
{
tmp.resize(nums.size());
mergeSort(nums, 0, nums.size()-1);
return nums;
}
void mergeSort(vector<int>& nums, int left, int right)
{
//递归出口
if(left >= right)
return;
//选择中间点划分
int mid = (left+right)/2;
//左右区间递归处理
mergeSort(nums, left, mid);
mergeSort(nums, mid+1, right);
//合并两个有序数组
int cur1 = left, cur2 = mid+1, i = 0;
while(cur1 <= mid && cur2 <= right)
{
tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
}
//处理没有遍历完的数组
while(cur1 <= mid) tmp[i++] = nums[cur1++];
while(cur2 <= right) tmp[i++] = nums[cur2++];
//还原到nums
for(int i=left; i<=right; i++)
{
nums[i] = tmp[i-left];//tmp每次都是从0开始的，nums是从left开始的
}
}
};大体过程分两步：
分：将数组一分为二两部分，一直分解到数组的长度为1，left == right，都指向这个数，return。使整个数组的排序过程被分为左半部分排序+右半部分排序。
治：将两个较短的有序数组合并成一个长的有序数组，一直合并到最初的长度。
比如5，2，3，1这个数组，一直分两部分最后就分成5，2两个长度为1的数组，他们各自的left == right，return，然后合并这两个数。合并完以后把tmp的内容放到nums中，此时一开始的merge(nums, 0, 1)结束了，该走merge(nums, 2, 3)也就是另一半了，同样的过程，最后把2，5和1，3合并到tmp中，用tmp更新nums。