首页 > 后端开发 > Python教程 > 各种编程语言中基数排序的原理与实现方法

各种编程语言中基数排序的原理与实现方法

PHPz
发布: 2023-05-08 12:31:07
转载
1534 人浏览过

    说明

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

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

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

    实现过程

    • 将待排序数列(正整数)统一为同样的数位长度,数位较短的补零。

    • 每个数位单独排序,从最低位到最高位,或从最高位到最低位。

    • 这样从最低到高或从高到低排序完成以后,数列就变成一个有序数列。

    示意图

    Java/Go/Python/JS/C基数排序算法的原理与实现方法是什么

    Java/Go/Python/JS/C基数排序算法的原理与实现方法是什么

    性能分析

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

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

    稳定性:稳定

    代码

    Java

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    35

    36

    37

    38

    39

    40

    41

    42

    43

    44

    45

    46

    47

    48

    49

    50

    51

    52

    53

    54

    55

    56

    57

    58

    59

    60

    61

    62

    63

    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

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    35

    36

    37

    38

    39

    40

    41

    42

    43

    44

    45

    46

    47

    48

    49

    50

    51

    52

    53

    54

    55

    56

    57

    58

    59

    60

    61

    62

    63

    64

    65

    66

    67

    68

    69

    70

    71

    72

    73

    74

    75

    76

    77

    78

    79

    80

    81

    82

    83

    84

    85

    86

    87

    // 基数排序,从高到低逐位排序,递归方式,基于桶排序。具体步骤如下:

    // 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

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    35

    36

    """

    基数排序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(&#39;buckets:&#39;, buckets)

     

            # 通过exend展开数组,相当于逐层添加

            arr = []

            for bucket in buckets:

                arr.extend(bucket)

                # 或逐项添加

                # for item in bucket:

                #     arr.append(item)

     

            # 数位移动到下一位

            digit *= 10

     

        return arr

    登录后复制

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    35

    36

    37

    38

    39

    40

    41

    42

    43

    44

    45

    46

    47

    48

    49

    50

    51

    52

    53

    54

    55

    56

    57

    58

    59

    60

    61

    62

    63

    """

    基数排序,从高到低逐位排序,递归方式,基于桶排序。具体步骤如下:

    1. 找出数组中最大的数,确定其位数。

    2. MSD是从高位开始,依次按照位数的值将数字放入到不同桶中。

    3. 如果桶里的长度超过1,则通过递归继续按桶排序。当桶里的数据只有1位时添加到原列表对应位置。

    重复步骤2和3,直到按照最高位排序完成。

    """

    # 桶排序,根据数位递归调用

    def bucket_sort(arr, exponent):

        print(&#39;origin arr:&#39;, arr, &#39;exponent:&#39;, exponent)

        if (len(arr) <= 1 or exponent <= 0):

            return arr

     

        min_value = min(arr)

     

        radix = 10

        amount = 10

     

        print(&#39;prepared arr:&#39;, arr, &#39;exponent:&#39;, 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(&#39;append to buckets:&#39;, 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 (&#39;sortedIdx::&#39;, sortedIdx)

                arr[sortedIdx] = num

                print(&#39;bucket:&#39;, bucket, &#39;sortedBucket:&#39;, sortedBucket,

                      &#39;sortedIdx:&#39;, sortedIdx, &#39;set arr:&#39;, arr)

                sortedIdx += 1

     

        print(&#39;exponent:&#39;, exponent, &#39;sorted arr:&#39;, 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

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    35

    36

    37

    38

    39

    40

    41

    42

    43

    44

    45

    46

    47

    48

    49

    50

    51

    52

    53

    54

    55

    // 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

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    35

    36

    37

    38

    39

    40

    41

    42

    43

    44

    45

    46

    47

    48

    49

    50

    51

    52

    53

    54

    55

    56

    57

    58

    59

    60

    61

    62

    63

    64

    65

    66

    67

    68

    69

    70

    71

    72

    73

    74

    75

    76

    77

    78

    79

    80

    81

    82

    83

    84

    85

    86

    87

    88

    89

    90

    91

    92

    93

    94

    95

    96

    97

    98

    99

    100

    101

    102

    103

    104

    105

    106

    107

    108

    109

    110

    111

    112

    113

    114

    115

    116

    117

    118

    119

    120

    121

    122

    123

    124

    // 基数排序,从高到低逐位排序,递归方式,基于桶排序。具体步骤如下:

    // 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

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    35

    36

    37

    38

    39

    40

    41

    42

    43

    44

    45

    46

    47

    48

    49

    50

    51

    52

    // 基数排序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

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    35

    36

    37

    38

    39

    40

    41

    42

    43

    44

    45

    46

    47

    48

    49

    50

    51

    52

    53

    54

    55

    56

    57

    58

    // 基数排序,从高到低逐位排序,递归方式,基于桶排序。具体步骤如下:

    // 1. 找出数组中最大的数,确定其位数。

    // 2. MSD是从高位开始,依次按照位数的值将数字放入到不同桶中。

    // 3. 如果桶里的长度超过1,则通过递归继续按桶排序。当桶里的数据只有1位时添加到原列表对应位置。

    // 重复步骤2和3,直到按照最高位排序完成。

    function radixSortMSD(arr) {

     

      function bucketSort(arr, exponent) {

        console.log(&#39;origin arr:&#39;, arr, &#39;exponent:&#39;, 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

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    35

    36

    37

    38

    39

    40

    41

    42

    43

    44

    45

    46

    47

    48

    49

    50

    51

    52

    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(&#39;countingSort countList:&#39;, 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

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    35

    36

    37

    38

    39

    40

    41

    42

    43

    44

    45

    46

    47

    48

    49

    50

    51

    52

    53

    54

    55

    56

    57

    58

    59

    60

    61

    62

    63

    64

    65

    66

    67

    68

    69

    // 计数排序,根据基数按位进行计数

    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;

    }

    登录后复制

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    35

    36

    37

    38

    39

    40

    41

    42

    43

    44

    45

    46

    47

    48

    49

    50

    51

    52

    53

    54

    55

    56

    57

    58

    59

    60

    61

    62

    63

    64

    65

    66

    67

    68

    69

    70

    71

    72

    73

    74

    75

    76

    77

    78

    79

    80

    81

    82

    83

    84

    85

    86

    87

    88

    89

    90

    91

    92

    93

    94

    95

    96

    97

    98

    99

    100

    101

    102

    103

    104

    105

    106

    107

    108

    109

    110

    111

    112

    113

    114

    115

    116

    117

    118

    119

    120

    121

    122

    123

    124

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

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    35

    36

    37

    38

    39

    40

    41

    42

    43

    44

    45

    46

    47

    48

    49

    50

    51

    52

    53

    54

    55

    56

    57

    58

    59

    60

    61

    62

    63

    64

    // 基数排序,从个位到高位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;

    }

    登录后复制

    链接

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

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

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

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

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

    以上是各种编程语言中基数排序的原理与实现方法的详细内容。更多信息请关注PHP中文网其他相关文章!

    相关标签:
    本站声明
    本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
    最新问题
    python - ubuntu16.04 lxml的报错
    来自于 1970-01-01 08:00:00
    0
    0
    0
    有办法在PHP里写Python吗?
    来自于 1970-01-01 08:00:00
    0
    0
    0
    python scrapy爬虫错误
    来自于 1970-01-01 08:00:00
    0
    0
    0
    python相关问题求解决,有偿
    来自于 1970-01-01 08:00:00
    0
    0
    0
    热门教程
    更多>
    最新下载
    更多>
    网站特效
    网站源码
    网站素材
    前端模板