在这之前。。。声明：
我还有这个排序算法的第二篇
点击下面的链接：
c++排序算法整理2{:target=”_blank”}
当然这些都是废话直接sort多好。。。
//放眼望去。。。好眼熟啊。。。
//当然身为神犇大佬的你不希望自己渺小到只会用sort。。。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int main(){
scanf("%d", &n);
for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
sort(a + 1, a + 1 + n);//<--!!!!!AC必备经典代码。。。。。
for (int i = 1;i <= n; i++) printf("%d ", a[i]); puts("");
return 0;
}
像上面这样简洁的代码难道不XIANG吗。。。（蒟蒻的心里话）
虽然我们平时排序可以直接上$STL$的专用武器$Sort$
但是我们还是有必要学习排序的方法
（就像某些人说的应付面试）
切入正题：
十种常见排序算法可以分为两大类：
比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。 包括插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序和归并排序
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。包括计数排序、桶排序和基数排序
| 排序算法名称 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 插入排序 | $O(n^2)$ | $O(n^2)$ | $O(n)$ | $O(1)$ | 稳定 |
| 希尔排序 | $O(n^{1.3})$ | $O(n^2)$ | $O(n)$ | $O(1)$ | 不稳定 |
| 选择排序 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 不稳定 |
| 堆排序 | $O(n log_2 n)$ | $O(n log_2 n)$ | $O(n log_2 n)$ | $O(1)$ | 不稳定 |
| 冒泡排序 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 稳定 |
| 快速排序 | $O(n log_2 n)$ | $O(n^2)$ | $O(n log_2 n)$ | $O(n log_2 n)$ | 不稳定 |
| 归并排序 | $O(n log_2 n)$ | $O(n log_2 n)$ | $O(n log_2 n)$ | $O(n)$ | 稳定 |
| 计数排序 | $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | 稳定 |
| 桶排序 | $O(n+k)$ | $O(n^2)$ | $O(n)$ | $O(n+k)$ | 稳定 |
| 基数排序 | $O(n \times k)$ | $O(n \times k)$ | $O(n \times k)$ | $O(n+k)$ | 稳定 |
相关概念
稳定：如果$a$原本在$b$前面，而$a=b$，排序之后$a$仍然在$b$的前面。
不稳定：如果$a$原本在$b$的前面，而$a=b$，排序之后 $a$ 可能会出现在 $b$ 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
提前声明：如果有点懵可以看看最后面的链接🔗，有配动图详细解释。
高危预警⚠⚠⚠⚠⚠⚠⚠⚠⚠⚠
1、冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
算法描述
1.比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3.针对所有的元素重复以上的步骤，除了最后一个；
4.重复步骤1~3，直到排序完成。
总共要循环$n-1$次
有一种冒泡排序的优化，叫鸡尾酒排序
点击最上面的链接c++排序算法整理2查看~
参考代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int a[MAXN], n;
int main(){
scanf("%d", &n);
for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
for (int i = n;i > 1; i--)
for(int j = 1;j < i; j++)
if(a[j] > a[j + 1]) swap(a[j], a[j + 1]); //交换两个数
for (int i = 1;i <= n; i++) printf("%d ", a[i]); puts("");
return 0;
}
2、选择排序（Selection Sort）
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
参考代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int a[MAXN], n;
int main(){
scanf("%d", &n);
for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
for (int i = 1;i < n; i++) {
int w = i, Min = a[i];
for (int j = i;j <= n; j++) if(Min > a[j]) w = j, Min = a[j]; //寻找🔎最小数和它的位置
swap(a[i], a[w]);
}
for (int i = 1;i <= n; i++) printf("%d ", a[i]); puts("");
return 0;
}
3、插入排序（Insertion Sort）
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
参考代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int a[MAXN], n;
int main(){
scanf("%d", &n);
for (int i = 1;i <= n; i++) {
scanf("%d", &a[i]); int x = i - 1;
while(a[x] > a[x + 1] && x > 0) swap(a[x], a[x + 1]), x--;
}
for (int i = 1;i <= n; i++) printf("%d ", a[i]); puts("");
return 0;
}
4、希尔排序（Shell Sort）
1959年$Shell$发明，第一个突破$O(n^2)$的排序算法（听起来挺厉害的。。。），是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
算法描述
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
选择一个增量序列$t1,t2,t3,.. . tk$，其中$ti>tj,tk=1$；
按增量序列个数$k$，对序列进行$k$趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为$m$的子序列，分别对各子表进行直接插入排序。仅增量因子为$1$时，整个序列作为一个表来处理，表长度即为整个序列的长度。
参考代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int main(){
scanf("%d", &n);
for (int i = 0;i < n; i++) scanf("%d", &a[i]);
for (int step = n / 2; step > 0; step /= 2)
for (int i = 0;i < step; i++)
for (int j = i + step;j < n; j += step)
if(a[j] < a[j - step]) {
int temp = a[j];
int k = j - step;
while (k >= 0 && temp < a[k]) {
swap(a[k + step], a[k]);
k -= step;
}
}
for (int i = 0;i < n; i++) printf("%d ", a[i]); puts("");
return 0;
}
5、归并排序（Merge Sort）
归并排序是建立在归并操作上的一种有效的排序算法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
算法描述
把长度为n的输入序列分成两个长度为$n/2$的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。
参考代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN], T[MAXN];
void Mergesort(int l, int r) {
if (l == r) return; //区间内只有一个数，返回
int mid = l + r >> 1; //相当于(l + r) / 2
Mergesort(l, mid); //递归左半部分
Mergesort(mid + 1, r); //递归右半部分
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r) //合并
if (a[i] <= a[j]) T[k++] = a[i++];
else T[k++] = a[j++];
while (i <= mid) T[k++] = a[i++];
while (j <= r) T[k++] = a[j++];
for (int q = l; q <= r; q++) a[q] = T[q]; //转移
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
Mergesort(1, n);
for (int i = 1; i <= n; i++) printf("%d ", a[i]);
return 0;
}
6、快速排序（Quick Sort）
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
参考代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
void quickSort(int l, int r) {
if (l >= r) return;
int i = l, j = r, base = a[l]; //base取最左边的数为基准数
while(i < j) {
while (a[j] >= base && i < j) j--;
while (a[i] <= base && i < j) i++;
if (i < j) swap(a[i], a[j]);
}
a[l] = a[i]; a[i] = base; //基准数归位
quickSort (l, i - 1); //递归左边
quickSort (i + 1, r); //递归右边
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
quickSort(1, n);
for (int i = 1; i <= n; i++) printf("%d ", a[i]);
return 0;
}
7、堆排序（Heap Sort）
堆排序（Heap-sort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
参考代码：
#include <bits/stdc++.h>
using namespace std;
int n;
const int MAXN = 1e8 + 10;
int h[MAXN], size;
void down(int u) {
int t = u; // t记录最小值
if (2 * u <= size && h[2 * u] < h[t]) t = 2 * u; // 左儿子
if (2 * u + 1 <= size && h[2 * u + 1] < h[t]) t = 2 * u + 1; // 右儿子
if (t != u) { //需要调整
swap(h[t], h[u]);
down(t); //递归
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++) scanf("%d", &h[i]);
size = n;
for (int i = n / 2; i >= 1; i--) down(i); //初始化堆
while (n--) {
printf("%d ", h[1]);
h[1] = h[size]; size--;
down(1);
}
return 0;
}
参考代码2（优先队列）：
//感慨万千：STL太好用了！
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n;
priority_queue<int, vector<int>, greater<int> >q; //小根堆
int main() {
scanf("%d", &n); int x;
for (int i = 1;i <= n; i++) scanf("%d", &x), q.push(x);
while (!q.empty()) {
printf("%d ", q.top()); //入队
q.pop(); //出队
}
return 0;
}
8、计数排序（Counting Sort）
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
参考代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
long long n, cnt[MAXN];
int main() {
scanf("%lld", &n); int x = 0, Max = -0x3f3f3f, Min = 0x3f3f3f; //初始化最大值和最小值
for (int i = 1; i <= n; i ++) {
scanf("%d", &x); cnt[x]++; //统计
Max = max(Max, x); Min = min(Min, x); //更新最大值和最小值
}
for (int i = Min;i <= Max; i++)
while(cnt[i]) cnt[i]--, printf("%d ", i); //输出
return 0;
}
9、桶排序（Bucket Sort）
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
参考代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, Min = MAXN, Max = 0, sum[MAXN];
bool f[45];
vector<int> bucket[45];//定义桶，这里定义40个桶
void insertsort(int s) {
for (int i = 0;i < bucket[s].size(); i++)
for (int j = i;j >= 1; j--) if(bucket[s][j - 1] > bucket[s][j]) swap(bucket[s][j], bucket[s][j - 1]);//这里是从小到大排序
for (int i = 0;i < bucket[s].size(); i++) printf("%d ", bucket[s][i]); //由于每个桶都是有序的，所以可以输出这个桶，节省了一次遍历的时间
}
void bucketsort() {
for (int i = 1;i <= n; i++)
bucket[int((sum[i] - Min) / ((Max - Min + 1) / 40.0))].push_back(sum[i]), f[int((sum[i] - Min) / ((Max - Min + 1) / 40.0))] = 1;//运用最大最小值来合理分配桶
for (int i = 0;i <= 40; i++) if(f[i]) insertsort(i); //如果当前桶有数值，则对桶内的数进行排序（这里用选择排序）
}
int main() {
scanf("%d", &n);
for (int i = 1;i <= n; i++) {
scanf("%d", &sum[i]);
Min = min(Min, sum[i]), Max = max(Max, sum[i]); //为了能够合理利用空间，确保第一个桶和最后一个桶都有数，所以存储最大最小值
}
bucketsort();
return 0;
}
10、基数排序（Radix Sort）
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
参考代码：
#include <bits/stdc++.h>
using namespace std;
int maxbit(int data[], int n) {
int d = 1, p = 10; //d保存最大的位数
for (int i = 0;i < n; i++) while(data[i] >= p) p *= 10, d++;
return d;
}
void radixsort(int data[], int n) { //基数排序
int d = maxbit(data, n);
int tmp[n];
int cnt[15], i, j, k, radix = 1;
for (i = 1;i <= d; i++) { //进行d次排序
memset(cnt, 0, sizeof(cnt)); //清空计数器
for (j = 0;j < n; j++) {
k = (data[j] / radix) % 10;
cnt[k]++;
}
for (j = 1;j < 10; j++) cnt[j] += cnt[j - 1];
for (j = n - 1;j >= 0; j--) {
k = (data[j] / radix) % 10;
tmp[cnt[k] - 1] = data[j];
cnt[k]--;
}
for (j = 0;j < n; j++) data[j] = tmp[j];
radix *= 10;
}
}
const int MAXN = 1e8 + 10;
int n, array[MAXN];
int main(){
scanf("%d", &n);
for (int i = 0;i < n; i++) scanf("%d", &array[i]);
radixsort(array, n);
for (int i = 0;i < n; i++) printf("%d ", array[i]); puts("");
}
如释重负。。。
还没呢。。。
搜了些算法时间复杂度分析大家可以康康：
稳定的排序
鸡尾酒排序（cocktail sort）— $O(n^2)$
原地归并排序— $O(n log_2 n)$如果使用最佳的现在版本
二叉排序树排序（binary tree sort）— $O(n log n)$期望时间；$O(n^2)$最坏时间；需要$O(n)$额外空间
鸽巢排序（pigeonhole sort）— $O(n+k)$；需要$O(k)$额外空间
基数排序（radix sort）— $O(n \times k)$；需要$O(n)$额外空间
侏儒排序（gnome sort）— $O(n^2)$
图书馆排序（library sort）— $O(n log_2 n)$期望时间；$O(n^2)$最坏时间；需要$(1+ε)n$额外空间
块排序（block sort）— $O(n log_2 n)$
不稳定的排序
Clover排序算法（Clover sort）— $O(n)$期望时间，$O(n^2)$最坏情况
梳排序— $O(n log n)$
平滑排序（smooth sort）— $O(n log_2 n)$
内省排序（introsort）— $O(n log_2 n)$
耐心排序（patience sort）— $O(n log_2 n + k)$最坏情况时间，需要额外的$O(n + k)$空间，也需要找到最长的递增子序列（longest increasing subsequence）
不实用的排序
(奇葩的排序)
猴子Bogo排序 — $O(n × n!)$，最坏的情况下期望时间为无穷，不过最好时间复杂度为$O(1)$。
Stupid排序 — $O(n^3)$;递归版本需要$O(n^2)$额外存储器
珠排序（bead sort）— $O(n)$ or $O(\sqrt n)$,但需要特别的硬件
煎饼排序 — $O(n)$,但需要特别的硬件
臭皮匠排序（stooge sort）算法简单，但需要约$O(n^{2.7})$的时间
参考资料：
梦开始的地方
你这不就是把人家的东西搬过来吗
考古
但是这不重要吧，我懂了就行了（）
还有蠢猴排序，直到宇宙的热寂都排不出来
第二个帖子
哇这……作者比我用心多了。
谢谢！
来踩踩大佬%%%
hh%%%
太太强了！！
谢谢谢谢大佬！！
有点东西
# 写的很多，没看完，先点个赞
谢谢资瓷！
@ssuunn xlz不是在DTOJ上给你了吗
我现在也不是我是sun了，我又改名了……
。。。。。
…
…
望神犇大佬们给个桶排代码
桶排可以啊
写个给你
需要写注释吗
……这是多少个月前的事了，早就知道了。。。
不过还是Thanks大佬给的代码
啊这
# 这是计数排序！！！不是桶排啊啊啊！
你怎么和别人一样。。。
但是你好像没加上去啊
我刚刚自己写的啊
我知道啊，但是这是计数排序，不是桶排
你记录的每个数出现了几次，就没了呀
？？？？
这不是桶排。。。
我不太确定，某个人告诉我是桶排，还有双重桶排我也会
（如果是的话）
这就是桶排啊
好像就是桶排
桶排不是吧，我看桶排和计数排序网上代码都一样……
思想都不一样
差距很大
他发的就对
你可以搜一下
否则你觉得MAXmin都是干啥的
XDDDD