說明

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

基數(shù)排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。LSD使用計數(shù)排序或桶排序，MSD可以使用桶排序。由低到高（LSD）比較簡單，按位重排即可，如果是從高往低（MSD）則不能每次重排，可以通過遞歸來逐層遍歷實現(xiàn)。詳細請看各種不同版本的源碼。

排序算法網(wǎng)上有很多實現(xiàn)，但經(jīng)常有錯誤，也缺乏不同語言的比較。本系列把各種排序算法重新整理，用不同語言分別實現(xiàn)。

實現(xiàn)過程

1. 將待排序數(shù)列（正整數(shù)）統(tǒng)一為同樣的數(shù)位長度，數(shù)位較短的補零。

2. 每個數(shù)位單獨排序，從最低位到最高位，或從最高位到最低位。

3. 這樣從最低到高或從高到低排序完成以后，數(shù)列就變成一個有序數(shù)列。

?

示意圖

?

?

性能分析

時間復雜度：O(k*N)
空間復雜度：O(k + N)
穩(wěn)定性：穩(wěn)定

?

代碼

?

Java

class RadixSort { ?// 基數(shù)排序，基于計數(shù)排序，按數(shù)位從低到高來排序 ?public static int[] countingSort(int arr[], int exponent) { ? ?// 基數(shù)exponent按10進位，range為10 ? ?int range = 10; ? ?int[] countList = new int[range]; ? ?int[] sortedList = new int[arr.length]; ? ?// 設(shè)定最小值以支持負數(shù) ? ?int min = arr[0]; ? ?for (int i = 0; i < arr.length; i++) { ? ? ?if (arr[i] < min) { ? ? ? ?min = arr[i]; ? ? ?} ? ?} ? ?// 根據(jù)基數(shù)求得當前項目對應位置的數(shù)值，并給對應計數(shù)數(shù)組位置加1 ? ?for (int i = 0; i < arr.length; i++) { ? ? ?int item = arr[i] - min; ? ? ?// 根據(jù)exponent獲得當前位置的數(shù)字是幾，存入對應計數(shù)數(shù)組 ? ? ?int idx = (item / exponent) % range; ? ? ?countList[idx] += 1; ? ?} ? ?// 根據(jù)位置計數(shù)，后面的位數(shù)為前面的累加之和 ? ?for (int i = 1; i < range; i++) { ? ? ?countList[i] += countList[i - 1]; ? ?} ? ?System.out.println("radixSort1 countingSort countList:" + Arrays.toString(countList)); ? ?// 根據(jù)計數(shù)數(shù)組按順序取出排序內(nèi)容 ? ?for (int i = arr.length - 1; i >= 0; i--) { ? ? ?int item = arr[i] - min; ? ? ?int idx = (item / exponent) % range; ? ? ?// 根據(jù)計數(shù)位置得到順序 ? ? ?sortedList[countList[idx] - 1] = arr[i]; ? ? ?countList[idx] -= 1; ? ?} ? ?// 最后賦值給原數(shù)據(jù) ? ?for (int i = 0; i < arr.length; i++) { ? ? ?arr[i] = sortedList[i]; ? ?} ? ?System.out.println("radixSort1 -> sortedList:" + Arrays.toString(sortedList)); ? ?return sortedList; ?} ?// 基數(shù)排序1，按數(shù)位大小，基于計數(shù)排序?qū)崿F(xiàn) ?public static int[] radixSort1(int arr[]) { ? ?int max = arr[0]; ? ?for (int i = 0; i < arr.length; i++) { ? ? ?if (arr[i] > max) { ? ? ? ?max = arr[i]; ? ? ?} ? ?} ? ?// 根據(jù)最大值，逐個按進位(基數(shù))來應用排序，exponent即數(shù)位。 ? ?for (int exponent = 1; (max / exponent) > 0; exponent *= 10) { ? ? ?countingSort(arr, exponent); ? ?} ? ?return arr; ?} }

?

// 基數(shù)排序，從高到低逐位排序，遞歸方式，基于桶排序。具體步驟如下：// 1. 找出數(shù)組中最大的數(shù)，確定其位數(shù)。// 2. MSD是從高位開始，依次按照位數(shù)的值將數(shù)字放入到不同桶中。// 3. 如果桶里的長度超過1，則通過遞歸繼續(xù)按桶排序。當桶里的數(shù)據(jù)只有1位時添加到原列表對應位置。// 重復步驟2和3，直到按照最高位排序完成。class RadixSortMSD { ?static int[] radixSort(int[] arr) { ? ?int len = arr.length; ? ?// 獲取數(shù)組最大項 ? ?int max = arr[0]; ? ?for (int i = 0; i < len; i++) { ? ? ?if (max < arr[i]) { ? ? ? ?max = arr[i]; ? ? ?} ? ?} ? ?// 獲取數(shù)組最小項 ? ?int min = arr[0]; ? ?for (int i = 0; i < len; i++) { ? ? ?if (min > arr[i]) { ? ? ? ?min = arr[i]; ? ? ?} ? ?} ? ?// 獲取數(shù)字一共有幾位，減去min得到最大值，以支持負數(shù)和減少最大值 ? ?int numberOfDigits = (int) (Math.log10(max - min) + 1); ? ?int exponent = (int) (Math.pow(10, numberOfDigits - 1)); ? ?// 根據(jù)數(shù)組最大值，自后向前逐個按數(shù)位基數(shù)(exponent)比較排序。 ? ?return bucketSort(arr, len, exponent); ?} ?static int[] bucketSort(int[] arr, int len, int exponent) { ? ?System.out.println("origin arr:" + Arrays.toString(arr) + " len=" + len + " exponent:" + exponent); ? ?if (len <= 1 || exponent < 1) { ? ? ?return arr; ? ?} ? ?// 獲取數(shù)組最小項 ? ?int min = arr[0]; ? ?for (int i = 0; i < len; i++) { ? ? ?if (min > arr[i]) { ? ? ? ?min = arr[i]; ? ? ?} ? ?} ? ?// 位數(shù)按10遞進 ? ?int range = 10; ? ?// 定義桶二維數(shù)組，長度為10，放入0-9的數(shù)字 ? ?int[][] buckets = new int[range][len]; ? ?// 記錄某個桶的最新長度，以便往桶內(nèi)追加數(shù)據(jù)。 ? ?int[] bucketsCount = new int[range]; ? ?for (int i = 0; i < len; i++) { ? ? ?int item = arr[i] - min; ? ? ?// 根據(jù)數(shù)位上的值，把數(shù)據(jù)追加到對應的桶里，減去min是支持負數(shù) ? ? ?int bucketIdx = (item / exponent) % range; ? ? ?// 把數(shù)據(jù)按下標插入到桶里 ? ? ?int numberIndex = bucketsCount[bucketIdx]; ? ? ?buckets[bucketIdx][numberIndex] = arr[i]; ? ? ?bucketsCount[bucketIdx] += 1; ? ?} ? ?// 將每個桶的數(shù)據(jù)按順序逐個取出，重新賦值給原數(shù)組 ? ?int sortedIdx = 0; ? ?for (int i = 0; i < range; i++) { ? ? ?int[] bucket = buckets[i]; ? ? ?int bucketLen = bucketsCount[i]; ? ? ?// 如果只有一個值，則直接更新到原數(shù)組 ? ? ?if (bucketsCount[i] == 1) { ? ? ? ?arr[sortedIdx] = bucket[0]; ? ? ? ?sortedIdx += 1; ? ? ?} else if (bucket.length > 0 && bucketLen > 0) { ? ? ? ?// 如果是數(shù)組且記錄大于1則繼續(xù)遞歸調(diào)用，位數(shù)降低1位 ? ? ? ?// 遞歸調(diào)用傳參時需要傳入當前子序列、子序列長度、當前分解的位數(shù)基數(shù) ? ? ? ?int[] sortedBucket = bucketSort(bucket, bucketLen, (int) (exponent / range)); ? ? ? ?// 依照已排序的子序列實際長度，把各個桶里的值按順序賦給原數(shù)組 ? ? ? ?for (int j = 0; j < bucketLen; j++) { ? ? ? ? ?int num = sortedBucket[j]; ? ? ? ? ?arr[sortedIdx] = num; ? ? ? ? ?sortedIdx += 1; ? ? ? ?} ? ? ?} ? ?} ? ?System.out.println("exponent:" + exponent + " sorted arr:" + Arrays.toString(arr)); ? ?return arr; ?}

?

Python

?

"""基數(shù)排序LSD版，本基于桶排序。 1. 找出數(shù)組中最大的數(shù)，確定其位數(shù)。 2. LSD是低位到高位，依次按照位數(shù)的值將數(shù)字放入到不同桶中。 3. 按照桶順序重新給數(shù)組排序。 重復步驟2和3，直到排序完成。"""def radix_sort(arr): ? ?max_value = max(arr) ?# 找出數(shù)組中最大的數(shù) ? ?min_value = min(arr) ?#最小值，為了支持負數(shù) ? ?digit = 1 ?# 從個位開始排序 ? ?# 每次排序一個數(shù)位，從低到高直到排序完成 ? ?while (max_value - min_value) // digit > 0: ? ? ? ?# 創(chuàng)建10個桶，分別對應0-9的數(shù)位值 ? ? ? ?buckets = [[] for _ in range(10)] ? ? ? ?for num in arr: ? ? ? ? ? ?# 找出當前位數(shù)的值 ? ? ? ? ? ?digit_num = (num - min_value) // digit % 10 ? ? ? ? ? ?# 將數(shù)字添加到對應數(shù)位的桶中，相當于根據(jù)數(shù)位排序 ? ? ? ? ? ?buckets[digit_num].append(num) ? ? ? ?print('buckets:', buckets) ? ? ? ?# 通過exend展開數(shù)組，相當于逐層添加 ? ? ? ?arr = [] ? ? ? ?for bucket in buckets: ? ? ? ? ? ?arr.extend(bucket) ? ? ? ? ? ?# 或逐項添加 ? ? ? ? ? ?# for item in bucket: ? ? ? ? ? ?# ? ? arr.append(item) ? ? ? ?# 數(shù)位移動到下一位 ? ? ? ?digit *= 10 ? ?return arr

"""基數(shù)排序，從高到低逐位排序，遞歸方式，基于桶排序。具體步驟如下： 1. 找出數(shù)組中最大的數(shù)，確定其位數(shù)。 2. MSD是從高位開始，依次按照位數(shù)的值將數(shù)字放入到不同桶中。 3. 如果桶里的長度超過1，則通過遞歸繼續(xù)按桶排序。當桶里的數(shù)據(jù)只有1位時添加到原列表對應位置。 重復步驟2和3，直到按照最高位排序完成。"""# 桶排序，根據(jù)數(shù)位遞歸調(diào)用def bucket_sort(arr, exponent): ? ?print('origin arr:', arr, 'exponent:', exponent) ? ?if (len(arr) <= 1 or exponent <= 0): ? ? ? ?return arr ? ?min_value = min(arr) ? ?radix = 10 ? ?amount = 10 ? ?print('prepared arr:', arr, 'exponent:', exponent) ? ?# 構(gòu)建排序的桶二維列表 ? ?buckets = [None] * radix ? ?for i in range(len(arr)): ? ? ? ?item = arr[i] - min_value ? ? ? ?# 根據(jù)數(shù)位上的值，把數(shù)據(jù)追加到對應的桶里，減去min是支持負數(shù) ? ? ? ?bucketIdx = int(item / exponent) % radix ? ? ? ?# 填充空桶，或者提前填充為列表 ? ? ? ?if buckets[bucketIdx] is None: ? ? ? ? ? ?buckets[bucketIdx] = [] ? ? ? ?buckets[bucketIdx].append(arr[i]) ? ?print('append to buckets:', buckets) ? ?# 將每個桶的數(shù)據(jù)按順序逐個取出，重新賦值給原數(shù)組 ? ?sortedIdx = 0 ? ?for i in range(radix): ? ? ? ?bucket = buckets[i] ? ? ? ?if bucket is None or len(bucket) < 1: ? ? ? ? ? ?continue ? ? ? ?# 如果是數(shù)組則繼續(xù)遞歸調(diào)用，位數(shù)降低1位 ? ? ? ?sortedBucket = bucket_sort(bucket, exponent // amount) ? ? ? ?# 把各個桶里的值按順序賦給原數(shù)組 ? ? ? ?for num in sortedBucket: ? ? ? ? ? ?print ('sortedIdx::', sortedIdx) ? ? ? ? ? ?arr[sortedIdx] = num ? ? ? ? ? ?print('bucket:', bucket, 'sortedBucket:', sortedBucket, ? ? ? ? ? ? ? ? ?'sortedIdx:', sortedIdx, 'set arr:', arr) ? ? ? ? ? ?sortedIdx += 1 ? ?print('exponent:', exponent, 'sorted arr:', arr) ? ?return arr# 基數(shù)排序，從高到低逐位排序MSD版，基于桶排序遞歸實現(xiàn)def radix_sort_msd(arr): ? ?# 根據(jù)最大值，逐個按進位(基數(shù))來應用排序，從高位到低位。 ? ?# 獲取數(shù)字的數(shù)位，這減去min_value是為了支持負數(shù) ? ?# exponent是最大的數(shù)位，由高到低逐位計算 ? ?max_value = max(arr) ? ?min_value = min(arr) ? ?numberOfDigits = int(math.log10(max_value - min_value) + 1) ? ?exponent = math.pow(10, numberOfDigits - 1) ? ?return bucket_sort(arr, int(exponent))

?

Go

// 2. 基數(shù)排序LSD版，計算最小值，基于計數(shù)排序?qū)崿F(xiàn)func radixSort2(arr []int) []int { ?var arrLen = len(arr) ?// 基數(shù)exponent按10進位，amount為10 ?var amount = 10 ?var sortedList = make([]int, arrLen) ?var max = arr[0] ?for i := 0; i < arrLen; i++ { ? ?if arr[i] > max { ? ? ?max = arr[i] ? ?} ?} ?var min = arr[0] ?for i := 0; i < arrLen; i++ { ? ?if arr[i] < min { ? ? ?min = arr[i] ? ?} ?} ?// 根據(jù)基數(shù)求得當前項目對應位置的數(shù)值，并給對應計數(shù)數(shù)組位置加1 ?// 按最大值補齊數(shù)位，基數(shù)exponent按10進位 ?for exponent := 1; ((max - min) / exponent) > 0; exponent *= amount { ? ?// 計數(shù)數(shù)組，長度為10，0-9一共10個數(shù)字 ? ?countList := make([]int, amount) ? ?// 根據(jù)基數(shù)得到當前位數(shù)，并給計數(shù)數(shù)組對應位置加1 ? ?for i := 0; i < arrLen; i++ { ? ? ?var item = arr[i] - min ? ? ?var idx = (item / exponent) % amount ? ? ?countList[idx] += 1 ? ?} ? ?// 計數(shù)排序構(gòu)建，自前往后，逐個將上一項的值存入當前項 ? ?for i := 1; i < amount; i++ { ? ? ?countList[i] += countList[i-1] ? ?} ? ?fmt.Println("radixSort2 -> countList:", countList) ? ?// 根據(jù)計數(shù)數(shù)組按順序取出排序內(nèi)容 ? ?for i := arrLen - 1; i >= 0; i-- { ? ? ?item := arr[i] - min ? ? ?var idx = (item / exponent) % amount ? ? ?sortedList[countList[idx]-1] = arr[i] ? ? ?countList[idx] -= 1 ? ?} ? ?// 將新順序賦值給原數(shù)組 ? ?for i := 0; i < arrLen; i++ { ? ? ?arr[i] = sortedList[i] ? ?} ?} ?return arr }

// 基數(shù)排序，從高到低逐位排序，遞歸方式，基于桶排序。具體步驟如下：// 1. 找出數(shù)組中最大的數(shù)，確定其位數(shù)。// 2. MSD是從高位開始，依次按照位數(shù)的值將數(shù)字放入到不同桶中。// 3. 如果桶里的長度超過1，則通過遞歸繼續(xù)按桶排序。當桶里的數(shù)據(jù)只有1位時添加到原列表對應位置。// 重復步驟2和3，直到按照最高位排序完成。func radixSortMSD(arr []int) []int { ?var amount = 10 ?maxValue := max(arr) ?exponent := pow(amount, getNumberOfDigits(maxValue)-1) ?bucketSort(arr, exponent) ?return arr }func bucketSort(arr []int, exponent int) []int { ?fmt.Println("origin arr:", arr, "exponent: ", exponent) ?if exponent < 1 || len(arr) <= 1 { ? ?return arr ?} ?var amount = 10 ?fmt.Println("prepared arr:", arr, "exponent: ", exponent) ?buckets := [][]int{} ?// 按數(shù)位來獲取最小值 ?minValue := getMinValue(arr, exponent) ?// 增加偏移以便支持負數(shù) ?offset := 0 ?if minValue < 0 { ? ?offset = 0 - minValue ?} ?// 填充桶二維數(shù)組 ?for i := 0; i < (amount + offset); i++ { ? ?buckets = append(buckets, []int{}) ?} ?// 獲取數(shù)組項指定數(shù)位的值，放入到對應桶中，桶的下標即順序 ?for i, num := range arr { ? ?bucketIdx := getDigit(arr, i, exponent) + offset ? ?buckets[bucketIdx] = append(buckets[bucketIdx], num) ?} ?fmt.Println("append to buckets: ", buckets) ?sortedIdx := 0 ?for _, bucket := range buckets { ? ?if len(bucket) <= 0 { ? ? ?continue ? ?} ? ?// 遞歸遍歷所有的桶，由里而外逐個桶進行排序 ? ?sortedBucket := bucketSort(bucket, exponent/amount) ? ?// 把各個桶里的值按順序賦給原數(shù)組 ? ?for _, num := range sortedBucket { ? ? ?arr[sortedIdx] = num ? ? ?fmt.Println("bucket:", bucket, "sortedBucket: ", sortedBucket, "sortedIdx:", sortedIdx, "set arr: ", arr) ? ? ?sortedIdx += 1 ? ?} ?} ?fmt.Println("exponent: ", exponent, "sorted arr: ", arr) ?return arr }// 獲取數(shù)字位數(shù)func getNumberOfDigits(num int) int { ?numberOfDigits := 0 ?for num > 0 { ? ?numberOfDigits += 1 ? ?num /= 10 ?} ?return numberOfDigits }// 獲取絕對值func abs(value int) int { ?if value < 0 { ? ?return -value ?} ?return value }// 獲取數(shù)組最大值func max(arr []int) int { ?maxValue := arr[0] ?for i := 1; i < len(arr); i++ { ? ?if arr[i] > maxValue { ? ? ?maxValue = arr[i] ? ?} ?} ?return maxValue }// 計算數(shù)字次冪func pow(a int, power int) int { ?result := 1 ?for i := 0; i < power; i++ { ? ?result *= a ?} ?return result }// 獲取數(shù)組項指定數(shù)位的最小值func getMinValue(arr []int, exponent int) int { ?minValue := getDigit(arr, 0, exponent) ?for i := 1; i < len(arr); i++ { ? ?element := getDigit(arr, i, exponent) ? ?if minValue > element { ? ? ?minValue = element ? ?} ?} ?return minValue }// 獲取數(shù)字指定數(shù)位的值，超出數(shù)位補0，負數(shù)返回負數(shù)// 如: 1024, 百位: 100 => 返回 0// 如: -2048, 千位: 1000 => 返回 -2func getDigit(arr []int, idx int, exponent int) int { ?element := arr[idx] ?digit := abs(element) / exponent % 10 ?if element < 0 { ? ?return -digit ?} ?return digit }

?

JS

// 基數(shù)排序2，從低到高逐個數(shù)位對比排序，基于桶排序，利用JS數(shù)組展開來還原數(shù)組function radixSort2(arr) { ?// 倒數(shù)獲取數(shù)字指定位置的數(shù) ?function getDigit(num, position) { ? ?const digit = Math.floor(num / Math.pow(10, position - 1)) % 10 ? ?return digit ?} ?// 獲取數(shù)組最大數(shù)字的位數(shù) ?function getNumberLength(num) { ? ?let maxLength = 0 ? ?while (num > 0) { ? ? ?maxLength++ ? ? ?num /= 10 ? ?} ? ?return maxLength ?} ?const max = Math.max.apply(null, arr) ?const min = Math.min.apply(null, arr) ?const maxLength = getNumberLength(max - min) ?for (let i = 0; i < maxLength; i++) { ? ?// 每個數(shù)位準備10個空數(shù)組，用于放數(shù)字0-9 ? ?const buckets = Array.from({ ? ? ?length: 10 ? ?}, () => []) ? ?// 遍歷數(shù)組將數(shù)位上的數(shù)放入對應桶里 ? ?for (let j = 0, l = arr.length; j < l; j++) { ? ? ?const item = (arr[j] - min) ? ? ?// 從后往前獲取第x位置的數(shù)，通過計算的方式 ? ? ?const num = getDigit(item, i + 1) ? ? ?// 當前位數(shù)如果不為空則添加到基數(shù)桶中 ? ? ?if (num !== isNaN) { ? ? ? ?buckets[num].push((arr[j])) ? ? ?} ? ?} ? ?// 將桶逐級展開取出數(shù)字，如果支持flat則直接使用數(shù)組的flat() ? ?if (buckets.flat) { ? ? ?arr = buckets.flat() ? ?} else { ? ? ?// 定定義數(shù)組展開函數(shù) ? ? ?// arr = flat(buckets) ? ?} ?} ?return arr }

// 基數(shù)排序，從高到低逐位排序，遞歸方式，基于桶排序。具體步驟如下：// 1. 找出數(shù)組中最大的數(shù)，確定其位數(shù)。// 2. MSD是從高位開始，依次按照位數(shù)的值將數(shù)字放入到不同桶中。// 3. 如果桶里的長度超過1，則通過遞歸繼續(xù)按桶排序。當桶里的數(shù)據(jù)只有1位時添加到原列表對應位置。// 重復步驟2和3，直到按照最高位排序完成。function radixSortMSD(arr) { ?function bucketSort(arr, exponent) { ? ?console.log('origin arr:', arr, 'exponent:', exponent) ? ?if (!arr || arr.length <= 1 || exponent < 1) { ? ? ?return arr ? ?} ? ?const min = Math.min.apply(null, arr) ? ?const range = 10 ? ?// 定義桶二維數(shù)組，長度為10，放入0-9的數(shù)字 ? ?const buckets = [] ? ?for (let i = 0; i < range; i++) { ? ? ?buckets[i] = [] ? ?} ? ?for (let i = 0, l = arr.length; i < l; i++) { ? ? ?const item = arr[i] - min ? ? ?// 根據(jù)數(shù)位上的值，把數(shù)據(jù)追加到對應的桶里，減去min是支持負數(shù) ? ? ?const bucketIdx = Math.floor(item / exponent % range) ? ? ?// 提前填充空桶或使用時再填充 ? ? ?if (!buckets[bucketIdx]) { ? ? ? ?buckets[bucketIdx] = [] ? ? ?} ? ? ?buckets[bucketIdx].push(arr[i]) ? ?} ? ?// 將每個桶的數(shù)據(jù)按順序逐個取出，重新賦值給原數(shù)組 ? ?let sortedIdx = 0 ? ?for (let i = 0; i < range; i++) { ? ? ?const bucket = buckets[i] ? ? ?if (bucket && bucket.length > 0) { ? ? ? ?// 如果是數(shù)組則繼續(xù)遞歸調(diào)用，位數(shù)降低1位 ? ? ? ?const sortedBucket = bucketSort(bucket, Math.floor(exponent / range)) ? ? ? ?// 把各個桶里的值按順序賦給原數(shù)組 ? ? ? ?sortedBucket.forEach(num => { ? ? ? ? ?arr[sortedIdx] = num ? ? ? ? ?sortedIdx += 1 ? ? ? ?}) ? ? ?} ? ?} ? ?return arr ?} ?const max = Math.max.apply(null, arr) ?const min = Math.min.apply(null, arr) ?// 獲取數(shù)字一共有幾位，減去min得到最大值，以支持負數(shù)和減少最大值 ?const numberOfDigits = Math.floor(Math.log10(max - min) + 1) ?const exponent = Math.pow(10, numberOfDigits - 1) ?// 根據(jù)數(shù)組最大值，自后向前逐個按數(shù)位基數(shù)(exponent)比較排序。 ?return bucketSort(arr, exponent) }

?

TS

?

class RadixSort { ?// 基數(shù)排序，基于計數(shù)排序的基礎(chǔ)上，按數(shù)字的每個位置來排序 ?countingSort(arr: Array<number>, exponent: number) { ? ?const countList = Array<number>() ? ?const range = 10 ? ?countList.length = range ? ?countList.fill(0) ? ?const min = Math.min.apply(null, arr) ? ?for (let i = 0, l = arr.length; i < l; i++) { ? ? ?const item = arr[i] - min ? ? ?// 取得數(shù)字的最后一位，并給對應計數(shù)數(shù)組加1 ? ? ?const idx = Math.floor((item / exponent) % range) ? ? ?countList[idx] += 1 ? ?} ? ?console.log('countingSort countList:', countList) ? ?// 根據(jù)位置計數(shù)，后面的位數(shù)為前面的累加之和 ? ?for (let i = 1; i < range; i++) { ? ? ?countList[i] += countList[i - 1] ? ?} ? ?const sortedList = Array<number>() ? ?// 根據(jù)計數(shù)數(shù)組按順序取出排序內(nèi)容 ? ?for (let i = arr.length - 1; i >= 0; i--) { ? ? ?const item = arr[i] - min ? ? ?const idx = Math.floor((item / exponent) % range) ? ? ?sortedList[countList[idx] - 1] = arr[i] ? ? ?countList[idx] -= 1 ? ?} ? ?// 最后賦值給原數(shù)據(jù) ? ?for (let i = 0; i < arr.length; i++) { ? ? ?arr[i] = sortedList[i] ? ?} ? ?return sortedList ?} ?// 基數(shù)排序LSD版，基于計數(shù)排序的基礎(chǔ)，支持負數(shù)，按數(shù)字的每個位置來排序 ?radixSort(arr: Array<number>) { ? ?let sortedList = Array<number>() ? ?const max = Math.max.apply(null, arr) ? ?const min = Math.min.apply(null, arr) ? ?for ( ? ? ?let exponent = 1; ? ? ?Math.floor((max - min) / exponent) > 0; ? ? ?exponent *= 10 ? ?) { ? ? ?sortedList = this.countingSort(arr, exponent) ? ?} ? ?return sortedList ?} }

?

C

// 計數(shù)排序，根據(jù)基數(shù)按位進行計數(shù)void counting_sort(int arr[], int len, int exponent) { ?int sorted_list[len]; ?int range = 10; ?int count_list[range]; ?// 找出最小值 ?int min_value = arr[0]; ?for (int i = 1; i < len; i++) ?{ ? ?if (arr[i] < min_value) ? ? ?min_value = arr[i]; ?} ?memset(count_list, 0, range * sizeof(int)); ?// 根據(jù)數(shù)字所在位置進行計數(shù) ?for (int i = 0; i < len; i++) ?{ ? ?int item = arr[i] - min_value; ? ?int idx = (item / exponent) % range; ? ?count_list[idx]++; ?} ?// 構(gòu)建計數(shù)排序，當前位置加上左側(cè)位置，后面的位數(shù)為前面的累加之和 ?for (int i = 1; i < range; i++) ?{ ? ?count_list[i] += count_list[i - 1]; ?} ?// 構(gòu)建輸出數(shù)組，根據(jù)計數(shù)數(shù)組按順序取得排序內(nèi)容 ?for (int i = len - 1; i >= 0; i--) ?{ ? ?int item = arr[i] - min_value; ? ?int idx = (item / exponent) % range; ? ?// 根據(jù)位置重排結(jié)果，減去min值還原數(shù)據(jù) ? ?sorted_list[count_list[idx] - 1] = arr[i]; ? ?count_list[idx]--; ?} ?// 復制到數(shù)組重排原始數(shù)組 ?for (int i = 0; i < len; i++) ?{ ? ?arr[i] = sorted_list[i]; ?} }// 基數(shù)排序，從低位到高位LSD版，基于計數(shù)排序int *radix_sort(int arr[], int len) { ?int max_value = arr[0]; ?for (int i = 1; i < len; i++) ?{ ? ?if (arr[i] > max_value) ? ? ?max_value = arr[i]; ?} ?int min_value = arr[0]; ?for (int i = 1; i < len; i++) ?{ ? ?if (arr[i] < min_value) ? ? ?min_value = arr[i]; ?} ?// 根據(jù)最大值，逐個按進位(基數(shù))來應用排序，exponent即數(shù)位基數(shù)，按個十百千遞增。 ?for (int exponent = 1; (max_value - min_value) / exponent > 0; exponent *= 10) ?{ ? ?counting_sort(arr, len, exponent); ?} ?return arr; }

// 根據(jù)最大長度來獲取數(shù)字第n位的值，從前往后開始，前面不足最大長度時補零int get_digit_by_position(int num, int position, int max_length) { ?if (num == 0) ?{ ? ?return 0; ?} ?int number_length = (int)log10(num) + 1; ?// 查詢的位置加上自身長度不足最大長度則返回0 ?if ((position + number_length) < max_length) ?{ ? ?return 0; ?} ?int exponent = (int)pow(10, number_length - position); ?int digit = 0; ?if (exponent > 0) ?{ ? ?digit = (num / exponent) % 10; ?} ?return digit; }// 基數(shù)排序，從高位到逐個對比排序，通過桶排序遞歸調(diào)用// arr是數(shù)組，len是當前數(shù)組長度，position為自前往后的位置，max_length是最大值的數(shù)位int *bucket_sort(int arr[], int len, int position, int max_length) { ?printf("\r\nlen=%d position=%d max_length=%d ", len, position, max_length); ?if (len <= 1 || position > max_length) ?{ ? ?return arr; ?} ?// 找出最小值 ?int min_value = arr[0]; ?for (int i = 1; i < len; i++) ?{ ? ?if (arr[i] < min_value) ? ? ?min_value = arr[i]; ?} ?int range = 10; ?// 桶一共從0-9十個數(shù)字 ?int buckets[range][len]; ?for (int i = 0; i < range; i++) ?{ ? ?// 此處未提前使用，也可以不設(shè)置默認值 ? ?memset(buckets[i], 0, len * sizeof(int)); ? ?// print_array(buckets[i], len); ?} ?// 默認填充內(nèi)容為0 ?int bucket_count_list[range]; ?memset(bucket_count_list, 0, range * sizeof(int)); ?for (int i = 0; i < len; i++) ?{ ? ?int item = arr[i] - min_value; ? ?// 根據(jù)數(shù)位上的值，減去最小值，分配到對應的桶里 ? ?int bucket_idx = get_digit_by_position(item, position, max_length); ? ?// 把數(shù)據(jù)按下標插入到桶里 ? ?int number_idx = bucket_count_list[bucket_idx]; ? ?buckets[bucket_idx][number_idx] = arr[i]; ? ?bucket_count_list[bucket_idx] += 1; ?} ?// 將每個桶的數(shù)據(jù)按順序逐個取出，重新賦值給原數(shù)組 ?int sorted_idx = 0; ?for (int i = 0; i < range; i++) ?{ ? ?int *bucket = buckets[i]; ? ?int bucket_len = bucket_count_list[i]; ? ?int bucket_size = sizeof(*bucket) / sizeof(bucket[0]); ? ?// 如果只有一個值，則直接更新到原數(shù)組 ? ?if (bucket_count_list[i] == 1) ? ?{ ? ? ?arr[sorted_idx] = bucket[0]; ? ? ?sorted_idx += 1; ? ?} ? ?else if (bucket_size > 0 && bucket_len > 0) ? ?{ ? ? ?// 如果是數(shù)組且記錄追加大于1則繼續(xù)遞歸調(diào)用，位置增加1位 ? ? ?// 遞歸調(diào)用傳參時需要傳入當前子序列、子序列長度、當前分解的位數(shù)基數(shù) ? ? ?int *sorted_bucket = bucket_sort(bucket, bucket_len, position + 1, max_length); ? ? ?// 依照已排序的子序列實際長度，把各個桶里的值按順序賦給原數(shù)組 ? ? ?for (int j = 0; j < bucket_len; j++) ? ? ?{ ? ? ? ?int num = sorted_bucket[j]; ? ? ? ?arr[sorted_idx] = num; ? ? ? ?sorted_idx += 1; ? ? ?} ? ?} ?} ?printf("\r\n position:%d", position); ?print_array(arr, len); ?return arr; }// 計數(shù)排序，根據(jù)數(shù)字的位置逐個對比排序，從高到低MSD，遞歸方式int *radix_sort_msd(int arr[], int len) { ?// 找出最大值 ?int max_value = arr[0]; ?for (int i = 1; i < len; i++) ?{ ? ?if (arr[i] > max_value) ? ? ?max_value = arr[i]; ?} ?// 獲取最小項 ?int min_value = arr[0]; ?for (int i = 0; i < len; i++) ?{ ? ?if (min_value > arr[i]) ? ?{ ? ? ?min_value = arr[i]; ? ?} ?} ?// 獲取數(shù)字一共有幾位，減去min得到最大值，以支持負數(shù)和減少最大值 ?int max_length = (int)(log10(max_value - min_value) + 1); ?// 根據(jù)數(shù)組最大值的長度，從前往后逐個對比排序。 ?return bucket_sort(arr, len, 1, max_length); }

?

C++

// 基數(shù)排序，從個位到高位LSD版，基于計數(shù)排序?qū)崿F(xiàn)int *radixSort(int *arr, int len) { ?// 以10倍遞進 ?int range = 10; ?int sortedList[len]; ?int max = arr[0]; ?for (int i = 1; i < len; i++) ?{ ? ?if (arr[i] > max) ? ?{ ? ? ?max = arr[i]; ? ?} ?} ?int min = arr[0]; ?for (int i = 1; i < len; i++) ?{ ? ?if (arr[i] < min) ? ?{ ? ? ?min = arr[i]; ? ?} ?} ?// 根據(jù)最大值，逐個按進位(基數(shù))來應用排序，exponent即基數(shù)。 ?for (int exponent = 1; ((max - min) / exponent) > 0; exponent *= range) ?{ ? ?// 計數(shù)數(shù)組，長度為10，0-9一共10個數(shù)字 ? ?int countList[range]; ? ?memset(countList, 0, range * sizeof(int)); ? ?// 根據(jù)基數(shù)得到當前位數(shù)，并給計數(shù)數(shù)組對應位置加1 ? ?for (int i = 0; i < len; i++) ? ?{ ? ? ?int item = arr[i] - min; ? ? ?int idx = (item / exponent) % range; ? ? ?countList[idx] += 1; ? ?} ? ?// 計數(shù)排序構(gòu)建，自前往后，逐個將上一項的值存入當前項 ? ?for (int i = 1; i < range; i++) ? ?{ ? ? ?countList[i] += countList[i - 1]; ? ?} ? ?// 根據(jù)計數(shù)數(shù)組按順序取出排序內(nèi)容 ? ?for (int i = len - 1; i >= 0; i--) ? ?{ ? ? ?int item = arr[i] - min; ? ? ?int idx = (item / exponent) % range; ? ? ?sortedList[countList[idx] - 1] = arr[i]; ? ? ?countList[idx] -= 1; ? ?} ? ?// 復制輸出數(shù)組到原始數(shù)組 ? ?for (int i = 0; i < len; i++) ? ?{ ? ? ?arr[i] = sortedList[i]; ? ?} ?} ?return arr; }

?

鏈接

基數(shù)排序與計數(shù)排序、桶排序區(qū)別

基數(shù)排序與計數(shù)排序、桶排序三者概念很像，但也有不同，其主要差異如下： 計數(shù)排序：根據(jù)數(shù)組值設(shè)定若干個桶，每個桶對應一個數(shù)值，將這些桶的值分別存入下一個桶中用于排序，最后按順序取出對應桶里的值。 桶排序：根據(jù)情況分為若干個桶，每個桶存儲一定范圍的數(shù)值，每個桶再單獨排序，最后按桶的順序取出全部數(shù)據(jù)。 基數(shù)排序：根據(jù)數(shù)據(jù)的位數(shù)來分配桶，每一位對應一個桶，先將全部數(shù)據(jù)的位數(shù)按最大位數(shù)對齊，再根據(jù)位數(shù)上的值大小排列?；鶖?shù)排序基于計數(shù)排序或者桶排序。