sortings排序

用途：Given an array that contains n elements, your task is to sort the elements in increasing order.

以下排序，比较排序

这些算法都有一个有趣的性质：在排序的最终结果中，各元素的次序依赖于它们之间的比较。我们把这类排序算法称为 Comparison sorts比较排序。

01 bubble sort 冒泡排序 稳定

Bubble Sort(冒泡排序)是一种简单直观的排序算法。它重复地走访要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行，直到没有再需要交换，也就是说该数列已经排序完成。

这个算法的名字由来是因为 越大/越小 的元素会经由交换慢慢 “浮” 到数列的顶端(右边)。冒泡排序，排序n轮，每一轮遍历一遍数组。当发现两个连续数字顺序不对时，交换他们。如果是正序排列，每一次swap，减少一个逆序对。问：整个冒泡排序进行了几次swap，就是数列中有多少逆序对。

冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。

什么时候最快 ，当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊）

什么时候最慢 ，当输入的数据是反序时（写一个 for 循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗）

时间复杂度：
空间复杂度：

#include <bits/stdc++.h>
using namespace std;
int a[110], n;
void bubble_sort01(){
    for (int i = 0; i < n; i++)                  //枚举有几趟冒泡
        for (int j = 0; j < n - 1; j++)
            if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);
}
void bubble_sort02(){
    for (int i = 0; i < n; i++)                  //枚举有几趟冒泡
        for (int j = 0; j < n - i - 1; j++)   //每一趟j的终点发生优化
            if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);
}
void bubble_sort03(){
    for (int i = n - 1; i > 0; i--)          //枚举每趟冒泡的终点
        for (int j = 0; j < i; j++)
            if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);
}
void bubble_sort04(){
    for (int i = n - 1; i > 0; i--){          //枚举每趟冒泡的终点
        bool flag = false;                    //立一个flag
        for (int j = 0; j < i; j++)              //如果一趟下来没有交换，    
        if (a[j] > a[j + 1]){                 //就表示已经有序
                swap(a[j], a[j + 1]);
                flag = true;
            }
        if (!flag) break;
    }
}
int main(){
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    bubble_sort04();
    for (int i = 0; i < n; i++) cout << a[i] << ' ';
    puts("");
    return 0;
}
/*
5  
3 4 2 1 5
1 2 3 4 5 
*/

第一轮过后，最大数字被放在了正确的位置上。k轮过后，k个最大的数字被放在了正确的位置上。n轮过后，n个数字（这个数组）被放在了正确位置上。

需要注意的是，冒泡排序只交换相邻两个数字。在整个冒泡排序的过程中，进行了几次swap操作，就表示序列当中，有几个逆序对。

如果，整个序列是倒序的，如果要冒泡成正序，交换次数是1+2+3...+(n-1) = n*(n-1)/2

02 selection sort 选择排序 不稳定

选择排序是一种简单直观的排序算法，无论什么数据进去都是的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

算法步骤：

1. 首先在未排序序列中找到最小(最大)元素，存放到排序序列的起始位置
2. 再从剩余未排序元素中继续寻找最小(最大)元素，然后放到已排序序列的末尾
3. 重复第二步，直到所有元素均排序完毕

时间复杂度：
空间复杂度：

#include <bits/stdc++.h>
using namespace std;
int a[110], n;
void selection_sort(){
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)          //枚举未排序的部分
            if (a[j] < a[i]) swap(a[j], a[i]);   //把最小的交换到a[i]上
}
int main(){
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    selection_sort();
    for (int i = 0; i < n; i++) cout << a[i] << ' ';
    puts("");
    return 0;
}
/*
5  
3 4 2 1 5
1 2 3 4 5 
*/

03 insertion sort 插入排序 稳定

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。

时间复杂度：
空间复杂度：

#include <bits/stdc++.h>
using namespace std;
int a[110], n;
void insertion_sort(){
    for (int i = 1; i < n; i++){   //从第二个数a[1]开始
        int t = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > t){
            a[j + 1] = a[j];      //依次往后坐一位
            j--;
        }
        a[j + 1] = t;             //跳出while时，j指向的是第一个a[j]<=t的位置
    }
}
int main(){
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    insertion_sort();
    for (int i = 0; i < n; i++) cout << a[i] << ' ';
    puts("");
    return 0;
}
/*
5  
3 4 2 1 5
1 2 3 4 5 
*/

