基數排序基數排序詳解－IT工程師數位筆記本

文章出處

基本概念：

基數排序（英語：Radix sort）是一種非比較型整數排序算法，其原理是將整數按位數切割成不同的數字，然后按每個位數分別比較。由于整數也可以表達字符串（比如名字或日期）和特定格式的浮點數，所以基數排序也不是只能使用于整數。基數排序是穩定性的排序。

它是這樣實現的：將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然后，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以后，數列就變成一個有序序列。

基數排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。

關于復雜度：

基數排序的時間復雜度是O(k·n)，其中n是排序元素個數，k是數字位數。注意這不是說這個時間復雜度一定優于O(n·log(n))，k的大小取決于數字位的選擇（比如比特位數），和待排序數據所屬數據類型的全集的大小；k決定了進行多少輪處理，而n是每輪處理的操作數目。

簡單例子：

將數組{27, 91, 1, 97, 17, 23, 84, 28, 72, 5, 67, 25}排序的流程如下

源碼：

#include #include #define BASE 10 //基數桶[0-9]void radixsort(int arr[], int size){    if (arr == NULL)        return ;    //找出最大數    int max = arr[0];    int i;    for (i = 1; i < size; ++i) {        if (arr[i] > max) {            max = arr[i];        }    }    int exp = 1; //位數    int *temp = (int*) malloc(size * sizeof(int));    while (max / exp > 0) {        //重置基數桶        int bucket[BASE] = {0};        //統計每個基數上有多少個數據        for (i = 0; i < size; ++i) {            bucket[(arr[i] / exp) % BASE]++;        }        //求出基數桶的邊界索引,bucket[i]值為第i個桶的右邊界索引+1        for (i = 1; i < BASE; ++i) {            bucket[i] += bucket[i - 1];        }        //這里要從右向左掃描，保證排序穩定性        for (i = size - 1; i >= 0; i--) {            temp[--bucket[(arr[i] / exp) % BASE]] = arr[i];        }        //將基數桶排好的數據賦值到原數據，完成一趟排序        for (i = 0; i < size; ++i) {            arr[i] = temp[i];        }        exp *= BASE; //位數遞增    }    free(temp);}int main(){    int arr[] = {27, 91, 1, 97, 17, 23, 84, 28, 72, 5, 67, 25};    int size = sizeof(arr) / sizeof(int);    // soer    radixsort(arr, size);    //print    int i;    for (i = 0; i < size; ++i)        printf("%d ", arr[i]);    printf("\n");    return 0;}

編譯運行：