在这之前。。。声明：
我还有这个排序算法的第二篇
点击下面的链接：
当然这些都是废话直接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吗。。。（蒟蒻的心里话）
切入正题：
十种常见排序算法可以分为两大类：
比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破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(nlog_2n)$，最坏时间复杂度$O(nlog_2n)$，最好时间复杂度$O(nlog_2n)$，空间复杂度$O(1)$
冒泡排序：平均时间复杂度$O(n^2)$，最坏时间复杂度$O(n^2)$，最好时间复杂度$O(n)$，空间复杂度$O(1)$
快速排序：平均时间复杂度$O(nlog_2n)$，最坏时间复杂度$O(n^2)$，最好时间复杂度$O(nlog_2n)$，空间复杂度$O(nlog_2n)$
归并排序：平均时间复杂度$O(nlog_2n)$，最坏时间复杂度$O(nlog_2n)$，最好时间复杂度$O(nlog_2n)$，空间复杂度$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)$
提前声明：如果有点懵可以看看最后面的链接🔗，有配动图详细解释。
高危预警⚠⚠⚠⚠⚠⚠⚠⚠⚠⚠
1、冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
算法描述
1.比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3.针对所有的元素重复以上的步骤，除了最后一个；
4.重复步骤1~3，直到排序完成。
总共要循环$n-1$次
参考代码：
#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（优先队列）：
#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)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
感谢$xlz$大佬给的桶排代码！
参考代码：
#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})$的时间
参考资料：
