基数排序算法的原理与实现详解(Java/Go/Python/JS/C)

目录
  • 说明
  • 实现过程
  • 示意图
  • 性能分析
  • 代码
    • Java
    • Python
    • Go
    • JS
    • TS
    • C
    • C++
  • 链接

说明

基数排序(RadixSort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在列表机(Tabulation Machine)上的

基数排序的方式可以采用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始。LSD使用计数排序或桶排序,MSD可以使用桶排序。由低到高(LSD)比较简单,按位重排即可,如果是从高往低(MSD)则不能每次重排,可以通过递归来逐层遍历实现。详细请看各种不同版本的源码。

排序算法网上有很多实现,但经常有错误,也缺乏不同语言的比较。本系列把各种排序算法重新整理,用不同语言分别实现。

实现过程

  • 将待排序数列(正整数)统一为同样的数位长度,数位较短的补零。
  • 每个数位单独排序,从最低位到最高位,或从最高位到最低位。
  • 这样从最低到高或从高到低排序完成以后,数列就变成一个有序数列。

示意图

性能分析

时间复杂度:O(k*N)

空间复杂度:O(k + N)

稳定性:稳定

代码

Java

class RadixSort {

  // 基数排序,基于计数排序,按数位从低到高来排序
  public static int[] countingSort(int arr[], int exponent) {
    // 基数exponent按10进位,range为10
    int range = 10;
    int[] countList = new int[range];
    int[] sortedList = new int[arr.length];

    // 设定最小值以支持负数
    int min = arr[0];
    for (int i = 0; i < arr.length; i++) {
      if (arr[i] < min) {
        min = arr[i];
      }
    }

    // 根据基数求得当前项目对应位置的数值,并给对应计数数组位置加1
    for (int i = 0; i < arr.length; i++) {
      int item = arr[i] - min;
      // 根据exponent获得当前位置的数字是几,存入对应计数数组
      int idx = (item / exponent) % range;
      countList[idx] += 1;
    }

    // 根据位置计数,后面的位数为前面的累加之和
    for (int i = 1; i < range; i++) {
      countList[i] += countList[i - 1];
    }
    System.out.println("radixSort1 countingSort countList:" + Arrays.toString(countList));

    // 根据计数数组按顺序取出排序内容
    for (int i = arr.length - 1; i >= 0; i--) {
      int item = arr[i] - min;
      int idx = (item / exponent) % range;
      // 根据计数位置得到顺序
      sortedList[countList[idx] - 1] = arr[i];
      countList[idx] -= 1;
    }

    // 最后赋值给原数据
    for (int i = 0; i < arr.length; i++) {
      arr[i] = sortedList[i];
    }
    System.out.println("radixSort1 -> sortedList:" + Arrays.toString(sortedList));
    return sortedList;
  }

  // 基数排序1,按数位大小,基于计数排序实现
  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];
      }
    }
    // 根据最大值,逐个按进位(基数)来应用排序,exponent即数位。
    for (int exponent = 1; (max / exponent) > 0; exponent *= 10) {
      countingSort(arr, exponent);
    }
    return arr;
  }
}
// 基数排序,从高到低逐位排序,递归方式,基于桶排序。具体步骤如下:
// 1. 找出数组中最大的数,确定其位数。
// 2. MSD是从高位开始,依次按照位数的值将数字放入到不同桶中。
// 3. 如果桶里的长度超过1,则通过递归继续按桶排序。当桶里的数据只有1位时添加到原列表对应位置。
// 重复步骤2和3,直到按照最高位排序完成。
class RadixSortMSD {
  static int[] radixSort(int[] arr) {
    int len = arr.length;
    // 获取数组最大项
    int max = arr[0];
    for (int i = 0; i < len; i++) {
      if (max < arr[i]) {
        max = arr[i];
      }
    }

    // 获取数组最小项
    int min = arr[0];
    for (int i = 0; i < len; i++) {
      if (min > arr[i]) {
        min = arr[i];
      }
    }

    // 获取数字一共有几位,减去min得到最大值,以支持负数和减少最大值
    int numberOfDigits = (int) (Math.log10(max - min) + 1);
    int exponent = (int) (Math.pow(10, numberOfDigits - 1));
    // 根据数组最大值,自后向前逐个按数位基数(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;
    }