// 二分插入排序
#include <bits/stdc++.h>
using namespace std;
int a[110], n;
void insertion_sort(){
    for (int i = 1; i < n; i++){   // 从第二个数a[1]开始
        int t = a[i];
        // 二分找到要插入的位置
        int l = 0, r = i - 1, best = 0;
        while (l <= r){
            int mid = (l + r) >> 1;
            if (a[mid] < t){
                l = mid + 1;
                best = mid + 1;
            }
            else r = mid - 1;
        }
        for (int j = i - 1; j >= best; j--) a[j + 1] = a[j];
        a[best] = t;        
    }
}
int main(){
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    insertion_sort();
    for (int i = 0; i < n; i++) cout << a[i] << ' ';
    puts("");
    return 0;
}
/*
5  
3 4 2 1 5
1 2 3 4 5 
*/

04 shell sort 希尔排序 不稳定

希尔排序是希尔 (Donald Shell) 于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破的第一批算法之一。

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为的排序（冒泡排序或插入排序），可能会进行 n 次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。

一个更好理解的希尔排序实现：将数组列在一个表中并对列排序（用插入排序）。重复这过程，不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身仅仅对原数组进行排序（通过增加索引的步长，例如是用 i += step_size 而不是 i++ ）。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序是非稳定排序算法。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。

希尔排序耗时的操作有：比较 + 后移赋值
1) 最好情况：
序列是正序排列，在这种情况下，需要进行的比较操作需（n-1）次。后移赋值操作为0次。即
2) 最坏情况：
希尔排序的平均时间复杂度和最坏时间复杂度与间距序列的选取（就是间距如何减小到 1）有关，比如「间距每次除以 3」的希尔排序的时间复杂度是。已知最好的最坏时间复杂度为
3) 平均时间复杂度：

时间复杂度：最好，最坏，平均根据步长序列的不同而不同，
空间复杂度：
https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F

#include <bits/stdc++.h>
using namespace std;
int a[110], n;
void shell_sort(int a[], int len){
    int h = 1;
    while (h < len / 3) h = h * 3 + 1;
    while (h >= 1){
        for (int i = h; i < len; i++)
            for (int j = i; j >= h && a[j] < a[j - h]; j -= h)
                swap(a[j], a[j - h]);
        h /= 3;
    }
}
int main(){
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    shell_sort(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << ' ';
    puts("");
    return 0;
}
// 比较神奇，shell_sort可以过1e5的数据
// https://www.acwing.com/problem/content/description/787/

05 merge sort 归并排序 分治 逆序对 稳定

归并排序（merge sort）是建立在归并操作上的一种有效的排序算法。
该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

• 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）
• 自下而上的迭代

算法步骤：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4. 重复步骤 3 直到某一指针达到序列尾；
5. 将另一序列剩下的所有元素直接复制到合并序列尾。

时间复杂度：
空间复杂度：

// 代码实现，见分治
void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

06 quick sort 快速排序 分治 不稳定

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

算法过程：

1. 从数列中挑出一个元素，称为 “基准”（pivot）;
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

算法过程简化版：
两个哨兵，一个从左走，一个从右走
相遇后，左边都比 j 小，右边都比 j 大

快速排序的最坏运行情况是 O(n²)，比如说有序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

快速排序是一种原地排序，只需要一个很小的栈作为辅助空间，空间复杂度为O(logn)，所以适合在数据集比较大且无序的时候使用。

空间的消耗主要是递归造成的栈空间使用，最好情况，递归树的深度为，其空间复杂度也就为，最坏情况，需要进行 n‐1 递归调用，其空间复杂度为，平均情况，空间复杂度也为。

特殊，对单链表进行快排，是稳定的。

时间复杂度：
空间复杂度：

// 代码实现，见分治
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

07 heap sort 堆排序 不稳定

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。

分为两种方法：

1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

算法步骤：

1. 创建一个堆 H[0……n-1]；
2. 把堆首（最大值）和堆尾互换；
3. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
4. 重复步骤 2，直到堆的尺寸为 1。

时间复杂度：最好O(nlogn)，最坏O(nlogn)，平均O(nlogn)
空间复杂度：O(1)

堆排序是一个优秀的算法，但是在实际应用中，快排的性能一般会优于堆排序。堆有一个常见的应用：作为高效的优先队列(priority queue)。优先队列是一种用来维护一组元素构成的集合S的数据结构，其中的每一个元素都有一个相关的值，称为关键字(key)。主要用途：能够O(1)时间返回堆顶元素。

// 会用STL  priority_queue 默认大根堆
// 如何使用小根堆
// 插入的数值，放负数，转为小根堆
// 或者自定义struct，重载小于符号
// 这块知识放在STL展开，在图论求最短路时会应用

以下排序，非比较排序

下面介绍三种线性时间复杂度的排序算法：计数排序、基数排序和桶排序。
这些算法是 用运算 而不是 用比较 来确定排序顺序的。

这部分的描述，比《算法导论》好理解太多了。。 良心推荐

08 counting sort 计数排序 稳定

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是。计数排序不是比较排序，因此不被 的下界限制。

由于用来计数的数组 C 的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。

例如：计数排序是用来排序 0 到 100 之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序算法中，能够更有效的排序数据范围很大的数组。

通俗地理解，例如，有 10 个年龄不同的人，统计出有 8 个人的年龄比 A 小，那 A 的年龄就排在第 9 位，用这个方法可以得到其他每个人的位置，也就排好了序。当然，年龄有重复时需要特殊处理(保证稳定性)，这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去1。

算法的步骤如下：

1. 找出待排序的数组中最大和最小的元素
2. 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项
3. 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）(做前缀和)
4. 反向填充目标数组：将每个元素 i 放在新数组的第 C[i] 项，每放一个元素就 C[i] 减去 1

时间复杂度：，k代表待排序数据的值域大小
空间复杂度：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 110;
int cnt[N], maxn = -1;
int a[M], b[M], n;
void counting_sort(){
    //cnt[x] 记录x出现的次数
    for (int i = 0; i < n; i++) cnt[a[i]]++;                 
    //维护出 比x小的有多少个
    for (int i = 1; i <= maxn; i++) cnt[i] += cnt[i - 1];    
    //b[排第几个] = 原数组中的数值
    //从后往前拿，cnt从大到小，保证了稳定性
    for (int i = n - 1; i >= 0; i--) b[--cnt[a[i]]] = a[i];  
}
int main(){
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> a[i];
        maxn = max(maxn, a[i]);
    }
    counting_sort();
    for (int i = 0; i < n; i++) cout << b[i] << ' ';
    puts("");
    return 0;
}
/*
5  
3 4 2 1 5
1 2 3 4 5 
*/

