数据结构篇笔记-9-桶&计数&基数排序

复习数据结构笔记之桶&计数&基数排序

数据结构篇-9-线性排序

线性排序算法介绍

1.线性排序算法包括桶排序、计数排序、基数排序。
2.线性排序算法的时间复杂度为O(n)。
3.此3种排序算法都不涉及元素之间的比较操作，是非基于比较的排序算法。
4.对排序数据的要求很苛刻，重点掌握此3种排序算法的适用场景。

桶排序（Bucket sort）

1.算法原理：
1）将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行快速排序或归并排序。
2）桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
2.使用条件
1）要排序的数据需要很容易就能划分成m个桶，并且桶与桶之间有着天然的大小顺序。
2）数据在各个桶之间分布是均匀的。
3.适用场景
1）桶排序比较适合用在外部排序中。
2）外部排序就是数据存储在外部磁盘且数据量大，但内存有限无法将整个数据全部加载到内存中。
4.算法分析
1)时间复杂度: 最好o(n), 最坏o(nlogn), 平均o(n)，一般桶分的越细越多复杂度就会最好。
2)内存消耗: o(n)
3)稳定性: 取决于每个桶的排序方式，快排就不稳定，归并就稳定。
5.应用案例
1）需求描述：
有10GB的订单数据，需按订单金额（假设金额都是正整数）进行排序
但内存有限，仅几百MB
2）解决思路：
扫描一遍文件，看订单金额所处数据范围，比如1元-10万元，那么就分100个桶。
第一个桶存储金额1-1000元之内的订单，第二个桶存1001-2000元之内的订单，依次类推。
每个桶对应一个文件，并按照金额范围的大小顺序编号命名（00，01，02，…，99）。
将100个小文件依次放入内存并用快排排序。
所有文件排好序后，只需按照文件编号从小到大依次读取每个小文件并写到大文件中即可。
3）注意点：若单个文件无法全部载入内存，则针对该文件继续按照前面的思路进行处理即可。

计数排序（Counting sort）

1.算法原理
1）计数其实就是桶排序的一种特殊情况。即每个下标代表一个数据范围，其值就是这个数据的个数。
2）当要排序的n个数据所处范围并不大时，比如最大值为k，则分成k个桶.
3）每个桶内的数据值都是相同的，就省掉了桶内排序的时间。
2.代码实现(见文末)
案例分析：
假设只有8个考生分数在0-5分之间，成绩存于数组A[8] = [2，5，3，0，2，3，0，3]。
使用大小为6的数组C[6]表示桶，下标对应分数，即0，1，2，3，4，5。
C[6]存储的是考生人数，只需遍历一边考生分数，就可以得到C[6] = [2，0，2，3，0，1]。
对C[6]数组顺序求和则C[6]=[2，2，4，7，7，8]，c[k]存储的是小于等于分数k的考生个数。
数组R[8] = [0，0，2，2，3，3，3，5]存储考生名次。那么如何得到R[8]的呢？
从后到前依次扫描数组A，比如扫描到3时，可以从数组C中取出下标为3的值7，也就是说，到目前为止，包括自己在内，分数小于等于3的考生有7个，也就是说3是数组R的第7个元素（也就是数组R中下标为6的位置）。当3放入数组R后，小于等于3的元素就剩下6个了，相应的C[3]要减1变成6。
以此类推，当扫描到第二个分数为3的考生时，就会把它放入数组R中第6个元素的位置（也就是下标为5的位置）。当扫描完数组A后，数组R内的数据就是按照分数从小到大排列的了。
执行步骤:

• 1).找出需要排序的数组的最大值
• 2).声明一个新的数组c，用于计数数组使用。此时申请的数组大小为第一步得出的最大值+1
• 3).遍历原始数组，将所在的计数数组的对应的下标的值进行累加1
• 4).遍历计数数组，将数组从1开始往后累计，
• 5).创建跟原始数组大小空间的临时数组
• 6).遍历原始数组，根据原始数组值找到对应计数的数组的所对应的下标，并且减一（数组从0开始）
• 7).将临时数组拷贝到原始数组
  总结：此处使用创建2次原始额外空间，所以计数数组，使用场景只能是排序的数组原始范围不大，但是数据量非常大的场景，使用场景非常有限