    // 获取数组最小项
    int min = arr[0];
    for (int i = 0; i < len; i++) {
      if (min > arr[i]) {
        min = arr[i];
      }
    }

    // 位数按10递进
    int range = 10;
    // 定义桶二维数组,长度为10,放入0-9的数字
    int[][] buckets = new int[range][len];
    // 记录某个桶的最新长度,以便往桶内追加数据。
    int[] bucketsCount = new int[range];
    for (int i = 0; i < len; i++) {
      int item = arr[i] - min;
      // 根据数位上的值,把数据追加到对应的桶里,减去min是支持负数
      int bucketIdx = (item / exponent) % range;
      // 把数据按下标插入到桶里
      int numberIndex = bucketsCount[bucketIdx];
      buckets[bucketIdx][numberIndex] = arr[i];
      bucketsCount[bucketIdx] += 1;
    }

    // 将每个桶的数据按顺序逐个取出,重新赋值给原数组
    int sortedIdx = 0;

    for (int i = 0; i < range; i++) {
      int[] bucket = buckets[i];
      int bucketLen = bucketsCount[i];
      // 如果只有一个值,则直接更新到原数组
      if (bucketsCount[i] == 1) {
        arr[sortedIdx] = bucket[0];
        sortedIdx += 1;
      } else if (bucket.length > 0 && bucketLen > 0) {
        // 如果是数组且记录大于1则继续递归调用,位数降低1位
        // 递归调用传参时需要传入当前子序列、子序列长度、当前分解的位数基数
        int[] sortedBucket = bucketSort(bucket, bucketLen, (int) (exponent / range));
        // 依照已排序的子序列实际长度,把各个桶里的值按顺序赋给原数组
        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

"""
基数排序LSD版,本基于桶排序。
1. 找出数组中最大的数,确定其位数。
2. LSD是低位到高位,依次按照位数的值将数字放入到不同桶中。
3. 按照桶顺序重新给数组排序。
重复步骤2和3,直到排序完成。
"""
def radix_sort(arr):
    max_value = max(arr)  # 找出数组中最大的数
    min_value = min(arr)  #最小值,为了支持负数
    digit = 1  # 从个位开始排序

    # 每次排序一个数位,从低到高直到排序完成
    while (max_value - min_value) // digit > 0:
        # 创建10个桶,分别对应0-9的数位值
        buckets = [[] for _ in range(10)]
        for num in arr:
            # 找出当前位数的值
            digit_num = (num - min_value) // digit % 10
            # 将数字添加到对应数位的桶中,相当于根据数位排序
            buckets[digit_num].append(num)

        print('buckets:', buckets)

        # 通过exend展开数组,相当于逐层添加
        arr = []
        for bucket in buckets:
            arr.extend(bucket)
            # 或逐项添加
            # for item in bucket:
            #     arr.append(item)

        # 数位移动到下一位
        digit *= 10

    return arr
"""
基数排序,从高到低逐位排序,递归方式,基于桶排序。具体步骤如下:
1. 找出数组中最大的数,确定其位数。
2. MSD是从高位开始,依次按照位数的值将数字放入到不同桶中。
3. 如果桶里的长度超过1,则通过递归继续按桶排序。当桶里的数据只有1位时添加到原列表对应位置。
重复步骤2和3,直到按照最高位排序完成。
"""
# 桶排序,根据数位递归调用
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
        # 根据数位上的值,把数据追加到对应的桶里,减去min是支持负数
        bucketIdx = int(item / exponent) % radix
        # 填充空桶,或者提前填充为列表
        if buckets[bucketIdx] is None:
            buckets[bucketIdx] = []
        buckets[bucketIdx].append(arr[i])

    print('append to buckets:', buckets)

    # 将每个桶的数据按顺序逐个取出,重新赋值给原数组
    sortedIdx = 0
    for i in range(radix):
        bucket = buckets[i]
        if bucket is None or len(bucket) < 1:
            continue
        # 如果是数组则继续递归调用,位数降低1位
        sortedBucket = bucket_sort(bucket, exponent // amount)
        # 把各个桶里的值按顺序赋给原数组
        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

# 基数排序,从高到低逐位排序MSD版,基于桶排序递归实现
def radix_sort_msd(arr):
    # 根据最大值,逐个按进位(基数)来应用排序,从高位到低位。
    # 获取数字的数位,这减去min_value是为了支持负数
    # exponent是最大的数位,由高到低逐位计算
    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. 基数排序LSD版,计算最小值,基于计数排序实现
func radixSort2(arr []int) []int {
  var arrLen = len(arr)
  // 基数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]
    }
  }

  // 根据基数求得当前项目对应位置的数值,并给对应计数数组位置加1
  // 按最大值补齐数位,基数exponent按10进位
  for exponent := 1; ((max - min) / exponent) > 0; exponent *= amount {

    // 计数数组,长度为10,0-9一共10个数字
    countList := make([]int, amount)
    // 根据基数得到当前位数,并给计数数组对应位置加1
    for i := 0; i < arrLen; i++ {
      var item = arr[i] - min
      var idx = (item / exponent) % amount
      countList[idx] += 1
    }

    // 计数排序构建,自前往后,逐个将上一项的值存入当前项
    for i := 1; i < amount; i++ {
      countList[i] += countList[i-1]
    }

    fmt.Println("radixSort2 -> countList:", countList)

    // 根据计数数组按顺序取出排序内容
    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
    }

    // 将新顺序赋值给原数组
    for i := 0; i < arrLen; i++ {
      arr[i] = sortedList[i]
    }
  }

  return arr
}
// 基数排序,从高到低逐位排序,递归方式,基于桶排序。具体步骤如下:
// 1. 找出数组中最大的数,确定其位数。
// 2. MSD是从高位开始,依次按照位数的值将数字放入到不同桶中。
// 3. 如果桶里的长度超过1,则通过递归继续按桶排序。当桶里的数据只有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{}
  // 按数位来获取最小值
  minValue := getMinValue(arr, exponent)

