1）算法簡介

基數排序是一種非比較型整數排序算法，其原理是將整數按位數切割成不同的數字，然后按每個位數分別比較。由于整數也可以表達字符串（比如名字或日期）和特定格式的浮點數，所以基數排序也不是只能使用于整數。基數排序的發明可以追溯到1887年赫爾曼·何樂禮在打孔卡片制表機（Tabulation Machine）上的貢獻。

2）算法描述和分析

整個算法過程描述如下：
1、將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。
2、從最低位開始，依次進行一次排序。
3、這樣從最低位排序一直到最高位排序完成以后, 數列就變成一個有序序列。

基數排序的時間復雜度是 O(k?n)，其中n是排序元素個數，k是數字位數。

注意這不是說這個時間復雜度一定優于O(n·log(n))，因為k的大小一般會受到n的影響。 以排序n個不同整數來舉例，假定這些整數以B為底，這樣每位數都有B個不同的數字，k就一定不小于logB(n)。由于有B個不同的數字，所以就需要B個不同的桶，在每一輪比較的時候都需要平均n·log2(B) 次比較來把整數放到合適的桶中去，所以就有：k 大于或等于 logB(n)
每一輪(平均)需要 n·log2(B) 次比較

所以，基數排序的平均時間T就是：
T ≥ logB(n)·n·log2(B) = log2(n)·logB(2)·n·log2(B) = log2(n)·n·logB(2)·log2(B) = n·log2(n)

所以和比較排序相似，基數排序需要的比較次數：T ≥ n·log2(n)。 故其時間復雜度為 Ω(n·log2(n)) = Ω(n·log n) 。

3）算法圖解、flash演示、視頻演示

圖解：

Flash：
可參見http://ds.fzu.edu.cn/fine/resources/FlashContent.asp?id=91中的flash過程

視頻：
http://www.tudou.com/programs/view/vfoUHC-tgi0

4）算法代碼

#include <stdio.h> #include <stdlib.h> void radixSort(int data[]) { int temp[10][10] = {0}; int order[10] = {0}; int n = 1; while(n <= 10) { int i; for(i = 0; i < 10; i++) { int lsd = ((data[i] / n) % 10); temp[lsd][order[lsd]] = data[i]; order[lsd]++; } // 重新排列 int k = 0; for(i = 0; i < 10; i++) { if(order[i] != 0) { int j; for(j = 0; j < order[i]; j++, k++) { data[k] = temp[i][j]; } } order[i] = 0; } n *= 10; } } int main(void) { int data[10] = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81}; printf("\n排序前: "); int i; for(i = 0; i < 10; i++) printf("%d ", data[i]); putchar('\n'); radixSort(data); printf("\n排序後: "); for(i = 0; i < 10; i++) printf("%d ", data[i]); return 0; }

5）考察點、重點和頻度分析

計數排序在處理密集整數排序的問題的時候非常有限，尤其是有時候題目對空間并不做太大限制，那使用計數排序能夠達到O(n)的時間復雜度，遠快于所有基于比較的其他排序方法。

轉載于:https://www.cnblogs.com/shih/p/6660246.html

總結

以上是生活随笔為你收集整理的【每日算法】基数排序算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。