您好,登錄后才能下訂單哦!
這篇文章主要介紹“Java/Go/Python/JS/C基數(shù)排序算法的原理與實現(xiàn)方法是什么”的相關知識,小編通過實際案例向大家展示操作過程,操作方法簡單快捷,實用性強,希望這篇“Java/Go/Python/JS/C基數(shù)排序算法的原理與實現(xiàn)方法是什么”文章能幫助大家解決問題。
基數(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)。
將待排序數(shù)列(正整數(shù))統(tǒng)一為同樣的數(shù)位長度,數(shù)位較短的補零。
每個數(shù)位單獨排序,從最低位到最高位,或從最高位到最低位。
這樣從最低到高或從高到低排序完成以后,數(shù)列就變成一個有序數(shù)列。
時間復雜度:O(k*N)
空間復雜度:O(k + N)
穩(wěn)定性:穩(wěn)定
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ù) 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ù)排序實現(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; }
""" 基數(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) # 構建排序的桶二維列表 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))
// 2. 基數(shù)排序LSD版,計算最小值,基于計數(shù)排序實現(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ù)排序構建,自前往后,逐個將上一項的值存入當前項 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 => 返回 -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 }
// 基數(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) }
class RadixSort { // 基數(shù)排序,基于計數(shù)排序的基礎上,按數(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ù)排序的基礎,支持負數(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 } }
// 計數(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]++; } // 構建計數(shù)排序,當前位置加上左側位置,后面的位數(shù)為前面的累加之和 for (int i = 1; i < range; i++) { count_list[i] += count_list[i - 1]; } // 構建輸出數(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ù)位置重排結果,減去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++) { // 此處未提前使用,也可以不設置默認值 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); }
// 基數(shù)排序,從個位到高位LSD版,基于計數(shù)排序實現(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ù)排序構建,自前往后,逐個將上一項的值存入當前項 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ù)值,將這些桶的值分別存入下一個桶中用于排序,最后按順序取出對應桶里的值。
桶排序:根據(jù)情況分為若干個桶,每個桶存儲一定范圍的數(shù)值,每個桶再單獨排序,最后按桶的順序取出全部數(shù)據(jù)。
基數(shù)排序:根據(jù)數(shù)據(jù)的位數(shù)來分配桶,每一位對應一個桶,先將全部數(shù)據(jù)的位數(shù)按最大位數(shù)對齊,再根據(jù)位數(shù)上的值大小排列?;鶖?shù)排序基于計數(shù)排序或者桶排序。
關于“Java/Go/Python/JS/C基數(shù)排序算法的原理與實現(xiàn)方法是什么”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關的知識,可以關注億速云行業(yè)資訊頻道,小編每天都會為大家更新不同的知識點。
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權內(nèi)容。