例题：CSP2019 入门组第一轮 计数排序

https://zhuanlan.zhihu.com/p/397169636

09 radix sort 基数排序 稳定

https://zh.wikipedia.org/zh-cn/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F

如果考虑和比较排序进行对照，基数排序的形式复杂度虽然不一定更小，但由于不进行比较，因此其基本操作的代价较小，而且在适当选择的B之下，k一般不大于logn，所以基数排序一般要快过基于比较的排序，比如快速排序。

基数排序是稳定的。

时间复杂度：
空间复杂度：

// n个数，每个数有k个关键字
// 对这n个数，进行k个关键字排序
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, k;       //n个数，每个数有k个关键字
int maxn = 100; //每个关键字最大是100
int cnt[N];
struct node{
    int key[110]; //模拟100位数
    bool operator< (const node& W)const{
        for (int i = 1; i <= k; i++){
            if (key[i] == W.key[i]) continue;
            return key[i] < W.key[i];
        }
        return false;
    }
}a[N], b[N];
void counting_sort(int p){
    memset(cnt, 0, sizeof cnt);
    for (int i = 0; i < n; i++) cnt[a[i].key[p]]++;
    for (int i = 1; i <= maxn; i++) cnt[i] += cnt[i - 1];
    // 为保证排序的稳定性，此处循环i应从n到1
    // 即当两元素关键字的值相同时，原先排在后面的元素在排序后仍应排在后面
    for (int i = n - 1; i >= 0; i--) b[--cnt[a[i].key[p]]] = a[i];
    memcpy(a, b, sizeof a);
}
void radix_sort(){
    for (int i = k; i >= 1; i--)
        counting_sort(i);
}
int main(){
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        for (int j = 1; j <= k; j++) cin >> a[i].key[j];
    //sort(a, a + n);  //自定义一个快排，模拟数据进行验证
    radix_sort();
    for (int i = 0; i < n; i++){
        for (int j = 1; j <= k; j++) cout << a[i].key[j] << ' ';
        puts("");
    }
    return 0;
}
/*
3 3
33 44 55
11 22 33
33 55 66
3 3
33 11 22
11 22 33
88 22 10
*/

