排序算法（5）--线性时间排序（计数、基数、桶）

    前面的文章里面介绍了几种常用排序算法，通过算法实现可以看出，都是基于比较的方式进行排序，称为比较排序；而且它们的时间下界是O(n lgn)。下面的描述中将介绍三种线性时间排序算法：计数排序、基数排序、桶排序。时间下界O(n lgn)对于这三种排序算法是不适用的，这三种排序算法的下界是O(n)。
一、计数排序
   原理：计数排序的基本思想是：对于每一个元素x，确定了小于等于x的元素的个数，就可以将x放到相应的位置上。主要过程是：
      假设k是待排序数组的最大值。
      1、使用辅助数组c（大小是k），记录[0...k]在数组a中出现的次数。
      2、依次计算数组c，使c[i]表示数组a中不大于i的元素的个数。
      3、从后往前遍历数组a，根据数组c中的个数将a的元素放到辅助数组b（大小等于a）中。
      4、把有序数组b复制到a中。
   代码实现：

/************************************************************************/
/* 计数排序
    a     输入待排序数组，保存排序后数组
    size  待排序数组长度
    k     待排序数组元素最大值
*/
/************************************************************************/
void CountingSort(int *a, int size, int k)
{
    int i = 0;
    int *b = NULL; // 排序结果
    int *c = NULL; // 待排序数组中 0-k的计数和

    c = (int *)malloc(sizeof(int) * (k + 1));
    b = (int *)malloc(sizeof(int) * size);
    memset(c, 0, sizeof(int) * (k + 1));
    memset(b, 0, sizeof(int) * size);

    // 计算排序数组中等于c[i]的个数
    for(i = 0; i < size; i++)
        (*(c + a[i]))++;

    // 计算排序数组中小于等于c[i]的个数
    for(i = 1; i <= k; i++)
        c[i] += c[i - 1];

    // 从后往前遍历a数组，将a数组元素放到b数组的相应位置
    for(i = size - 1; i >= 0; i--)
    {
        b[*(c + a[i]) - 1] = a[i];
        (*(c + a[i]))--;
    }

    // 将b数组赋给a数组
    for(i = 0; i < size; i++)
        a[i] = b[i];

    free(c);
    free(b);
}

    性能分析：从代码可以看出，算法的总时间T = 第一个循环n + 第二个循环k + 第三个循环n + 第四个循环n = 3n + k，时间复杂度是O(n + k)。所以计数排序的时间下界是O(n)，在最坏情况下也是不变的。此外计数排序需要n+k的辅助空间，这个辅助空间是比较大的。计数排序是稳定的排序，它不会改变相同元素的顺序，这就是为什么从后往前遍历a数组的原因；而且计数排序是基数排序的基础，这种稳定性也是基数排序需要的。

二、基数排序
    原理：在计数排序中，当k值很大时如（{12,1134,99999}），这时需要的辅助空间和时间都会很大，其效率并不比比较排序高。所以基数排序弥补了计数排序的缺陷，基数排序的基本原理是：将数组元素分解成个位（第一位）、十位（第二位）。。。。。。，然后从第一位开始进行计数排序，直到最高位结束，排序完成。由于分解出来的每位数据的最大值是9，因此计数排序的k值为9。
   代码实现：

