内部排序算法:基数排序

基本思想

基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。
基数排序可以采用两种方式:

  • LSD(Least Significant Digital):从待排序元素的最右边开始计算(如果是数字类型,即从最低位个位开始)。
  • MSD(Most Significant Digital):从待排序元素的最左边开始计算(如果是数字类型,即从最高位开始)。

我们以LSD方式为例,从数组R[1..n]中每个元素的最低位开始处理,假设基数为radix,如果是十进制,则radix=10。基本过程如下所示:

  1. 计算R中最大的元素,求得位数最大的元素,最大位数记为distance;
  2. 对每一位round<=distance,计算R[i] % radix即可得到;
  3. 将上面计算得到的余数作为bucket编号,每个bucket中可能存放多个数组R的元素;
  4. 按照bucket编号的顺序,收集bucket中元素,就地替换数组R中元素;
  5. 重复2~4,最终数组R中的元素为有序。

算法实现

基数排序算法,Java实现,代码如下所示:

public abstract class Sorter {
     public abstract void sort(int[] array);
}

public class RadixSorter extends Sorter {
    
     private int radix;
    
     public RadixSorter() {
          radix = 10;
     }
    
     @Override
     public void sort(int[] array) {
          // 数组的第一维表示可能的余数0-radix,第二维表示array中的等于该余数的元素
          // 如:十进制123的个位为3,则bucket[3][] = {123}
          int[][] bucket = new int[radix][array.length];
          int distance = getDistance(array); // 表示最大的数有多少位
          int temp = 1;
          int round = 1; // 控制键值排序依据在哪一位
          while (round <= distance) {
               // 用来计数:数组counter[i]用来表示该位是i的数的个数
               int[] counter = new int[radix];
               // 将array中元素分布填充到bucket中,并进行计数
               for (int i = 0; i < array.length; i++) {
                    int which = (array[i] / temp) % radix;
                    bucket[which][counter[which]] = array[i];
                    counter[which]++;
               }
               int index = 0;
               // 根据bucket中收集到的array中的元素,根据统计计数,在array中重新排列
               for (int i = 0; i < radix; i++) {
                    if (counter[i] != 0)
                         for (int j = 0; j < counter[i]; j++) {
                              array[index] = bucket[i][j];
                              index++;
                         }
                    counter[i] = 0;
               }
               temp *= radix;
               round++;
          }
     }
    
     private int getDistance(int[] array) {
          int max = computeMax(array);
          int digits = 0;
          int temp = max / radix;
          while(temp != 0) {
               digits++;
               temp = temp / radix;
          }
          return digits + 1;
     }
    
     private int computeMax(int[] array) {
          int max = array[0];
          for(int i=1; i<array.length; i++) {
               if(array[i]>max) {
                    max = array[i];
               }
          }
          return max;
     }
}

基数排序算法,Python实现,代码如下所示:

class Sorter:
    '''
    Abstract sorter class, which provides shared methods being used by
    subclasses.
    '''
    __metaclass__ = ABCMeta
   
    @abstractmethod   
    def sort(self, array):
        pass

class RadixSorter(Sorter):
    '''
    Radix sorter
    '''
    def __init__(self):
        self.radix = 10
       
    def sort(self, array):
        length = len(array)
        which_round = 1
        bucket = [[0 for col in range(length)] for row in range(self.radix)]
        distance = self.__get_distance(array)
        temp = 1
        while which_round<=distance:
            counter = [0 for x in range(self.radix)]
            for i in range(length):
                which = (array[i] // temp) % self.radix
                bucket[which][counter[which]] = array[i]
                counter[which] += 1
            index = 0
            for i in range(self.radix):
                if counter[i]!=0:
                    for j in range(counter[i]):
                        array[index] = bucket[i][j]
                        index += 1
            temp *= self.radix
            which_round += 1
           

    def __get_distance(self, array):
        max_elem = self.__get_max(array)
        digits = 0
        temp = max_elem // self.radix
        while temp != 0:
            digits += 1
            temp //= self.radix
        return digits + 1
   
    def __get_max(self, array):
        max_elem = array[0]
        for x in range(1, len(array)):
            if array[x]>max_elem:
                max_elem = array[x]
        return max_elem

排序过程

假设待排序数组为array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49},数组大小为20,我们以该数组为例,
最大的数组元素的位数为2,所以需要进行2轮映射(映射到对应的桶中),执行基数排序的具体过程,如下所示:

  • 数组原始顺序