  // 增加偏移以便支持负数
  offset := 0
  if minValue < 0 {
    offset = 0 - minValue
  }

  // 填充桶二维数组
  for i := 0; i < (amount + offset); i++ {
    buckets = append(buckets, []int{})
  }

  // 获取数组项指定数位的值,放入到对应桶中,桶的下标即顺序
  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)
    // 把各个桶里的值按顺序赋给原数组
    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
}

// 获取数字位数
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
}

// 获取数组最大值
func max(arr []int) int {
  maxValue := arr[0]
  for i := 1; i < len(arr); i++ {
    if arr[i] > maxValue {
      maxValue = arr[i]
    }
  }
  return maxValue
}

// 计算数字次幂
func pow(a int, power int) int {
  result := 1
  for i := 0; i < power; i++ {
    result *= a
  }
  return result
}

// 获取数组项指定数位的最小值
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
}

// 获取数字指定数位的值,超出数位补0,负数返回负数
// 如: 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

// 基数排序2,从低到高逐个数位对比排序,基于桶排序,利用JS数组展开来还原数组
function radixSort2(arr) {

  // 倒数获取数字指定位置的数
  function getDigit(num, position) {
    const digit = Math.floor(num / Math.pow(10, position - 1)) % 10
    return digit
  }

  // 获取数组最大数字的位数
  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++) {
    // 每个数位准备10个空数组,用于放数字0-9
    const buckets = Array.from({
      length: 10
    }, () => [])

    // 遍历数组将数位上的数放入对应桶里
    for (let j = 0, l = arr.length; j < l; j++) {
      const item = (arr[j] - min)

      // 从后往前获取第x位置的数,通过计算的方式
      const num = getDigit(item, i + 1)
      // 当前位数如果不为空则添加到基数桶中
      if (num !== isNaN) {
        buckets[num].push((arr[j]))
      }
    }

    // 将桶逐级展开取出数字,如果支持flat则直接使用数组的flat()
    if (buckets.flat) {
      arr = buckets.flat()
    } else {
      // 定定义数组展开函数
      // arr = flat(buckets)
    }
  }

  return arr
}
// 基数排序,从高到低逐位排序,递归方式,基于桶排序。具体步骤如下:
// 1. 找出数组中最大的数,确定其位数。
// 2. MSD是从高位开始,依次按照位数的值将数字放入到不同桶中。
// 3. 如果桶里的长度超过1,则通过递归继续按桶排序。当桶里的数据只有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

    // 定义桶二维数组,长度为10,放入0-9的数字
    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
      // 根据数位上的值,把数据追加到对应的桶里,减去min是支持负数
      const bucketIdx = Math.floor(item / exponent % range)
      // 提前填充空桶或使用时再填充
      if (!buckets[bucketIdx]) {
        buckets[bucketIdx] = []
      }
      buckets[bucketIdx].push(arr[i])
    }

    // 将每个桶的数据按顺序逐个取出,重新赋值给原数组
    let sortedIdx = 0

    for (let i = 0; i < range; i++) {
      const bucket = buckets[i]
      if (bucket && bucket.length > 0) {
        // 如果是数组则继续递归调用,位数降低1位
        const sortedBucket = bucketSort(bucket, Math.floor(exponent / range))
        // 把各个桶里的值按顺序赋给原数组
        sortedBucket.forEach(num => {
          arr[sortedIdx] = num
          sortedIdx += 1
        })
      }
    }

    return arr
  }

  const max = Math.max.apply(null, arr)
  const min = Math.min.apply(null, arr)
  // 获取数字一共有几位,减去min得到最大值,以支持负数和减少最大值
  const numberOfDigits = Math.floor(Math.log10(max - min) + 1)
  const exponent = Math.pow(10, numberOfDigits - 1)
  // 根据数组最大值,自后向前逐个按数位基数(exponent)比较排序。
  return bucketSort(arr, exponent)
}

