基数排序算法思想

输入n个d位数，现在要对n个数进行排序，就需要设计一个排序算法法。基数排序算法思想：先对最低有效位采用稳定排序算法进行排序，然后从次最低有效位到最高有效位依次采用稳定排序算法进行排序，处理完最高有效位后则是最终排序后的结果。这里说明一下什么是稳定排序算法和不稳定排序算法：大小相同的数字A和B分别在原始序列中的索引是x和y，且x>y。经过排序后A和B分别所在输出序列的索引是x1和y1，如果x1>y1，那么这个排序算法是稳定的，如果x1<y1，那么这个排序算法是不稳定的。而基数排序算法为什么一定要用稳定排序算法进行排序呢？因为不稳定排序算法会破坏相同数字的相对顺序，举个例子，现有输入序列[23, 24]，最低有效位分别是3和4，先对最低有效位排序后得到的结果是[23, 24]，最后我们对最高有效位进行排序，最高有效位都是是2，如果排序算法是不稳定的那么得到的结果是[24, 23]，这是不正确的。而采用稳定排序算法输出结果是[23, 24]。为了方便理解基数排序算法，我们作了如下图描述基数排序过程。

从图中可以看出，输入序列中每个元素的数据位数不同，那么在进行排序时高位不足的补0。

基数排序算法实现

基数排序算法的实现最重要的是各个有效位使用的排序算法，已知计数排序算法的时间复杂度是O(n+k)，如果基数排序采用计数排序对n个d位的数字进行排序，那么时间复杂度是O(d(n+k))，现在我们用计数排序算法实现基数排序算法。

//求取最大值static int get_max(int *arr, int length){    int i = 0;    int max = 0;    max = arr[0];    for(i = 1; i < length; i++){        if(arr[i] > max){            max = arr[i];        }    }    return max;}//计数排序void count_sort(int *arr, int length, int exp){    if(arr == NULL || length <= 0 || exp <= 0){        return;    }    int bucket[10] = {0};    int *output = (int *)malloc(sizeof(int) * length);    if(output == NULL){        return;    }    memset(output, 0, sizeof(int) * length);    int i = 0;    for(i = 0; i < length; i++){        bucket[(arr[i] / exp) % 10]++;    }    for(i = 1; i < length; i++){        bucket[i] += bucket[i - 1];    }    for(i = length - 1; i >= 0; i--){        output[bucket[(arr[i] / exp) % 10] - 1] = arr[i];        bucket[(arr[i] / exp) % 10]--;    }    for(i = 0; i < length; i++){        arr[i] = output[i];    }    free(output);}//基数排序void radix_sort(int *arr, int length){    if(arr == NULL || length <= 0){        return;    }    int exp = 0;    int max = get_max(arr, length);    for(exp = 1; max / exp; exp *= 10){        count_sort(arr, length, exp);    }}

最后写一个小程序验证算法的正确性。

#include <stdio.h>#include "radix_sort.h"int main() {    int arr[10] = {873, 12, 89, 256, 978, 67, 56434, 654, 24345, 9};    radix_sort(arr, 10);    int i = 0;    printf("基数排序结果\n");    for(i = 0; i < 10; i++){        printf("%d ", arr[i]);    }    printf("\n");    return 0;}

编译运行输出如下：

基数排序结果9 12 67 89 256 654 873 978 24345 56434

输出完全正确。