数组的原始顺序,如下图所示:
radixsorter-array-original
数组中存在的相同的元素(同一个待排序的数字出现大于1次),我们使用不同的背景颜色来区分(红色背景表示第二次出现,靛青色表示第三次出现),如果一个元素只出现过一次,则我们就使用一种固定的颜色(浅绿色)表示。

    根据数组元素个位数字将数组中元素映射到对应的桶中(bucket)

我们使用的是十进制,基数(Radix)自然是10,根据数组元素个位数的,应该映射到10个桶中,映射后的结果,如图所示:
radixsorter-bucket-1
在映射到桶的过程中,从左到右扫描原始数组。因为映射到同一个桶中的元素可能存在多个,最多为整个数组的长度,所以在同一个桶中,要保持进入桶中的元素的先后顺序(先进的排在左侧,后进的排在右侧)。

  • 收集桶中元素,并在原始数组中原地替换,使数组中元素顺序重新分布

扫面前面已经映射到各个桶中的元素,满足这样的顺序:先扫描编号最小的桶,桶中如果存在多个元素,必须按照从左到右的顺序。这样,将得到的数组元素重新分布,得到一个元素位置重新分布的数组,如图所示:
radixsorter-array-after-collecting-1
这时,可以看到元素实际上是按照个位的数字进行了排序,但是基于整个元素来说并不是有序的。

  • 根据数组元素十位数字将数组中元素映射到对应的桶中(bucket)

这次映射的原则和过程,与前面类似,不同的是,这次扫描的数组是经过个位数字处理重新分布后的新数组,映射后桶内的状态,如图所示:
radixsorter-bucket-2

  • 收集桶中元素,并在原始数组中原地替换,使数组中元素顺序重新分布

和前面收集方法类似,得到的数组及其顺序,如图所示:
radixsorter-array-after-collecting-2
我们可以看到,经过两轮映射和收集过程,数组已经变成有序了,排序结束。

算法分析

  • 时间复杂度

设待排序的数组R[1..n],数组中最大的数是d位数,基数为r(如基数为10,即10进制,最大有10种可能,即最多需要10个桶来映射数组元素)。处理一位数,需要将数组元素映射到r个桶中,映射完成后还需要收集,相当于遍历数组一遍,最多元素书为n,则时间复杂度为O(n+r)。所以,总的时间复杂度为O(d*(n+r))。

  • 空间复杂度

设待排序的数组R[1..n],数组中最大的数是d位数,基数为r。基数排序过程中,用到一个计数器数组,长度为r,还用到一个r*n的二位数组来做为桶,所以空间复杂度为O(r*n)。

  • 排序稳定性

通过上面的排序过程,我们可以看到,每一轮映射和收集操作,都保持从左到右的顺序进行,如果出现相同的元素,则保持他们在原始数组中的顺序。
可见,基数排序是一种稳定的排序。

Creative Commons License

本文基于署名-非商业性使用-相同方式共享 4.0许可协议发布,欢迎转载、使用、重新发布,但务必保留文章署名时延军(包含链接:http://shiyanjun.cn),不得用于商业目的,基于本文修改后的作品务必以相同的许可发布。如有任何疑问,请与我联系

评论(3): “内部排序算法:基数排序

    • 抱歉,在网上找到的,确实没有找到原始作者,方便的话,把您的原创连接发给我,我标注一下。

Yanjun进行回复 取消回复

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>