TS

class RadixSort {
  // 基数排序,基于计数排序的基础上,按数字的每个位置来排序
  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
      // 取得数字的最后一位,并给对应计数数组加1
      const idx = Math.floor((item / exponent) % range)
      countList[idx] += 1
    }
    console.log('countingSort countList:', countList)

    // 根据位置计数,后面的位数为前面的累加之和
    for (let i = 1; i < range; i++) {
      countList[i] += countList[i - 1]
    }

    const sortedList = Array<number>()
    // 根据计数数组按顺序取出排序内容
    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
    }

    // 最后赋值给原数据
    for (let i = 0; i < arr.length; i++) {
      arr[i] = sortedList[i]
    }
    return sortedList
  }

  // 基数排序LSD版,基于计数排序的基础,支持负数,按数字的每个位置来排序
  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

// 计数排序,根据基数按位进行计数
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));
  // 根据数字所在位置进行计数
  for (int i = 0; i < len; i++)
  {
    int item = arr[i] - min_value;
    int idx = (item / exponent) % range;
    count_list[idx]++;
  }

  // 构建计数排序,当前位置加上左侧位置,后面的位数为前面的累加之和
  for (int i = 1; i < range; i++)
  {
    count_list[i] += count_list[i - 1];
  }

  // 构建输出数组,根据计数数组按顺序取得排序内容
  for (int i = len - 1; i >= 0; i--)
  {
    int item = arr[i] - min_value;
    int idx = (item / exponent) % range;
    // 根据位置重排结果,减去min值还原数据
    sorted_list[count_list[idx] - 1] = arr[i];
    count_list[idx]--;
  }

  // 复制到数组重排原始数组
  for (int i = 0; i < len; i++)
  {
    arr[i] = sorted_list[i];
  }
}

// 基数排序,从低位到高位LSD版,基于计数排序
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];
  }

  // 根据最大值,逐个按进位(基数)来应用排序,exponent即数位基数,按个十百千递增。
  for (int exponent = 1; (max_value - min_value) / exponent > 0; exponent *= 10)
  {
    counting_sort(arr, len, exponent);
  }

  return arr;
}
// 根据最大长度来获取数字第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;
}

