第12讲 桶排序、基数排序、外部排序

完整代码

桶排序（计数排序）

1. 简介：就是开对应元素个桶，每个桶里面存储小于该元素以及等于该元素但在该元素左边（这个考虑的是元素相等的情况和稳定性）的个数，然后排序的时候，元素的最终位置就是桶里面存储的元素个数，我们从后枚举（保证稳定性）。

2. 时间复杂度：（n元素数量 m数值的大小）

3. 最好情况：O(n+m）。

4. 平均情况：O(n+m）。

5. 最坏情况：O(n+m）。

6. 空间复杂度：O(n+m）。

7. 稳定。

/*桶排序：如果把上面N（桶的大小）开的更大一点数据会过的更多。但是数值过大
就不太适用*/
void bucket_sort(){
    //统计每个桶里面应该有多少元素，即小于和等于在该元素左边的个数
    for(int i = 0 ;i < n ; i++)   s[q[i]]++;
    //求所有桶的前缀和（循环到数值的最大范围）
    for(int i = 0 ; i < N ; i++)  s[i] += s[i - 1];
    /*把每个元素放到对应的位置上，一定要从后往前放（稳定），先放到
    辅助数组里面，防止产生读写的冲突*/
    for(int i = n - 1 ; i >= 0 ; i --)  w[-- s[q[i]]] = q[i];
    //排完序之后，把序列复制到原数组中去
    for(int i = 0 ; i <  n ; i++)  q[i] = w[i];

}

基数排序

1. 简介：桶排序的扩展。简单来说，就是把一组序列中位数最多的作为基，每次比较从个位排（只看个位上的大小排成一个序列），然后十位、百位，直到排到位数最多的那一位，最终有序。
2. 时间复杂度：
3. 最好情况：O(d(n+r)）。
4. 平均情况：O(d(n+r)）。
5. 最坏情况：O(d(n+r)）。
6. 空间复杂度：O(n+r）。
7. 稳定。

/*基数排序：d关键字的数量，也就是最多有多少位. r进位制的基数：如2进制，十进制等等*/
void radix_sort( int d , int r){
    //radix进制,从个位开始
    int radix = 1;
    //枚举所有的关键字
    for(int i = 1 ; i <= d ; i ++){
        //清空所有的桶
        for(int j = 0 ; j < r ; j++ ) s[j] = 0 ;
        //统计每个桶里面有多少个元素,q[j] / radix % r:获得对应位上的数，计数
        for(int j = 0 ; j < n ; j++) s[q[j] / radix % r] ++;
        //求前缀和
        for(int j = 1 ; j < r ; j++) s[j] += s[j - 1];
        //按照当前位数上的大小从后往前排序
        for(int j = n -1 ; j >= 0 ;j--) w[--s[q[j] / radix % r]] = q[j];
        //赋值回原数组
        for(int j = 0 ; j < n ; j++) q[j] = w[j];
        //做完当前个位后，往十位、百位上继续，直到最大位数都排完
        radix *= r;
    }
}

外部排序

简介：设计到外存上的数据进行排序，无法在内存中直接进行的。（从外存上往内存读写数据很慢）

1. 步骤：

2. 预处理一些数据（置换选择排序）

3. 归并成有序的一段

4. 置换选择排序：生成若干个顺序段

5. （k路）归并排序：将之前生成m个顺序段归并成一个顺序段（实质是huffman问题，可以用这个来优化。归并的过程可以用败者树来进行实现）

6. 胜者树：选择相邻两个元素，小的胜出作为他们的父结点，用的是索引，依次这样比较下去直到根结束。

败者树：选择相邻两个元素，大的失败最为两个的父结点，小的胜者作为父结点的父结点，按照这个规律依次构建下去，最终会多一个根结点也就是胜者。更新结点时，相比较胜者树会少一半的访问结点。

1. 各种内部排序算法的比较

考题：

2011-10、2011-11、2012-10、2012-11、2013-11、2014-10、2014-11、2015-9、2015-10、2015-11、2016-11、2016-43、2017-10、2017-11、2018-10、2018-11、2019-7、2019-10、2019-11、2020-9、2020-1

总结：

1. 所有的 内部排序一般都是宜采用顺序存储比较好
2. 大根堆元素调整的时候比较次数，比较失败的也算一次。
3. 每趟排序至少能确定一个元素的最终位置的排序有：简单选择排序、快速排序（考研教材上的可以确定，但是y总的代码不能保证，以考研为准）、堆排序（堆排的 一趟指的是每次将最小或最大的放在堆顶）、
4. 折半插入排序比直接插入排序优化的是比较次数
5. 基数排序如果没有说明就是按照十进制来排，
6. 判断希尔排序的增量，我们可以不用模拟整个过程。把每个选项的增量带入题中看哪1个是升序哪1个降序（看这一小段的），就可以推出这个希尔的增量是多少。因为正确答案唯一，其余三个肯定会跟正确答案逆序。
7. 快速排序的第 i 趟的序列，判断依据： 至少有 i 个元素会出现在正确的位置上（判断一个元素是不是在最终位置上，可以看左边的元素是不是都比他小右边的都比他大，不用）。
8. 希尔排序和堆排序采用链式存储效率会变低，因为他们要用到随机索引。（堆排序排序时采用数组模拟的，不是那种树结构的）