| 排序算法 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | 主要使用场景 |
|---|---|---|---|---|---|---|
| 直接插入排序 | 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 直接插入排序
当插入第 i 个元素时，前面的[0, i-1] 已经排好序了，此时用 arr[i] 和 arr[i-1]、arr[i-2]......依次比较，将原来位置上的元素后移，直到找到插入位置，将元素插入。
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。