// 基数排序,从高位到逐个对比排序,通过桶排序递归调用
// arr是数组,len是当前数组长度,position为自前往后的位置,max_length是最大值的数位
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十个数字
  int buckets[range][len];
  for (int i = 0; i < range; i++)
  {
    // 此处未提前使用,也可以不设置默认值
    memset(buckets[i], 0, len * sizeof(int));
    // print_array(buckets[i], len);
  }

  // 默认填充内容为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;
    // 根据数位上的值,减去最小值,分配到对应的桶里
    int bucket_idx = get_digit_by_position(item, position, max_length);
    // 把数据按下标插入到桶里
    int number_idx = bucket_count_list[bucket_idx];
    buckets[bucket_idx][number_idx] = arr[i];
    bucket_count_list[bucket_idx] += 1;
  }

  // 将每个桶的数据按顺序逐个取出,重新赋值给原数组
  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]);
    // 如果只有一个值,则直接更新到原数组
    if (bucket_count_list[i] == 1)
    {
      arr[sorted_idx] = bucket[0];
      sorted_idx += 1;
    }
    else if (bucket_size > 0 && bucket_len > 0)
    {
      // 如果是数组且记录追加大于1则继续递归调用,位置增加1位
      // 递归调用传参时需要传入当前子序列、子序列长度、当前分解的位数基数
      int *sorted_bucket = bucket_sort(bucket, bucket_len, position + 1, max_length);
      // 依照已排序的子序列实际长度,把各个桶里的值按顺序赋给原数组
      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;
}

// 计数排序,根据数字的位置逐个对比排序,从高到低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];
    }
  }
  // 获取数字一共有几位,减去min得到最大值,以支持负数和减少最大值
  int max_length = (int)(log10(max_value - min_value) + 1);
  // 根据数组最大值的长度,从前往后逐个对比排序。
  return bucket_sort(arr, len, 1, max_length);
}

C++

// 基数排序,从个位到高位LSD版,基于计数排序实现
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];
    }
  }

  // 根据最大值,逐个按进位(基数)来应用排序,exponent即基数。
  for (int exponent = 1; ((max - min) / exponent) > 0; exponent *= range)
  {

    // 计数数组,长度为10,0-9一共10个数字
    int countList[range];
    memset(countList, 0, range * sizeof(int));
    // 根据基数得到当前位数,并给计数数组对应位置加1
    for (int i = 0; i < len; i++)
    {
      int item = arr[i] - min;
      int idx = (item / exponent) % range;
      countList[idx] += 1;
    }

    // 计数排序构建,自前往后,逐个将上一项的值存入当前项
    for (int i = 1; i < range; i++)
    {
      countList[i] += countList[i - 1];
    }

    // 根据计数数组按顺序取出排序内容
    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;
    }

    // 复制输出数组到原始数组
    for (int i = 0; i < len; i++)
    {
      arr[i] = sortedList[i];
    }
  }

  return arr;
}

链接

基数排序与计数排序、桶排序区别

基数排序与计数排序、桶排序三者概念很像,但也有不同,其主要差异如下:

计数排序:根据数组值设定若干个桶,每个桶对应一个数值,将这些桶的值分别存入下一个桶中用于排序,最后按顺序取出对应桶里的值。

桶排序:根据情况分为若干个桶,每个桶存储一定范围的数值,每个桶再单独排序,最后按桶的顺序取出全部数据。

基数排序:根据数据的位数来分配桶,每一位对应一个桶,先将全部数据的位数按最大位数对齐,再根据位数上的值大小排列。基数排序基于计数排序或者桶排序。

基数排序算法源码:https://github.com/microwind/algorithms/tree/master/sorts/radixsort

其他排序算法源码:https://github.com/microwind/algorithms

以上就是基数排序算法的原理与实现详解(Java/Go/Python/JS/C)的详细内容,更多关于基数排序算法的资料请关注我们其它相关文章!

(0)