3.使用条件
1）只能用在数据范围不大的场景中，若数据范围k比要排序的数据n大很多，就不适合用计数排序；
2）计数排序只能给非负整数排序，其他类型需要在不改变相对大小情况下，转换为非负整数；
3）比如如果考试成绩精确到小数后一位，就需要将所有分数乘以10，转换为整数。
4.算法分析
1)时间复杂度: 都是o(n)
2)内存消耗: o(n)
3)稳定性: 稳定，只要整理最后结果时从后开始遍历即可。

基数排序（Radix sort）

1.算法原理
对数据的每一位进行桶排序或计数排序，对每位排序后结果就是有序的。
2.案例说明（以排序10万个手机号为例来说明）
1）比较两个手机号码a，b的大小，如果在前面几位中a已经比b大了，那后面几位就不用看了。
2）借助稳定排序算法的思想，可以先按照最后一位来排序手机号码，然后再按照倒数第二位来重新排序，以此类推，最后按照第一个位重新排序。
3）经过11次排序后，手机号码就变为有序的了。
4）每次排序有序数据范围较小，可以使用桶排序或计数排序来完成。
2.使用条件
1）要求数据可以分割独立的“位”来比较；
2）位之间由递进关系，如果a数据的高位比b数据大，那么剩下的地位就不用比较了；
3）每一位的数据范围不能太大，要可以用线性排序，否则基数排序的时间复杂度无法做到O(n)。
4.算法分析
1）时间复杂度: 最好o(n), 最坏o(nlogn), 平均o(n)
2）内存消耗: o(n)
3）稳定性: 稳定。否则就排不成的。

思考

1.如何根据年龄给100万用户数据排序？
答：我们假设年龄的范围最小 1 岁，最大不超过 120 岁。我们可以遍历这 100 万用户，根据年龄将其划分到这 120个桶里，然后依次顺序遍历这 120 个桶中的元素。这样就得到了按照年龄排序的 100 万用户数据。

2.对D，a，F，B，c，A，z这几个字符串进行排序，要求将其中所有小写字母都排在大写字母前面，但是小写字母内部和大写字母内部不要求有序。比如经过排序后为a，c，z，D，F，B，A，这个如何实现呢？如果字符串中处理大小写，还有数字，将数字放在最前面，又该如何解决呢？
答：用两个指针a、b：a指针从头开始往后遍历，遇到大写字母就停下，b从后往前遍历，遇到小写字母就停下，交换a、b指针对应的元素；重复如上过程，直到a、b指针相交。
对于小写字母放前面，数字放中间，大写字母放后面，可以先将数据分为小写字母和非小写字母两大类，进行如上交换后再在非小写字母区间内分为数字和大写字母做同样处理。

附：计数排序代码实现(java版)

public class CountingSort {
    /**
     * 计数排序
     *
     * @param arr 要排序的数组大小
     * @param n 数组元素个数
     */
    public static void sort(int[] arr, int n) {
        if (n <= 1) {
            return;
        }

        //默认数组最大的元素为数组第一个元素
        int max = arr[0];
        //遍历数组的所有的元素，找到最大的元素
        for (int i = 1; i < n; i++) {
            //若后面的元素大于指定的数组元素，则把元素进行交换
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        //申请一个计数数组，下标从0~max。
        int[] c = new int[max + 1];

        //遍历数组，将每个元素的个数放入到计数数组中，比如分数为0的元素，在c[0]就累加1，依次类推
        for (int i = 0; i < n; i++) {
            c[arr[i]]++;
        }

        //开始重新整理c[]数组，将c[]数组顺序求和，比如分数0的个数1，分数为1的个数为3。那么重新整理后，分数<=0的为1，分数<=1人数诶1+3=4个，因为包含了<=0的个数，依次类推
        //所以终止条件为i<=max
        for (int i = 1; i <= max; i++) {
            c[i] = c[i] + c[i - 1];
        }

        //这时候开始进行排序，创建一个跟要排序的数组一样大小的数据空间
        int[] temp = new int[n];

        //开始循环需要排序的数据
        for (int i = 0; i < n; i++) {
            //计算出需要往temp临时数组哪个索引位置存放arr[i]的值。
            //根据原始数组的值找到计数数组的对应值的计数个数，得到c[arr[i]]的值，也就是temp数组从0开始，所以需要减一
            int index = c[arr[i]] - 1;
            temp[index] = arr[i];
            //每次循环，计数数组的元素值减一，因为数组放到了temp数组中
            c[arr[i]]--;
        }

        //重新赋值
        for (int i = 0; i < n; i++) {
            arr[i] = temp[i];
        }
    }
}