时间逼近线性的3种排序

1、计数排序

(1)描述
之前的排序都是基于元素之间的比较来进行的，而计数排序不是，它以空间换取时间，当待排序数据是一定范围内的整数时，设最大值减最小值为k，则时间复杂度是Ο(n+k)，有可能比任何基于比较的算法都快，当k的值较大时，效率降低。

定义一个数组，先统计出每个元素的个数，进而统计出比每个元素小的元素有多少个，这样就可以直接把每个元素放到对应的位置上。

局限性也比较明显，
1是当元素分布范围零散时，会浪费很多空间。
2是只能用于整型数据的排序。

(2)实现

void counting_sort(int data[], int n)
{
    int max = data[0], min = data[0]; // 假设排序数据都是整数
    for (int i = 1; i < n; ++i)
    {
        max = data[i] > max ? data[i] : max;
        min = data[i] < min ? data[i] : min;
    }

    int *count = (int *)malloc((max - min + 1) * sizeof(int));
    memset(count, 0, (max - min + 1) * sizeof(int));
    int *result = (int *)malloc(n * sizeof(int));
    memset(result, 0, n * sizeof(int));
    
    for (int i = 0; i < n; i++)
    {
        count[data[i] - min]++;
    }
    for (int i = 1; i < max - min + 1; i++)
    {
        count[i] = count[i] + count[i - 1];
    }
    for (int i = 0; i < n; i++)
    {
        count[data[i] - min]--;
        result[count[data[i] - min]] = data[i];
    }
    for (int i = 0; i < n; i++)
    {
        data[i] = result[i];
    }
    free(result);
    free(count);
}

代码链接

(3) 时间复杂度 O(n+k)
当k=0时，最好时间复杂度 O(n)

而k还可能是n的平方甚至立方，所以最坏时间复杂度就没有上限了。

(4)空间复杂度 O(k)

(5)稳定性：稳定

2、桶排序

(1)描述
采用分治思想，把待排序数据根据某种映射函数，分到有限数量个桶中。每个桶内部再各自排序，最后依次把各个桶中的记录列出来记得到有序序列。
显然，尽量减少桶内数据的数量是提高效率的唯一办法。第一是选择一个合适的映射函数使得待排序的数据均匀分布在各个桶内，第二是尽可能的增加桶的数量。

(2)实现
这里用链表来实现，其中参数 n 是数据个数，bucket_size 是 桶的个数。

typedef struct node
{
    int value;
    struct node* next;
}Node;

void bucket_sort(int data[], int n, int bucket_size)
{
    // 初始化桶
    Node **bucket_list = (Node **)malloc(bucket_size * sizeof(Node*));
    for (int i = 0; i < bucket_size; ++i)
    {
        bucket_list[i] = (Node *)malloc(sizeof(Node));
        bucket_list[i]->value = 0;
        bucket_list[i]->next = NULL;
    }
    // 把每个数据分到对应的桶中
    for (int i = 0; i < n; ++i)
    {
        Node *x = (Node *)malloc(sizeof(Node));
        x->value = data[i];
        x->next = NULL;
        
        int index = data[i] / bucket_size;
        Node *p = bucket_list[index];
        if (0 == p->value) // 头结点的value保存数据的个数
        {
            p->next = x;
            ++(p->value);
        }
        else
        {
            while (p->next && p->next->value <= x->value)
            {
                p = p->next;
            }
            x->next = p->next;
            p->next = x;
            ++(bucket_list[index]->value);
        }
    }

    // 把桶里的数据复制回原来位置,并释放内存
    Node *p = NULL;
    Node *tmp = NULL;
    int j = 0;
    for (int i = 0; i < bucket_size; ++i)
    {
        for (p = bucket_list[i]->next; NULL != p; p = tmp)
        {
            data[j++] = p->value;
            tmp = p->next;
            free(p);
        }
        free(bucket_list[i]);
    }
    free(bucket_list);
}

代码链接

(3) 时间复杂度 O(n)
上面的代码可以分为三个部分：

第一是分配内存，循环 bucket_size 次，

第二是把每个数据分到对应的桶中，循环 n 次；每个桶内部需要排序，循环 n/bucket_size 次；一共是循环 n * (n/bucket_size)次。

第三是把桶里的数据复制回原来位置,并释放内存，循环 n 次。

三者相加的结果是
S = n * (n/bucket_size) + n + bucket_size

取bucket_size = 1，则 S = n^2 + n + 1
即 最坏时间复杂度是 O(n²)

取bucket_size = n，则 S = n + n + n = 3n
即 最好时间复杂度是 O(n)

当然，不一定要用链表，不一定要动态分配内存，桶内的排序也不一定要像上面的代码那样使用直接插入排序，不过这些对时间复杂度的影响没有很明显。只要映射函数选的好，还有桶的数量足够大，时间复杂度就趋于线性。

(4)空间复杂度 O(n)

(5)稳定性：稳定

3、基数排序

(1)描述
基数排序使用分治思想，与桶排序十分类似。

先根据键值的部份资料，将要排序的数据分配到某些“桶”中，桶内排序。再根据键值的另一个资料来重复执行。
比如先根据键值的个位数排序，再根据十位数、百位数等等，直到完全有序。

或者说是根据多个键值排序，比如扑克牌的大小和花色。

基数排序的方式可以采用最低位优先法，简称LSD（Least significant digital）或最高位优先法，简称MSD（Most significant digital）。

LSD：先从最低位开始排序，再对次低位排序，直到对最高位排序后得到一个有序序列；

MSD：先从最高位开始排序，再逐个对各分组按次高位进行子排序，循环直到最低位。

LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。

(2)实现

#define RADIX 10
void lsd_radix_sort(int data[], int n)
{
    int max = data[0];
    for (int i = 1; i < n; ++i)
    {
        max = data[i] > max ? data[i] : max;
    }

    int *result = (int *)malloc(n * sizeof(int));
    int bucket[RADIX];
    int digit_position;
    for (digit_position = 1; max/digit_position > 0; digit_position *= RADIX)
    {
        memset(bucket, 0, sizeof(bucket));
        for (int i = 0; i < n; ++i)
        {
            bucket[data[i]/digit_position%RADIX]++; // 统计每个桶有几个数据
        }
        for (int i = 1; i < RADIX; ++i)
        {
            bucket[i] = bucket[i] + bucket[i - 1]; // 统计每个数据之前有多少个数据
        }
        for (int i = n-1; i >= 0; --i) // 从后往前,稳定
        {
            bucket[data[i]/digit_position%RADIX]--;
            result[bucket[data[i]/digit_position%RADIX]] = data[i];
        }
        for (int i = 0; i < n; ++i)
        {
            data[i] = result[i];
        }
    }
    free(result);
}

代码链接

(3) 时间复杂度O(n log_rm)
其中m表示数据的最大值，
r表示基数，
n表示数据个数。
所以在m非常大的时候，不适合用基数排序。

(4)空间复杂度 O(n)

(5)稳定性：稳定