// 下面这份代码，a[i]是1-index
// 这在从桶里拿数的时候，是b[cnt[a[i].key[p]]--] = a[i];
// 而不是b[--cnt[a[i].key[p]]] = a[i];
// 这和排n, n-1是有关系的
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, k;       //n个数，每个数有k个关键字
int maxn = 100; //每个关键字最大是100
int cnt[N];
struct node{
    int key[110]; //模拟100位数
    bool operator< (const node& W)const{
        for (int i = 1; i <= k; i++){
            if (key[i] == W.key[i]) continue;
            return key[i] < W.key[i];
        }
        return false;
    }
}a[N], b[N];
void counting_sort(int p){
    memset(cnt, 0, sizeof cnt);
    for (int i = 1; i <= n; i++) cnt[a[i].key[p]]++;
    for (int i = 1; i <= maxn; i++) cnt[i] += cnt[i - 1];
    // 为保证排序的稳定性，此处循环i应从n到1
    // 即当两元素关键字的值相同时，原先排在后面的元素在排序后仍应排在后面
    for (int i = n; i >= 1; i--) b[cnt[a[i].key[p]]--] = a[i];
    memcpy(a, b, sizeof a);
}
void radix_sort(){
    for (int i = k; i >= 1; i--)
        counting_sort(i);
}
int main(){
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= k; j++) cin >> a[i].key[j];
    //sort(a + 1, a + 1 + n);  //自定义一个快排，模拟数据进行验证
    radix_sort();
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= k; j++) cout << a[i].key[j] << ' ';
        puts("");
    }
    return 0;
}
/*
3 3
33 44 55
11 22 33
33 55 66
3 3
33 11 22
11 22 33
88 22 10
*/

10 bucket sort(或 bin sort) 桶排 稳定

桶排序（Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。

桶排序假设输入数据服从均匀分布，平均情况下它的时间代价为。与计数排序类似，因为对输入数据做了某种假设，桶排序的速度也很快。具体来说，计数排序假设输入数据都属于一个小区间内的整数，而桶排序则假设输入是由一个过程产生，该过程将元素均匀、独立地分布在[0, 1)区间上。

桶排序将[0, 1)区间划分为 n 个相同大小的子区间，或称为桶。然后，将 n 个输入数分别放到各个桶中。因为输入数据是均匀、独立地分布在[0, 1)上，所以一般不会出现很多数落在同一个桶中的情况。为了得到输出结果，我们先对每个桶中的数进行排序，然后遍历每个桶，按照次序把各个桶中的元素取出来即可。

桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间。但桶排序并不是比较排序，他不受到下限的影响。

算法过程：

1. 设置一个定量的数组当作空桶子。
2. 寻访序列，并且把项目一个一个放到对应的桶子去。
3. 对每个不是空的桶子进行排序。
4. 从不是空的桶子里把项目再放回原来的序列中。

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

1. 在额外空间充足的情况下，尽量增大桶的数量
2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

1. 什么时候最快
当输入的数据可以均匀的分配到每一个桶中

2. 什么时候最慢
当输入的数据被分配到了同一个桶中

时间复杂度：，k表示数字大小的范围
空间复杂度：

如果每个桶只存放一种数字，则不需要对桶内数字进行排序，直接从小到大输出桶内的数字即可。这种排序算法的总时间复杂度为。这种特殊的桶排序算法被称为计数排序，它只适用于 k 不是特别大的情况。

元素分配到桶中

对桶中元素排序

// n个数，取值上限是w
// 每个桶中的排序，用的是插入排序
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
vector<int> bucket[N];
int n;                  // n个桶
int w;                  // max{a[i]}
int a[N];
void insertion_sort(vector<int>& A) {
    for (int i = 1; i < A.size(); ++i) {
        int key = A[i];
        int j = i - 1;
        while (j >= 0 && A[j] > key) {
            A[j + 1] = A[j];
            --j;
        }
        A[j + 1] = key;
    }
}
void bucket_sort() {
    int bucket_size = w / n + 1;
    for (int i = 0; i < n; ++i) {
        bucket[i].clear();
    }
    for (int i = 1; i <= n; ++i) {
        bucket[a[i] / bucket_size].push_back(a[i]);       //按规则落入桶中
    }
    for (int i = 0; i < n; i++) insertion_sort(bucket[i]);
    int p = 0;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < bucket[i].size(); ++j) {
            a[++p] = bucket[i][j];
        }
    }
}
int main(){
    cin >> n >> w;
    for (int i = 1; i <= n; i++) cin >> a[i];
    bucket_sort();
    for (int i = 1; i <= n; i++) cout << a[i] << ' ';
    puts("");
    return 0;
}

