《算法导论》学习总结 — 第八章(2) 计数排序 && 基数排序 && 桶排序

《算法导论》学习总结 — 8.第八章(2) 计数排序 && 基数排序 && 桶排序

1)稳定的：如果存在多个具有相同排序码的记录，经过排序后，这些记录的相对次序仍然保持不变，则这种排序算法称为稳定的。
插入排序、冒泡排序、归并排序、分配排序（桶式、基数）都是稳定的排序算法。
2）不稳定的：否则称为不稳定的。
直接选择排序、堆排序、shell排序、快速排序都是不稳定的排序算法。
一个各种排序算法演示网站:http://www.sorting-algorithms.com/

计数排序
元素必须是大于等于0，同时不能太大，否则数组res会暴栈
特点是：非常稳定
作用：经常用作基数排序算法的一个子过程

void CountingSort(int kp[], int res[], int size) {

    memset(Hash, 0, sizeof(*Hash) * size);

    for (int i = 1; i <= length; i++) {

        Hash[kp[i]]++;

    }

    //此时Hash[]包含等于i的元素个数

    for (int i = 1; i <= size; i++) {

        Hash[i] += Hash[i - 1];

    }

    //此时Hash[]包含小于等于i的元素个数

    for (int i = length; i >= 1; i--) {

        res[Hash[kp[i]]] = kp[i];

        Hash[kp[i]]--;

    }

}

基数排序
http://massivealgorithms.blogspot.com/2014/07/radix-sort-geeksforgeeks.html

http://massivealgorithms.blogspot.com/2014/08/sort-n-numbers-in-range-from-0-to-n2-1.html

首先要搞懂MSD(Most significant digital， 最高位优先级)和LSD(Least significant digital， 最低位优先级)。例如: 纸牌排序问题，要求结果符合面值，花色从小到大排序

K0 ： 花色 （高优先级) ；

K1 ： 面值 （低优先级)；

MSD：先按k0排序，得到四堆牌，每堆包含属于同一花色的所有纸牌然后分别对每一堆按照面值排序，然后四堆牌叠到一起就是最后结果

LSD：先按k1排序，分成13堆，每堆4种花色，面值相同,然后叠为一堆，然后按k0排序，分为4堆，然后叠为一堆，就是结果。

这期间的排序使用的是计数排序……

可以发现MSD每次都是单独子堆分别排序，而LSD每次都是整堆排序，所以LSD比MSD简单，花费开销要小，所以基数排序通常使用LSD，此处的基数，代表用基数r可以分解为多少个个位数。

r = 10, 基数为10, 按10进制分解结果

r = 2， 基数为2, 按2进制分解结果

排序过程即：先按个位数排序，然后按十位数排序，然后百位数排序，类推……

严蔚敏版《数据结构》中基数排序演示

桶排序
http://massivealgorithms.blogspot.com/2014/06/bucket-sort.html