相关推荐

  • python简单实现基数排序算法

    本文实例讲述了python简单实现基数排序算法.分享给大家供大家参考.具体实现方法如下: from random import randint def main(): A = [randint(1, 99999999) for _ in xrange(9999)] for k in xrange(8): S = [ [] for _ in xrange(10)] for j in A: S[j / (10 ** k) % 10].append(j) A = [a for b in S for a

  • python算法学习之基数排序实例

    基数排序法又称桶子法(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些"桶"中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的比较性排序法. 复制代码 代码如下: # -*- coding: utf-8 -*- def _counting_sort(A, i):    """计数排序,以i

  • JS使用队列对数组排列,基数排序算法示例

    本文实例讲述了JS使用队列对数组排列,基数排序算法.分享给大家供大家参考,具体如下: /* * 使用队列对数组排列,基数排序 *对于0~99的数字,基数排序将数组集扫描两次. * 第一次按个位上的数字进行排序, * 第二次按十位上的数字进行排序 * */ function Queue(){ this.dataStore = [];//存放队列的数组,初始化为空 this.enqueue = enqueue;//向队列尾部添加一个元素 this.dequeue = dequeue;//删除队首的元

  • JAVA十大排序算法之基数排序详解

    目录 基数排序 代码实现 时间复杂度 算法稳定性 基数排序 vs 桶排序 vs 计数排序 总结 基数排序 常见的数据元素一般是由若干位组成的,比如字符串由若干字符组成,整数由若干位0~9数字组成. 基数排序按照从右往左的顺序,依次将每一位都当做一次关键字,然后按照该关键字对数组排序,同时每一轮排序都基于上轮排序后的结果:当我们将所有的位排序后,整个数组就达到有序状态.基数排序不是基于比较的算法. 基数是什么意思?对于十进制整数,每一位都只可能是0~9中的某一个,总共10种可能.那10就是它的基,

  • python计数排序和基数排序算法实例

    一.计数排序 计数排序(Counting sort)是一种稳定的排序算法 算法的步骤如下:找出待排序的数组中最大和最小的元素统计数组中每个值为i的元素出现的次数,存入数组C的第i项对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1当输入的元素是 n 个 0 到 k 之间的整数时,计数排序的时间复杂度为O(N+K),空间复杂度为O(N+K).当K不是很大时,这是一个很有效的线性排序算法. 以下是测试代

  • Python数据结构与算法之常见的分配排序法示例【桶排序与基数排序】

    本文实例讲述了Python数据结构与算法之常见的分配排序法.分享给大家供大家参考,具体如下: 箱排序(桶排序) 箱排序是根据关键字的取值范围1~m,预先建立m个箱子,箱排序要求关键字类型为有限类型,可能会有无限个箱子,实用价值不大,一般用于基数排序的中间过程. 桶排序是箱排序的实用化变种,其对数据集的范围,如[0,1) 进行划分为n个大小相同的子区间,每一个子区间为一个桶,然后将n非记录分配到各桶中.因为关键字序列是均匀分布在[0,1)上的,所以一般不会有很多记录落入同一个桶中. 以下的桶排序方

  • 基数排序算法的原理与实现详解(Java/Go/Python/JS/C)

    目录 说明 实现过程 示意图 性能分析 代码 Java Python Go JS TS C C++ 链接 说明 基数排序(RadixSort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较.由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数.基数排序的发明可以追溯到1887年赫尔曼·何乐礼在列表机(Tabulation Machine)上的 基数排序的方式可以采用LSD(Least significant di

  • Java中Prime算法的原理与实现详解

    目录 Prim算法介绍 1.点睛 2.算法介绍 3. 算法步骤 4.图解 Prime 算法实现 1.构建后的图 2.代码 3.测试 Prim算法介绍 1.点睛 在生成树的过程中,把已经在生成树中的节点看作一个集合,把剩下的节点看作另外一个集合,从连接两个集合的边中选择一条权值最小的边即可. 2.算法介绍 首先任选一个节点,例如节点1,把它放在集合 U 中,U={1},那么剩下的节点为 V-U={2,3,4,5,6,7},集合 V 是图的所有节点集合. 现在只需要看看连接两个集合(U 和 V-U)

  • Matlab中图像数字水印算法的原理与实现详解

    目录 一.背景意义 二.基本原理 三.算法介绍 3.1 数字水印嵌入 3.2 数字水印提取 四.程序实现 一.背景意义 数字水印技术作为信息隐藏技术的一个重要分支,是将信息(水印)隐藏于数字图像.视频.音频及文本文档等数字媒体中,从而实现隐秘传输.存储.标注.身份识别.版权保护和防篡改等目的. 随着 1996 年第一届信息隐藏国际学术研讨会的召开,数字水印技术的研究得到了迅速的发展,不少政府机构和研究部门加大了对其的研究力度,其中包括美国财政部.美国版权工作组.美国洛斯阿莫斯国家实验室.美国海陆

  • 详解java调用python的几种用法(看这篇就够了)

    java调用python的几种用法如下: 在java类中直接执行python语句 在java类中直接调用本地python脚本 使用Runtime.getRuntime()执行python脚本文件(推荐) 调用python脚本中的函数 准备工作: 创建maven工程,结构如下: 到官网https://www.jython.org/download.html下载Jython的jar包或者在maven的pom.xml文件中加入如下代码: <dependency> <groupId>org

  • 详解Java Bellman-Ford算法原理及实现

    目录 一 点睛 二 算法步骤 三 算法实现 四 测试 一 点睛 如果遇到负权边,则在没有负环(回路的权值之和为负)存在时,可以采用 Bellman-Ford 算法求解最短路径.该算法的优点是变的权值可以是负数.实现简单,缺点是时间复杂度过高.但是该算法可以进行若干种优化,以提高效率. Bellman-Ford 算法与 Dijkstra 算法类似,都是以松弛操作作为基础.Dijkstra 算法以贪心法选取未被处理的具有最小权值的节点,然后对其进行松弛操作:而 Bellman-Ford 算法对所有边

  • Java异或技操作给任意的文件加密原理及使用详解

    异或简单介绍:异或是一种基于二进制的位运算,用符号XOR或者 ^ 表示,其运算法则是对运算符两侧数的每一个二进制位,同值取0,异值取1. 简单理解就是不进位加法,如1+1=0,,0+0=0,1+0=1. 需求描述 在信息化时代对数据进行加密是一个很重要的主题,在做项目的过程中,我也实现了一个比较复杂的加密算法,但是由于涉及到的技术是保密的,所以在这里我实现一个比较简单的版本,利用文件的输入输出流和异或操作进行任意文件的加密,关于解密算法,很简单,自己思考下就能解决. 数学原理 该加密算法利用的是

  • 详解Java 中泛型的实现原理

    泛型是 Java 开发中常用的技术,了解泛型的几种形式和实现泛型的基本原理,有助于写出更优质的代码.本文总结了 Java 泛型的三种形式以及泛型实现原理. 泛型 泛型的本质是对类型进行参数化,在代码逻辑不关注具体的数据类型时使用.例如:实现一个通用的排序算法,此时关注的是算法本身,而非排序的对象的类型. 泛型方法 如下定义了一个泛型方法, 声明了一个类型变量,它可以应用于参数,返回值,和方法内的代码逻辑. class GenericMethod{ public <T> T[] sort(T[]

  • 详解 Java HashMap 实现原理

    HashMap 是 Java 中最常见数据结构之一,它能够在 O(1) 时间复杂度存储键值对和根据键值读取值操作.本文将分析其内部实现原理(基于 jdk1.8.0_231). 数据结构 HashMap 是基于哈希值的一种映射,所谓映射,即可以根据 key 获取到相应的 value.例如:数组是一种的映射,根据下标能够取到值.不过相对于数组,HashMap 占用的存储空间更小,复杂度却同样为 O(1). HashMap 内部定义了一排"桶",用一个叫 table 的 Node 数组表示:

  • 详解Java分布式系统中一致性哈希算法

    业务场景 近年来B2C.O2O等商业概念的提出和移动端的发展,使得分布式系统流行了起来.分布式系统相对于单系统,解决了流量大.系统高可用和高容错等问题.功能强大也意味着实现起来需要更多技术的支持.例如系统访问层的负载均衡,缓存层的多实例主从复制备份,数据层的分库分表等. 我们以负载均衡为例,常见的负载均衡方法有很多,但是它们的优缺点也都很明显: 随机访问策略.系统随机访问,缺点:可能造成服务器负载压力不均衡,俗话讲就是撑的撑死,饿的饿死. 轮询策略.请求均匀分配,如果服务器有性能差异,则无法实现

  • 详解Java TCC分布式事务实现原理

    概述 之前网上看到很多写分布式事务的文章,不过大多都是将分布式事务各种技术方案简单介绍一下.很多朋友看了还是不知道分布式事务到底怎么回事,在项目里到底如何使用. 所以这篇文章,就用大白话+手工绘图,并结合一个电商系统的案例实践,来给大家讲清楚到底什么是 TCC 分布式事务. 业务场景介绍 咱们先来看看业务场景,假设你现在有一个电商系统,里面有一个支付订单的场景. 那对一个订单支付之后,我们需要做下面的步骤: 更改订单的状态为"已支付" 扣减商品库存 给会员增加积分 创建销售出库单通知仓

随机推荐