基數(shù)排序算法的原理與實(shí)現(xiàn)詳解(Java/Go/Python/JS/C)
說明
基數(shù)排序(RadixSort)是一種非比較型整數(shù)排序算法,其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字,然后按每個(gè)位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串(比如名字或日期)和特定格式的浮點(diǎn)數(shù),所以基數(shù)排序也不是只能使用于整數(shù)。基數(shù)排序的發(fā)明可以追溯到1887年赫爾曼·何樂禮在列表機(jī)(Tabulation Machine)上的
基數(shù)排序的方式可以采用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由鍵值的最右邊開始,而MSD則相反,由鍵值的最左邊開始。LSD使用計(jì)數(shù)排序或桶排序,MSD可以使用桶排序。由低到高(LSD)比較簡(jiǎn)單,按位重排即可,如果是從高往低(MSD)則不能每次重排,可以通過遞歸來逐層遍歷實(shí)現(xiàn)。詳細(xì)請(qǐng)看各種不同版本的源碼。
排序算法網(wǎng)上有很多實(shí)現(xiàn),但經(jīng)常有錯(cuò)誤,也缺乏不同語言的比較。本系列把各種排序算法重新整理,用不同語言分別實(shí)現(xiàn)。
實(shí)現(xiàn)過程
- 將待排序數(shù)列(正整數(shù))統(tǒng)一為同樣的數(shù)位長(zhǎng)度,數(shù)位較短的補(bǔ)零。
- 每個(gè)數(shù)位單獨(dú)排序,從最低位到最高位,或從最高位到最低位。
- 這樣從最低到高或從高到低排序完成以后,數(shù)列就變成一個(gè)有序數(shù)列。
示意圖
性能分析
時(shí)間復(fù)雜度:O(k*N)
空間復(fù)雜度:O(k + N)
穩(wěn)定性:穩(wěn)定
代碼
Java
class RadixSort { // 基數(shù)排序,基于計(jì)數(shù)排序,按數(shù)位從低到高來排序 public static int[] countingSort(int arr[], int exponent) { // 基數(shù)exponent按10進(jìn)位,range為10 int range = 10; int[] countList = new int[range]; int[] sortedList = new int[arr.length]; // 設(shè)定最小值以支持負(fù)數(shù) int min = arr[0]; for (int i = 0; i < arr.length; i++) { if (arr[i] < min) { min = arr[i]; } } // 根據(jù)基數(shù)求得當(dāng)前項(xiàng)目對(duì)應(yīng)位置的數(shù)值,并給對(duì)應(yīng)計(jì)數(shù)數(shù)組位置加1 for (int i = 0; i < arr.length; i++) { int item = arr[i] - min; // 根據(jù)exponent獲得當(dāng)前位置的數(shù)字是幾,存入對(duì)應(yīng)計(jì)數(shù)數(shù)組 int idx = (item / exponent) % range; countList[idx] += 1; } // 根據(jù)位置計(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ù)計(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ù)計(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ù)位大小,基于計(jì)數(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ù)最大值,逐個(gè)按進(jìn)位(基數(shù))來應(yīng)用排序,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. 如果桶里的長(zhǎng)度超過1,則通過遞歸繼續(xù)按桶排序。當(dāng)桶里的數(shù)據(jù)只有1位時(shí)添加到原列表對(duì)應(yīng)位置。 // 重復(fù)步驟2和3,直到按照最高位排序完成。 class RadixSortMSD { static int[] radixSort(int[] arr) { int len = arr.length; // 獲取數(shù)組最大項(xiàng) int max = arr[0]; for (int i = 0; i < len; i++) { if (max < arr[i]) { max = arr[i]; } } // 獲取數(shù)組最小項(xiàng) int min = arr[0]; for (int i = 0; i < len; i++) { if (min > arr[i]) { min = arr[i]; } } // 獲取數(shù)字一共有幾位,減去min得到最大值,以支持負(fù)數(shù)和減少最大值 int numberOfDigits = (int) (Math.log10(max - min) + 1); int exponent = (int) (Math.pow(10, numberOfDigits - 1)); // 根據(jù)數(shù)組最大值,自后向前逐個(gè)按數(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ù)組最小項(xiàng) int min = arr[0]; for (int i = 0; i < len; i++) { if (min > arr[i]) { min = arr[i]; } } // 位數(shù)按10遞進(jìn) int range = 10; // 定義桶二維數(shù)組,長(zhǎng)度為10,放入0-9的數(shù)字 int[][] buckets = new int[range][len]; // 記錄某個(gè)桶的最新長(zhǎng)度,以便往桶內(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ù)追加到對(duì)應(yīng)的桶里,減去min是支持負(fù)數(shù) int bucketIdx = (item / exponent) % range; // 把數(shù)據(jù)按下標(biāo)插入到桶里 int numberIndex = bucketsCount[bucketIdx]; buckets[bucketIdx][numberIndex] = arr[i]; bucketsCount[bucketIdx] += 1; } // 將每個(gè)桶的數(shù)據(jù)按順序逐個(gè)取出,重新賦值給原數(shù)組 int sortedIdx = 0; for (int i = 0; i < range; i++) { int[] bucket = buckets[i]; int bucketLen = bucketsCount[i]; // 如果只有一個(gè)值,則直接更新到原數(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í)需要傳入當(dāng)前子序列、子序列長(zhǎng)度、當(dāng)前分解的位數(shù)基數(shù) int[] sortedBucket = bucketSort(bucket, bucketLen, (int) (exponent / range)); // 依照已排序的子序列實(shí)際長(zhǎng)度,把各個(gè)桶里的值按順序賦給原數(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ù)組排序。 重復(fù)步驟2和3,直到排序完成。 """ def radix_sort(arr): max_value = max(arr) # 找出數(shù)組中最大的數(shù) min_value = min(arr) #最小值,為了支持負(fù)數(shù) digit = 1 # 從個(gè)位開始排序 # 每次排序一個(gè)數(shù)位,從低到高直到排序完成 while (max_value - min_value) // digit > 0: # 創(chuàng)建10個(gè)桶,分別對(duì)應(yīng)0-9的數(shù)位值 buckets = [[] for _ in range(10)] for num in arr: # 找出當(dāng)前位數(shù)的值 digit_num = (num - min_value) // digit % 10 # 將數(shù)字添加到對(duì)應(yīng)數(shù)位的桶中,相當(dāng)于根據(jù)數(shù)位排序 buckets[digit_num].append(num) print('buckets:', buckets) # 通過exend展開數(shù)組,相當(dāng)于逐層添加 arr = [] for bucket in buckets: arr.extend(bucket) # 或逐項(xiàng)添加 # for item in bucket: # arr.append(item) # 數(shù)位移動(dòng)到下一位 digit *= 10 return arr
""" 基數(shù)排序,從高到低逐位排序,遞歸方式,基于桶排序。具體步驟如下: 1. 找出數(shù)組中最大的數(shù),確定其位數(shù)。 2. MSD是從高位開始,依次按照位數(shù)的值將數(shù)字放入到不同桶中。 3. 如果桶里的長(zhǎng)度超過1,則通過遞歸繼續(xù)按桶排序。當(dāng)桶里的數(shù)據(jù)只有1位時(shí)添加到原列表對(duì)應(yīng)位置。 重復(fù)步驟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ù)追加到對(duì)應(yīng)的桶里,減去min是支持負(fù)數(shù) bucketIdx = int(item / exponent) % radix # 填充空桶,或者提前填充為列表 if buckets[bucketIdx] is None: buckets[bucketIdx] = [] buckets[bucketIdx].append(arr[i]) print('append to buckets:', buckets) # 將每個(gè)桶的數(shù)據(jù)按順序逐個(gè)取出,重新賦值給原數(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) # 把各個(gè)桶里的值按順序賦給原數(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版,基于桶排序遞歸實(shí)現(xiàn) def radix_sort_msd(arr): # 根據(jù)最大值,逐個(gè)按進(jìn)位(基數(shù))來應(yīng)用排序,從高位到低位。 # 獲取數(shù)字的數(shù)位,這減去min_value是為了支持負(fù)數(shù) # exponent是最大的數(shù)位,由高到低逐位計(jì)算 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版,計(jì)算最小值,基于計(jì)數(shù)排序?qū)崿F(xiàn) func radixSort2(arr []int) []int { var arrLen = len(arr) // 基數(shù)exponent按10進(jìn)位,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ù)求得當(dāng)前項(xiàng)目對(duì)應(yīng)位置的數(shù)值,并給對(duì)應(yīng)計(jì)數(shù)數(shù)組位置加1 // 按最大值補(bǔ)齊數(shù)位,基數(shù)exponent按10進(jìn)位 for exponent := 1; ((max - min) / exponent) > 0; exponent *= amount { // 計(jì)數(shù)數(shù)組,長(zhǎng)度為10,0-9一共10個(gè)數(shù)字 countList := make([]int, amount) // 根據(jù)基數(shù)得到當(dāng)前位數(shù),并給計(jì)數(shù)數(shù)組對(duì)應(yīng)位置加1 for i := 0; i < arrLen; i++ { var item = arr[i] - min var idx = (item / exponent) % amount countList[idx] += 1 } // 計(jì)數(shù)排序構(gòu)建,自前往后,逐個(gè)將上一項(xiàng)的值存入當(dāng)前項(xiàng) for i := 1; i < amount; i++ { countList[i] += countList[i-1] } fmt.Println("radixSort2 -> countList:", countList) // 根據(jù)計(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. 如果桶里的長(zhǎng)度超過1,則通過遞歸繼續(xù)按桶排序。當(dāng)桶里的數(shù)據(jù)只有1位時(shí)添加到原列表對(duì)應(yīng)位置。 // 重復(fù)步驟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) // 增加偏移以便支持負(fù)數(shù) offset := 0 if minValue < 0 { offset = 0 - minValue } // 填充桶二維數(shù)組 for i := 0; i < (amount + offset); i++ { buckets = append(buckets, []int{}) } // 獲取數(shù)組項(xiàng)指定數(shù)位的值,放入到對(duì)應(yīng)桶中,桶的下標(biāo)即順序 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 } // 遞歸遍歷所有的桶,由里而外逐個(gè)桶進(jìn)行排序 sortedBucket := bucketSort(bucket, exponent/amount) // 把各個(gè)桶里的值按順序賦給原數(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 } // 獲取絕對(duì)值 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 } // 計(jì)算數(shù)字次冪 func pow(a int, power int) int { result := 1 for i := 0; i < power; i++ { result *= a } return result } // 獲取數(shù)組項(xiàng)指定數(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ù)位補(bǔ)0,負(fù)數(shù)返回負(fù)數(shù) // 如: 1024, 百位: 100 => 返回 0 // 如: -2048, 千位: 1000 => 返回 -2 func 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,從低到高逐個(gè)數(shù)位對(duì)比排序,基于桶排序,利用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++) { // 每個(gè)數(shù)位準(zhǔn)備10個(gè)空數(shù)組,用于放數(shù)字0-9 const buckets = Array.from({ length: 10 }, () => []) // 遍歷數(shù)組將數(shù)位上的數(shù)放入對(duì)應(yīng)桶里 for (let j = 0, l = arr.length; j < l; j++) { const item = (arr[j] - min) // 從后往前獲取第x位置的數(shù),通過計(jì)算的方式 const num = getDigit(item, i + 1) // 當(dāng)前位數(shù)如果不為空則添加到基數(shù)桶中 if (num !== isNaN) { buckets[num].push((arr[j])) } } // 將桶逐級(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. 如果桶里的長(zhǎng)度超過1,則通過遞歸繼續(xù)按桶排序。當(dāng)桶里的數(shù)據(jù)只有1位時(shí)添加到原列表對(duì)應(yīng)位置。 // 重復(fù)步驟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ù)組,長(zhǎng)度為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ù)追加到對(duì)應(yīng)的桶里,減去min是支持負(fù)數(shù) const bucketIdx = Math.floor(item / exponent % range) // 提前填充空桶或使用時(shí)再填充 if (!buckets[bucketIdx]) { buckets[bucketIdx] = [] } buckets[bucketIdx].push(arr[i]) } // 將每個(gè)桶的數(shù)據(jù)按順序逐個(gè)取出,重新賦值給原數(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)) // 把各個(gè)桶里的值按順序賦給原數(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得到最大值,以支持負(fù)數(shù)和減少最大值 const numberOfDigits = Math.floor(Math.log10(max - min) + 1) const exponent = Math.pow(10, numberOfDigits - 1) // 根據(jù)數(shù)組最大值,自后向前逐個(gè)按數(shù)位基數(shù)(exponent)比較排序。 return bucketSort(arr, exponent) }
TS
class RadixSort { // 基數(shù)排序,基于計(jì)數(shù)排序的基礎(chǔ)上,按數(shù)字的每個(gè)位置來排序 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ù)字的最后一位,并給對(duì)應(yīng)計(jì)數(shù)數(shù)組加1 const idx = Math.floor((item / exponent) % range) countList[idx] += 1 } console.log('countingSort countList:', countList) // 根據(jù)位置計(jì)數(shù),后面的位數(shù)為前面的累加之和 for (let i = 1; i < range; i++) { countList[i] += countList[i - 1] } const sortedList = Array<number>() // 根據(jù)計(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版,基于計(jì)數(shù)排序的基礎(chǔ),支持負(fù)數(shù),按數(shù)字的每個(gè)位置來排序 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
// 計(jì)數(shù)排序,根據(jù)基數(shù)按位進(jìn)行計(jì)數(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ù)字所在位置進(jìn)行計(jì)數(shù) for (int i = 0; i < len; i++) { int item = arr[i] - min_value; int idx = (item / exponent) % range; count_list[idx]++; } // 構(gòu)建計(jì)數(shù)排序,當(dāng)前位置加上左側(cè)位置,后面的位數(shù)為前面的累加之和 for (int i = 1; i < range; i++) { count_list[i] += count_list[i - 1]; } // 構(gòu)建輸出數(shù)組,根據(jù)計(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]--; } // 復(fù)制到數(shù)組重排原始數(shù)組 for (int i = 0; i < len; i++) { arr[i] = sorted_list[i]; } } // 基數(shù)排序,從低位到高位LSD版,基于計(jì)數(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ù)最大值,逐個(gè)按進(jìn)位(基數(shù))來應(yīng)用排序,exponent即數(shù)位基數(shù),按個(gè)十百千遞增。 for (int exponent = 1; (max_value - min_value) / exponent > 0; exponent *= 10) { counting_sort(arr, len, exponent); } return arr; }
// 根據(jù)最大長(zhǎng)度來獲取數(shù)字第n位的值,從前往后開始,前面不足最大長(zhǎng)度時(shí)補(bǔ)零 int get_digit_by_position(int num, int position, int max_length) { if (num == 0) { return 0; } int number_length = (int)log10(num) + 1; // 查詢的位置加上自身長(zhǎng)度不足最大長(zhǎng)度則返回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ù)排序,從高位到逐個(gè)對(duì)比排序,通過桶排序遞歸調(diào)用 // arr是數(shù)組,len是當(dāng)前數(shù)組長(zhǎng)度,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十個(gè)數(shù)字 int buckets[range][len]; for (int i = 0; i < range; i++) { // 此處未提前使用,也可以不設(shè)置默認(rèn)值 memset(buckets[i], 0, len * sizeof(int)); // print_array(buckets[i], len); } // 默認(rèn)填充內(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ù)位上的值,減去最小值,分配到對(duì)應(yīng)的桶里 int bucket_idx = get_digit_by_position(item, position, max_length); // 把數(shù)據(jù)按下標(biāo)插入到桶里 int number_idx = bucket_count_list[bucket_idx]; buckets[bucket_idx][number_idx] = arr[i]; bucket_count_list[bucket_idx] += 1; } // 將每個(gè)桶的數(shù)據(jù)按順序逐個(gè)取出,重新賦值給原數(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]); // 如果只有一個(gè)值,則直接更新到原數(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í)需要傳入當(dāng)前子序列、子序列長(zhǎng)度、當(dāng)前分解的位數(shù)基數(shù) int *sorted_bucket = bucket_sort(bucket, bucket_len, position + 1, max_length); // 依照已排序的子序列實(shí)際長(zhǎng)度,把各個(gè)桶里的值按順序賦給原數(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; } // 計(jì)數(shù)排序,根據(jù)數(shù)字的位置逐個(gè)對(duì)比排序,從高到低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]; } // 獲取最小項(xiàng) int min_value = arr[0]; for (int i = 0; i < len; i++) { if (min_value > arr[i]) { min_value = arr[i]; } } // 獲取數(shù)字一共有幾位,減去min得到最大值,以支持負(fù)數(shù)和減少最大值 int max_length = (int)(log10(max_value - min_value) + 1); // 根據(jù)數(shù)組最大值的長(zhǎng)度,從前往后逐個(gè)對(duì)比排序。 return bucket_sort(arr, len, 1, max_length); }
C++
// 基數(shù)排序,從個(gè)位到高位LSD版,基于計(jì)數(shù)排序?qū)崿F(xiàn) int *radixSort(int *arr, int len) { // 以10倍遞進(jìn) 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ù)最大值,逐個(gè)按進(jìn)位(基數(shù))來應(yīng)用排序,exponent即基數(shù)。 for (int exponent = 1; ((max - min) / exponent) > 0; exponent *= range) { // 計(jì)數(shù)數(shù)組,長(zhǎng)度為10,0-9一共10個(gè)數(shù)字 int countList[range]; memset(countList, 0, range * sizeof(int)); // 根據(jù)基數(shù)得到當(dāng)前位數(shù),并給計(jì)數(shù)數(shù)組對(duì)應(yīng)位置加1 for (int i = 0; i < len; i++) { int item = arr[i] - min; int idx = (item / exponent) % range; countList[idx] += 1; } // 計(jì)數(shù)排序構(gòu)建,自前往后,逐個(gè)將上一項(xiàng)的值存入當(dāng)前項(xiàng) for (int i = 1; i < range; i++) { countList[i] += countList[i - 1]; } // 根據(jù)計(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; } // 復(fù)制輸出數(shù)組到原始數(shù)組 for (int i = 0; i < len; i++) { arr[i] = sortedList[i]; } } return arr; }
鏈接
基數(shù)排序與計(jì)數(shù)排序、桶排序區(qū)別
基數(shù)排序與計(jì)數(shù)排序、桶排序三者概念很像,但也有不同,其主要差異如下:
計(jì)數(shù)排序:根據(jù)數(shù)組值設(shè)定若干個(gè)桶,每個(gè)桶對(duì)應(yīng)一個(gè)數(shù)值,將這些桶的值分別存入下一個(gè)桶中用于排序,最后按順序取出對(duì)應(yīng)桶里的值。
桶排序:根據(jù)情況分為若干個(gè)桶,每個(gè)桶存儲(chǔ)一定范圍的數(shù)值,每個(gè)桶再單獨(dú)排序,最后按桶的順序取出全部數(shù)據(jù)。
基數(shù)排序:根據(jù)數(shù)據(jù)的位數(shù)來分配桶,每一位對(duì)應(yīng)一個(gè)桶,先將全部數(shù)據(jù)的位數(shù)按最大位數(shù)對(duì)齊,再根據(jù)位數(shù)上的值大小排列?;鶖?shù)排序基于計(jì)數(shù)排序或者桶排序。
基數(shù)排序算法源碼:https://github.com/microwind/algorithms/tree/master/sorts/radixsort
其他排序算法源碼:https://github.com/microwind/algorithms
以上就是基數(shù)排序算法的原理與實(shí)現(xiàn)詳解(Java/Go/Python/JS/C)的詳細(xì)內(nèi)容,更多關(guān)于基數(shù)排序算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
UUencode 編碼,UU編碼介紹、UUencode編碼轉(zhuǎn)換原理與算法
這篇文章主要介紹了UUencode 編碼,UU編碼介紹、UUencode編碼轉(zhuǎn)換原理與算法,需要的朋友可以參考下2016-06-06一文教你在現(xiàn)有Vue項(xiàng)目中嵌入Blazor項(xiàng)目
目前官方只提供了angular和react倆種示例,所以本教程將來講解如何在Vue的現(xiàn)有項(xiàng)目中嵌入使用Blazor項(xiàng)目。文中的方法講解詳細(xì),感興趣的小伙伴可以了解一下2023-01-01在小程序中實(shí)現(xiàn)ChatGPT?聊天打字兼自動(dòng)滾動(dòng)效果
ChatGPT已經(jīng)長(zhǎng)時(shí)間大火,未來將會(huì)是AI的天下,們需要更多地學(xué)習(xí)和掌握AI,而不是被AI所取代,在?ChatGPT?的背景下,我們今天來聊聊在小程序中怎么實(shí)現(xiàn)類似?chatGPT?的聊天打字效果,并且實(shí)現(xiàn)滾動(dòng)效果2023-06-06詳解git submodule HEAD detached 的問題
這篇文章主要介紹了詳解git submodule HEAD detached 的問題,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-08-08