// 特殊的桶排序，计数排序
// 10 100
// 1 2 1 2 1 2 3 4 5 4
// 从小到大排序
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
int a[N], book[N];
int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        book[a[i]]++;
    }
    for (int j = 0; j <= m; j++)
        while (book[j]--) cout << j << ' ';
    puts("");
    return 0;
}

稳定性、比较次数 与 交换次数

https://blog.csdn.net/dreamer2020/article/details/8740244

首先说明稳定性是指相同元素在排序后相对位置保持不变。个人感觉稳定性的含义在于更广泛情形下，排序元素通常具有多个键值，即可以按照多个标准来排序。稳定性则保证了按照一个键排序的结果可以为第二个键所用。举个例子，对于学生的课程成绩，通常会和学号、姓名列在一起，先按照学生学号排序，然后再根据成绩从高到低，这样，相同分数的学生则是按照学号排名。

其次是关于比较次数和交换次数，通常用于算法效率分析。基于比较的排序算法其性能最好是nlog(n)。因而，不同的优化都是向这个边界靠近。且不同的算法也有不同的应用场景，不完全是看复杂度。

一、冒泡排序

冒泡排序的原理是将相邻元素比较，小的往左移动，大的往右，整个过程就像是水中气泡上浮。在相邻两个元素的比较中，如果相等，则没有必要交换。这一点，保证了冒泡排序的稳定性。无论相等的元素之前处于什么位置，在冒泡的效果下， 最终会相邻，只要相等元素不交换，就不会改变相对位置。所以冒泡排序是稳定的。

对于n个元素，相邻元素均要比较，共有(n-1)次。经过一回合冒泡过程后，最大元素沉淀到最右位置。第二回合，只剩下(n-1)个元素，只需要比较(n-2)次。依次类推，其他比较次数为(n-3),……,2,1. 所以总共比较次数为n(n-1)/2，而且是固定为这个数目。

至于交换次数，这个取决于初始序列的逆序数。对于数组A[1,…,n]，如果对于iA[j]，则称(A[i],A[j])是一个逆序对，序列中逆序对的个数称为逆序数。

冒泡排序每次交换，只改变了相邻两元素的位置，不影响和其他元素之间的逆序关系，因而，逆序数只减1。所以，冒泡排序交换次数等于初始序列的逆序数。

二、选择排序

选择排序的原理是每回合找出最小元素，然后交换到前面位置。

选择排序是不稳定的排序算法，不稳定主要产生于交换。交换过程可能改变相同元素的相对位置，举个例子，序列（5，8，5，1），最小数是1，第一次交换，得到（1，8，5，5），元素5相对位置已经发生变化。

下面是比较次数。对于n个元素的序列，找出最小元素需要比较(n-1)次。第一回合后，序列只剩下(n-1)个元素，下一次找最小元素还需要(n-2)次比较。最后直到2个元素需要比较1次。所以最后比较次数总共为(n-1)+(n-2)+…+1=n(n-1)/2，且固定不变。

