欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

基數(shù)排序算法的原理與實(shí)現(xiàn)詳解(Java/Go/Python/JS/C)

 更新時(shí)間:2023年03月06日 10:34:28   作者:刀法如飛  
基數(shù)排序(RadixSort)是一種非比較型整數(shù)排序算法,其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字,然后按每個(gè)位數(shù)分別比較。本文將利用Java/Go/Python/JS/C不同語言實(shí)現(xiàn)基數(shù)排序算法,感興趣的可以了解一下

說明

基數(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)文章

  • Webstorm開發(fā)工具使用教程詳解

    Webstorm開發(fā)工具使用教程詳解

    這篇文章主要為大家詳細(xì)介紹了Webstorm使用教程的使用教程,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-09-09
  • UltraEdit編輯器免費(fèi)激活方法

    UltraEdit編輯器免費(fèi)激活方法

    UltraEdit?是一套功能強(qiáng)大的文本編輯器,可以編輯文本、十六進(jìn)制、ASCII?碼,完全可以取代記事本,下面小編把這款UltraEdit編輯器免費(fèi)激活方法分享給大家,需要的朋友參考下
    2021-08-08
  • UUencode 編碼,UU編碼介紹、UUencode編碼轉(zhuǎn)換原理與算法

    UUencode 編碼,UU編碼介紹、UUencode編碼轉(zhuǎn)換原理與算法

    這篇文章主要介紹了UUencode 編碼,UU編碼介紹、UUencode編碼轉(zhuǎn)換原理與算法,需要的朋友可以參考下
    2016-06-06
  • Xmind用例導(dǎo)入到TAPD的解決方案

    Xmind用例導(dǎo)入到TAPD的解決方案

    這篇文章主要介紹了Xmind用例導(dǎo)入到TAPD的方案,大家都知道XMind2TestCase?,該工具基于?Python?實(shí)現(xiàn),通過制定測(cè)試用例通用模板,然后使用?XMind?這款廣為流傳且開源的思維導(dǎo)圖工具進(jìn)行用例設(shè)計(jì),需要的朋友可以參考下
    2022-07-07
  • 一文教你在現(xiàn)有Vue項(xiàng)目中嵌入Blazor項(xiàng)目

    一文教你在現(xiàn)有Vue項(xiàng)目中嵌入Blazor項(xiàng)目

    目前官方只提供了angular和react倆種示例,所以本教程將來講解如何在Vue的現(xiàn)有項(xiàng)目中嵌入使用Blazor項(xiàng)目。文中的方法講解詳細(xì),感興趣的小伙伴可以了解一下
    2023-01-01
  • vscode的幾項(xiàng)基本配置詳解

    vscode的幾項(xiàng)基本配置詳解

    VSCode是一款免費(fèi)的、開源的、高性能的、跨平臺(tái)的、輕量級(jí)的代碼編輯器,這篇文章主要介紹了vscode的幾項(xiàng)基本配置,本文給大家介紹的非常詳細(xì),感興趣的朋友跟隨小編一起看看吧
    2020-05-05
  • 在小程序中實(shí)現(xiàn)ChatGPT?聊天打字兼自動(dòng)滾動(dòng)效果

    在小程序中實(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
  • 利用二進(jìn)制文件安裝etcd的教程詳解

    利用二進(jìn)制文件安裝etcd的教程詳解

    etcd組件作為一個(gè)高可用強(qiáng)一致性的服務(wù)發(fā)現(xiàn)存儲(chǔ)倉(cāng)庫.這篇文章主要介紹了利用二進(jìn)制文件安裝etcd的教程詳解,需要的朋友可以參考下
    2019-08-08
  • 詳解git submodule HEAD detached 的問題

    詳解git submodule HEAD detached 的問題

    這篇文章主要介紹了詳解git submodule HEAD detached 的問題,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-08-08
  • C1任務(wù)01之修改游戲存檔的方法

    C1任務(wù)01之修改游戲存檔的方法

    這篇文章主要介紹了C1任務(wù)01之修改游戲存檔的相關(guān)知識(shí),前三個(gè)任務(wù)會(huì)用到十六進(jìn)制編輯器來實(shí)現(xiàn),在修改的的過程中涉及到的知識(shí)點(diǎn)為十進(jìn)制數(shù)據(jù)與十六進(jìn)制之間數(shù)據(jù)的相互轉(zhuǎn)換,需要的朋友可以參考下
    2021-10-10

最新評(píng)論