- 归并排序:稳定、O(NlogN)
- 快速排序:不稳定、随机数据 O(NlogN)、最坏 O(N2)、相比归并和堆排的常数较小
- 堆排序:不稳定、O(NlogN)
- 桶排序/基数排序:了解概念即可,计数排序是一种特殊的桶排序
- 归并排序时求逆序对:O(NlogN),详见下面题目的题解区
- 快速排序思想求第 k 大数:O(N),详见下面题目的题解区
- 基于堆排序的优先队列:压入 O(logN)、弹出 O(logN)、查最大元素 O(1),详见下面题目的题解区
算法可视化
#include <bits/stdc++.h>
using namespace std;
int n;
int a[1123456];
int t[1123456]; //临时辅助数组
//将有序的 a[l] ~ a[mid] 及有序的 a[mid+1] ~ a[r] 有序合并
void merge_array(int l, int r)
{
// 1. 有序放入临时数组
int mid = (l + r) / 2;
int pl, pr, pt;
pl = l; // l ~ mid
pr = mid + 1; // mid+1 ~ r
pt = l; // l~r
//两边都还有元素
while (pl <= mid && pr <= r)
{
if (a[pl] <= a[pr])
{
// 可简写为 t[pt++] = a[pl++];
t[pt] = a[pl];
pt++;
pl++;
}
else
{
t[pt] = a[pr];
pt++;
pr++;
}
}
//只有一边有元素
while (pl <= mid)
{
t[pt] = a[pl];
pt++;
pl++;
}
while (pr <= r)
{
t[pt] = a[pr];
pt++;
pr++;
}
// 2. 从临时数组覆盖回来
for (int i = l; i <= r; i++)
a[i] = t[i];
}
//对 a[l] ~ a[r] 排序
void merge_sort(int l, int r)
{
if (l == r)
return;
int mid = (l + r) / 2;
merge_sort(l, mid); //对左半边排序
merge_sort(mid + 1, r); //对右半边排序
merge_array(l, r); //将有序的左右合并
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
merge_sort(1, n);
for (int i = 1; i <= n; i++)
cout << a[i] << " ";
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n;
int a[1000000+5];
//对 a[l]~a[r] 进行快速排序
void quick_sort(int l,int r){
//边界条件
if(l>=r) //只有一个元素或者区间不合法
return;
//可选操作:更换基准数(下面演示的是换成中间的数作为基准)
int mid = (l+r)/2;
swap(a[l],a[mid]);
//挑一个基准数
int key = a[l];
//划分左右:左边小于等于key,右边大于等于key
int pl = l, pr = r;
while(pl<pr)//还没有都指到空穴
{
// ( ) x x x x x
// pl pr
// 找到右边下一个比 key 小的,放在 pl 的位置
while(pr>pl&&a[pr]>=key)
pr--;
a[pl]=a[pr];
// x x x ( ) x x
// pl pr
// 找到左边下一个比 key 大的,放在 pr 的位置
while(pl<pr&&a[pl]<=key)
pl++;
a[pr]=a[pl];
}
//(划分好后:a[l~pl-1]<=a[pl/pr]<=a[pr+1~r])
// x x x ( ) x x
// pl/pr
a[pl] = key;
//分别对左右进行快速排序
quick_sort(l,pl-1);
quick_sort(pr+1,r);
}
int main()
{
//输入
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
//排序
quick_sort(1,n);
//输出
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int n;
int a[1123456];
//在原数组 a 上建立大根堆实现排序
int len; //堆的大小 a[1]~a[len]
void up(int pos)
{
int fa = pos / 2;
if (pos == 1 || a[pos] < a[fa])
return;
swap(a[pos], a[fa]);
up(fa);
}
void down(int pos)
{
int lson = pos * 2;
int rson = pos * 2 + 1;
if (lson > len)
return;
int best = pos;
if (lson <= len && a[lson] > a[best])
best = lson;
if (rson <= len && a[rson] > a[best])
best = rson;
if (best == pos)
return;
swap(a[pos], a[best]);
down(best);
}
int main()
{
//输入
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
//堆排序
len = 1;
for (int i = 2; i <= n; i++)
{
len++;
up(i);
}
while (len > 0)
{
swap(a[1], a[len]);
len--;
down(1);
}
//输出
for (int i = 1; i <= n; i++)
cout << a[i] << " ";
return 0;
}
视频演示