每一回合最多交换一次，有(n-1)回合，所以最多交换次数为(n-1）。

三、插入排序

插入排序基本原理是假定前面i个元素已经排好，接下来将第(i+1)个元素插入到前面的序列中，保证有序。循环插入所有元素，即完成排序。

插入第(i+1)元素如果是从后往前扫描，寻找比其小的元素，这叫作直接插入排序。

如果是使用二分查找判断新元素位置，则叫作二分插入排序。两种插入排序都是稳定的。对于直接插入排序，新来元素位置是通过从后往前比较（寻找比其小或相等元素，假设是a[j]）来确定的，将新元素放在a[j]后即可，相等可以保证稳定性。对于二分插入排序，可以通过修改二分查找来保证稳定性，如下代码所示，但x[mid] == temp时，low指针右移，该操作可以保证相等元素不会被放到前面。

while (l <= r){
    mid = (l + r) >> 1;
    if (x[mid] <= mid) l = mid + 1;
    else r = mid - 1;
}

直接插入排序每回合的比较次数和元素移动次数等于其原始位置和插入位置之间的偏移。最好情况下（有序），需要比较(n-1)次，移动0次；最差情况下，需要比较1+2+…+(n-1)=n(n-1)/2次，移动n(n-1)/2次。

在程序实现上，通常会用一个临时变量(如temp）保存待插入元素，最后又将temp移动到相应位置上。从上面的分析可以发现，直接插入排序对于基本有序的初始序列，有较好效果，无论是比较次数还是移动次数，都很少。

二分插入排序仅仅是加快了查找这一过程，即减少了元素比较次数，对于m个有序的序列，二分查找最坏情况下比较次数为1+log(m)。因而，在插入排序中，元素比较次数为（n-1)+log(12…*(n-1)),在初始序列杂乱无章的情形下，其平均查找性能较好。[

](https://blog.csdn.net/dreamer2020/article/details/8740244)

四、归并排序

归并的基本思想是合并多路有序数组，通常我们考虑两路归并算法。

归并排序是稳定的，这是因为，在进行多路归并时，如果各个序列当前元素均相等，可以令排在前面的子序列的元素先处理，不会打乱相等元素的顺序。

考虑元素比较次数，两个长度分别为m和n的有序数组，每次比较处理一个元素，因而
合并的最多比较次数为(m+n-1)，最少比较次数为min(m,n)。

通常，对于两路归并，序列都是两两合并的。不妨假设元素个数为n=2^h，

第一次归并：合并两个长度为1的数组，总共有n/2个合并，比较次数为n/2。

第二次归并：合并两个长度为2的数组，最少比较次数是2，最多是3，总共有n/4次，比较次数是(2~3)n/4。

第三次归并：合并两个长度为4的数组，最少比较次数是4，最多是7，总共有n/8次合并，比较次数是(4~7)n/8。

第k次归并：合并两个长度为2^(k-1)的数组，最少比较次数是2^(k-1)，最多是2^k-1，总共合并n/(2^k)次，比较次数是2^(k-1)~(2^k-1)=n/2~n(1-1/2^k)。

按照这样的思路，可以估算比较次数
下界为n/2 h = n/2 log2(n) = nlog2(n)/2
上界为n[h-(1/2+1/4+1/8+…+1/2^h)]=n[h-(1-1/2^h)]=nlog2(n)-n+1。
综上所述，归并排序比较次数为nlog2(n)/2~nlog2(n)-n+1。

归并排序引入了一个与初始序列长度相同的数组来存储合并后的结果，因而不涉及交换。

五、快速排序

快速排序的基本思想是分治。

快排是不稳定的，关键在于划分过程。现有的几种划分过程，基本都是分两个指针从左右同时扫描，然后交换元素，交换过程很容易打乱元素位置。

元素比较次数，也就是其复杂性分析。

理想情况下，快速排序每次划分都将原始序列划分为两个等长的子序列。所以其比较次数为T(n)=2T(n/2)+n，所以其平均期望时间为nlog(n)。

在最坏情况下，即序列有序情形下，每次划分只能分出一个元素，因而总共需要(n-1)次划分，总的比较次数为(n-1)+(n-2)+…+1=n(n-1)/2，即退化为O(n^2)。

几种排序算法的比较

6分钟演示15种排序算法，（注意开音响，有声效）

1. 稳定性。插入、冒泡、二叉树、归并是稳定的；选择、希尔、快排、堆排是不稳定的。（有跨度的交换，会导致不稳定）
2. 时间复杂度。O(n^2)，插入、冒泡、选择；O(nlogn)，快排、堆排，归并；O(n)，桶排序。（最好的情况下，插入、冒泡最快。平均情况下，快排最快。最坏情况下，堆排、归并最快）
3. 辅助空间。桶排、归并，需要O(n)辅助空间。快排，需要O(logn)辅助空间，最坏需要O(n)。其他排序算法需要O(1)
4. 插入、冒泡的速度较慢，但局部/整体有序的情况下，却很快，此时快速排序反而变慢，变成O(n^2)
5. n 较小时，对稳定性不作要求，用选择排序；稳定性有要求，用插入或冒泡排序
6. 排序的数字范围是一个有限的范围，对稳定性没有要求，用桶排，主要考虑开数组不能 SE
7. n 较大时，元素随机，对稳定性没有要求，用快速排序
8. n 较大时，元素有序，对稳定性没有要求，用堆排序（用 priority_queue 实现）
9. STL 的 sort 不是纯快排，是快排和插入的结合。

上图中，希尔排序的时间复杂度有异议

STL: sorting in C++

// sort()，一统天下
vector<int> v = {4,2,5,3,5,8,3};
sort(v.begin(),v.end());
sort(v.rbegin(),v.rend());
int n = 7; // array size
int a[] = {4,2,5,3,5,8,3};
sort(a,a+n);
string s = "monkey";
sort(s.begin(), s.end());
vector<pair<int,int>> v;
v.push_back({1,5});
v.push_back({2,3});
v.push_back({1,2});
sort(v.begin(), v.end());

User-defined structs自定义结构体排序

// 使用重载小于号的方法
struct node{
    int x, y;
    bool operator< (const node& W)const
    {
        if (x != W.x) return x < W.x;
        else return y < W.y;
    }
}a[N];
// 调用
sort(a, a + n);

// 使用cmp函数的方法
bool comp(string a, string b) {
    if (a.size() != b.size()) return a.size() < b.size();
    return a < b;
}
// 调用，vector里存的是string
sort(v.begin(), v.end(), comp);

中位数和顺序统计量

在一个由 n 个元素组成的集合中，第 i 个顺序统计量(order statistic)是该集合中第 i 小的元素。一个中位数(median)是它所属集合的“中点元素”。当n为奇数时，中位数是唯一的，位于 i = (n + 1) / 2。当n为偶数时，存在两个中位数，分别位于 i = n / 2， i = n / 2 + 1 处。一般，中位数都是指下中位数。

打擂台

同时找到最小值和最大值

在 n 个元素中，同时找到最小值和最大值的方法是显然的：只要分别独立地找出最小值和最大值，这各需要 n-1 次比较，共需 2n - 2 次比较。

事实上，我们只需要最多次比较就可以同时找到最小值和最大值。首先，我们将一对输入元素相互进行比较，然后把较小的与当前最小值比较，把较大的与当前最大值进行比较。这样，每对元素共需3次比较。

如何设定已知的最小值和最大值的初始值依赖于 n 是奇数还是偶数。如果 n 是奇数，我们就将最小值和最大值的初值都设为第一个元素的值，然后成对地处理余下的元素。如果 n 是偶数，就对前两个元素做一次比较，以决定最小值和最大值的初值，然后与 n 是技术的情形式样，成对地处理余下的元素。

下面来分析一下总的比较次数。如果 n 是奇数，那么总共进行 次比较。如果 n 是偶数，则是先进行一次初始比较，然后进行 次比较，总共 次比较。因此，不管是哪一种情况，总的比较次数至多是

例题：NOIP2018普及组初赛第9题

《算法导论》练习9. 1-2 提示：考虑有多少个数成为最大值或最小值的潜在可能，然后分析一下每一次比较会如何影响这些计数。

《一本通》题目

【例2.2】车厢重组

//冒泡

【例2.5】求逆序对

//归并

谁考了第k名

//结构体排序

奇数单增序列

//初次使用sort

成绩排序

//结构体排序

奖学金

//结构体排序，[NOIP2007 普及组\] 奖学金

分数线划定

//结构体排序，模拟，[NOIP2009 普及组] 分数线划定

整数奇偶排序

//sort，reverse

合影效果

//男女分开，分别排序

病人排队

//结构体排序

明明的随机数

//桶排，[NOIP2006 普及组] 明明的随机数

单词排序

//初次接触 map<string, int>

出现次数超过一半的数

//稍微思考一下性质

统计字符数

//桶排

其他题目

[NOIP2011 普及组] 瑞士轮

//

P1626 象棋比赛

//桶排

P1716 双调序列

//

P3955 [NOIP2017 普及组] 图书管理员

//

P4432 [COCI2017-2018#2] ZigZag

//

P2676 [USACO07DEC]Bookshelf B

//sortings + greedy

P4379 [USACO18OPEN]Lemonade Line S

//sortings + greedy

P1056 [NOIP2008 普及组] 排座椅

//sortings + greedy

P1097 [NOIP2007 提高组] 统计数字

//sorting + binary search