桶排序

桶排序的核心思路

• 桶排序的核心处理思想是先定义几个有序的桶，将要排序的数组按照桶划分的值的范围分到这几个桶中，对每个桶的数据单独进行排序。再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的。

桶排序的操作流程

• 比如要排序的数据有n个，我们划分出m个桶，将数据按照划分的值范围分别划分到对应桶中。然后单独对桶内的数据进行排序，可以采用任何排序算法，总之就是将桶内数据排好序。
• 排好了各个桶内的数据之后。再按顺序依次将桶内的数据取出，合并成一个整体，就排好序了。

桶排序的相关

• 桶排序比较适合用在外部排序中。即数组存储在外部磁盘，数据量比较大而内存有限，无法将全部数据加载到内存中处理。
• 桶排序的平均时间复杂度为O(n+k)，k为数据范围。
• 桶排序不是原地排序，是否是稳定排序就得看桶内排序时使用的排序算法是否是稳定排序算法了。
• 桶排序对排序数据有一定的特殊要求。待排数据很容易被划分成m个桶，并且桶和桶之间有着天然的大小顺序，这样每个桶内的数据排序完成之后，桶与桶之间的数据不需要再次进行排序。

计数排序

计数排序的核心思路

• 计数排序是桶排序的一种特殊情况。当要排序的n个数据所处的范围并不大的时候，如最大值为k，则可以将数据划分为k个桶，每个桶中的数据是相等的，省掉了桶内数据排序的时间。

计数排序的操作流程

• 假设一次考试满分为100分。我们可以将所有考生的考试成绩划分为101个桶，每个桶依次表示0到100分。然后遍历数据，将对应分数的考生直接划分到对应分数的桶中。这样每个桶中所有的考生的分数都是相同的，就不再需要排序了。如果需要计算考生的名次或者分数段内考生的数量，就直接对桶的数据量进行运算就可以得出了。
• 如果我们要对这些考试数据进行排序，获得考生再有序数组中的具体位置。所有考生数据的一个数组为c[n],则我们再创建一个数组a[101],其中数组的下标对应的是分数，数组存储的数据对应的是考了这个分数的学生数量。
• 用一个比较巧妙的处理思路：对数组a[101]顺序累加求和。即a[0]=a[0],a[1]=a[0]+a[1],a[2]=a[1]+a[2],类似这种操作。做完这个操作，数组a就改变了表示的含义。此时数组a的下标仍然是表示的分数，而数组a装的数据则表示的是所有考了小于等于以当前下标为分数的考生个数。
• 然后我们创建一个和c[n]一样大小的数组temp,用于存放排好序的数据。对c[n]所有学生数据的数组从后向前遍历，遍历到c[n-1],取出来当前考生的分数是score，这个分数对应的就是a[101]数组的下表，取出a[score]，此时就取出了考了小于等于这个分数的学生个数k。此时我们就可以将这个学生放入到temp[k-1]的位置。此时我们就排好了这个学生的位置，然后将a[score]=k-1,代表剩余的未排序的学生数组中还剩下k-1个学生分数小于等于score分。
• 注意：这里为什么要从后向前遍历学生数组c[n]，是因为后续插入到temp中时也是在这个分数区间内插入到的区间末尾。这样才是稳定排序。

计数排序的相关

• 计数排序对数据有限制。1.数据范围不能太大，太大了如果数据范围k比需要排序的数据个数n还要大很多，那就不适用计数排序了。2.计数排序只能给非负整数排序，如果是有小数点，则需要都乘到整数位。如果存在负数，则需要都加到正数才可。因为计数排序不是对数据的比较，而是对数据的数量的计算之后对数据的排序，用到了数据下标的方法。
• 计数排序不是原地排序，是稳定排序。
• 计数排序的平均时间复杂度是O(n)。

基数排序

基数排序的核心思想

• 基数排序的核心思想就是将数据划分成高低位，然后再借助桶排序或者计数排序去完成每一位的排序工作。

基数排序的操作流程

• 排序手机号码，可以划分成每一位去排序。
• 排序英文单词，可以利用用0补全，再分别取每一位字母去对比排序。

基数排序的相关

• 基数排序对数据有一定的要求，要求数据必须可以划分成高低位，并且位之间是有递进关系的。
• 每一位的数据范围不能太大，因为基数排序需要借助桶排序或者计数排序来完成每一位的排序工作。
• 基数排序的平均时间复杂度是O(dn)，d为数据维度。