/************************************************************************/
/* 获取整数 第loc位的值 */
/************************************************************************/
int digit(int num, int loc)
{
    return (num / (int)pow(10, loc - 1)) % 10;
}
/************************************************************************/
/* 基数排序中的计数排序
    a  排序数组
    n  数组大小
    k  记录最大值
    d  按数组元素的第 d 位排序
*/
/************************************************************************/
void CountSort(int *a, int n, int k, int d)
{
    int i = 0;
    int *c = NULL;
    int *b = NULL;

    c = (int *)malloc(sizeof(int) * (k + 1));
    b = (int *)malloc(sizeof(int) * n);
    memset(c, 0, sizeof(int) * (k + 1));
    memset(b, 0, sizeof(int) * n);

    // 计算a[i]中第d位记录的个数
    for(i = 0; i < n; i++)
        (*(c + digit(a[i], d)))++;

    // 计算小于等于a[i]中第d为的记录个数
    for(i = 1; i <= k; i++)
        c[i] += c[i - 1];

    // 从后往前遍历a数组，将元素放到b的相应位置
    for(i = n - 1; i >= 0; i--)
    {
        *(b + *(c + digit(a[i], d)) - 1)= a[i];
        (*(c + digit(a[i], d)))--;
    }

    // 将b复制到a
    for(i = 0; i < n; i++)
        a[i] = b[i];

    free(c);
    free(b);
}
/************************************************************************/
/* 基数排序
    a     待排序数组
    size  数组大小
    d     数组元素的位数
*/
/************************************************************************/
void RadixSort(int *a, int size, int d)
{
    int i;
    for(i = 1; i <= d; i++)
    {
        CountSort(a, size, 9, i);
    }
}

    性能分析：基数排序时间T=d*(3n + k),其中d是记录值的位数，(3n + k)是每一趟计数排序时间，我们知道，k不超过9，d的值一般也很小，k、d都可以看成是一个很小的常数，所以时间复杂度O（n）。最坏最佳情况并不改变时间复杂度。从这里可以看出计数排序的稳定性直接影响了基数排序的结果，基数排序是稳定的。基数排序需要一部分辅助空间，所以在内存紧张的系统中，原地排序算法可能是更好的选择。

三、桶排序
    原理：桶排序与计数排序类似，都是做了一种假设。桶排序是假设待排序序列是随机产生，并且均匀的分布在[0,1)的区间。其思想是将区间[0,1)划分成那个区间（或称桶），将n个序列元素分不到桶中。若多个元素分不到同一个桶中，则需要进行桶内排序。最后将各桶内数据依次输出得到有序序列。
    代码实现：下面的以小数点后第一位作为区间划分的标准，共10个区间。

// 链表节点结构体
typedef struct Node
{
    double key;
    struct Node *next;
}Node;
/************************************************************************/
/* 桶排序 */
/************************************************************************/
void BucketSort(double *a, int n)
{
    Node *List[10] = {NULL}; // 申请10个桶
    int i = 0, j = 0;
    Node *node = NULL;
    Node *p = NULL;
    Node *q = NULL;

    // 循环待排序数组，放到桶的相应位置
    for(i = 0; i < n; i++)
    {
        node = calloc(1, sizeof(Node));
        node->key = a[i];
        node->next = NULL;

        // 桶中没有元素
        q = p = List[(int)(a[i] * 10)];
        if(p == NULL)
        {
            List[(int)(a[i] * 10)] = node;
            continue;
        }

        // 桶中有元素则插入到相应位置
        while(p)
        {
            if(a[i] < p->key)
            {
                q->next = node;
                node->next = p;
                break;
            }

            q = p;
            p = p->next;
        }

        if(p == NULL)
        {
            q->next = node;
        }
    }

    // 将桶中元素输出到a中
    for(i = 0; i < 10; i++)
    {
        p = List[i];
        while(p)
        {
            a[j++] = p->key;
            q = p;
            p = p->next;
            free(q);
        }
    }

}

    性能分析：在最好情况下，当记录在桶中分布均匀时，即每个桶只有一个元素，此时时间复杂度O（n）。因此桶排序适合对很少重复的记录排序。辅助空间n。而且桶排序是稳定的排序，实现比较复杂。
    从桶排序的辅助空间可以看出，这是类似于hash表的数据结构，桶内元素的插入和遍历是线性顺序遍历的；所以当桶内元素过多时插入的效率是很低的。在tomcat早期版本中hash表的相同元素的遍历采用了线性查找、插入算法，导致了旧版本的tomcat很容易造成ddos攻击，这点需要注意。在这个例子中采用了小数点后一位作为桶的划分标准，在实际应用中可以采用其他粒度作为桶划分的标准，如小数点2位、hash值等等。