基数排序
2022-11-12 21:47:42 # 算法 # 排序 #基数排序

1. 基数排序算法思想

现在有一个问题，对一个数组从小到大排序，数组中元素的范围都在$[0,9]$。

最好的做法是设置一个桶数组buckets，长度为10，buckets的第i个元素，表示数字i出现的次数。因此我们只需要遍历一次数组，把各个数字出现的次数记录到buckets里，然后我们从左到右遍历buckets，如果buckets[i]>0，说明元素i出现了buckets[i]次，那么就输出buckets[i]个元素i到原数组即可。如下图所示：

写成代码就是如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
public class SortZeroToNine {
    
    public static void sort(int[] arr) {
        int[] buckets = new int[10];
        
        //统计各个元素的出现次数
        for(int i = 0; i < arr.length; ++i) ++buckets[arr[i]];
        
        //遍历统计结果，填入数据。
        for(int j = 0, i = 0; j <= 9; ++j) 
            while(buckets[j]-- > 0) arr[i++] = j;
    }
}

时间复杂度$O(N)$，空间复杂度$O(1)$。

这是计数排序的思想。因此当数据的范围很有限的时候（屈指可数），使用计数的思想是比较好的。

基数排序也是基于这样的想法。只不过基数排序是对数据的每一位按照上述方法排序，排序的过程大致如下：假设一组数据中最高位是百位，那么首先按照个位进行排序；然后在个位有序的基础上，对十位进行排序，对于十位相同的数据，不要改变个位已经排好的顺序；然后对百位进行排序，百位相同的数据，不要改变十位已经排好顺序（稳定性）。这样整个数组就有序了，如下图所示：

这样做的道理是什么呢？

我们观察一个有序的数组（不妨按照从小到大的顺序，便于描述，我们假设数组中元素的最高位是百位），所有元素的相同的位有一个规律，即百位按照从小到大的顺序排列，百位相同的，十位按照从小到大的顺序排列，十位相同的，个位按照从小到大的顺序排列的。反之，我们只要把数组排列成这样的顺序，数组就是有序的（因为比较两个数的大小的时候，先比较高位）。

因为基数排序是先排个位，然后十位，… …，最后排最高位。因为最高位是最后完成排序的，因此最高位一定是有序的。那么当最高位相同的时候，我们排序的时候要求不能改变次高位已经排好顺序的相对位置，因此次高位也是从小到大，… …，这样我们正好达到了上面所说的一个有序数组的规律，因此这样操作可以完成数组的排序。

多行注释 我们是怎么比较两个正整数的大小的呢？先看最高位，最高位大的那个数大，如果最高位分不出来，那么再看次高位，次高位大的那个数大，否则再往下看，直到能分出来为止，如果所有的位都看完了，还没有分出来，说明两个数一样大。 这是因为整数的大小是由最高位决定的，当最高位相等的时候，此时我们就需要看下一位，因为我们是从低位到高位依次排序的，因此在排高位的时候，低位已经完成了排序。因为当高位相等的时候，我们只需按照数据在原数组中的原来的位置输出即可，而不能改变他们的相对次序。因为一旦改变的话，就打乱了低位已经排好的顺序（这就是为什么我们要求在给每一位排序的时候，选择的排序方法是稳定的原因）。即基数排序的基本思想是，高位可以决定出来大小的，就采用高位排出来的顺序，否则就采用它的下一位给出的顺序。例如arr=[123,133,321]，先按个位排序：[321,123,133]，在按十位排序：[321,123,133]，再根据十位排序的时候，321和123的十位都是2，因此分不出来大小，于是就按照原顺序输出（即参考个位给出的顺序），再根据百位排序：[123,133,321]，根据百位的大小关系，321被排在了最后，这是因为它是百位最大的，于是它就改变原来的顺序（百位大的数更大，可以忽略十位排好的顺序），但是123和133因为百位都是1，分不出来大小，因此它们的相对顺序不变，从第二步的1，2位置，变成第三步的0，1位置（相对位置不变，即参考十位给出的顺序）。

2. 算法实现

我们需要获取到一个数上的各个数位的值，比如123，第0位是个位，第1位是十位，… …，现在给定任意的一个正整数$x$，得到它的第$i(i>=0)$位上的值，应该怎么办？这里直接给出公式：$\frac{x}{10^i}\bmod 10$。

还有一个问题就是，我们怎么对每一位排序？根据上面的描述，我们知道，整数的每一位的范围是$[0,9]$，因此对每一位排序我们可以采取计数排序的方法，但是根据上面我们说过的规则，对每一位排序要求排序方法是稳定的，而一般的计数排序是做不到稳定性的，此时我们需要对一般的计数排序算法改进一下，使其达到稳定性的要求。那么如何改进呢？

所谓排序算法的稳定性是指在排序前后，相同数据的相对位置不能改变。

例如数组arr：[1,3,4,5,7,3]，排序之前红色的3在绿色的3左边，在排序以后，红色的3不能跑到绿色的3右边。虽然这在一般的排序中即使换了位置也无所谓，但是在对象排序以及本文所介绍的基数排序中是至关重要的。

2.1. 稳定的计数排序

下面使用一张图描述计数排序的改进方案，如下图所示：

2.2. 稳定的计数排序代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class SortZeroToNineStable {
    
    public static void sort(int[] arr) {
        int[] buckets = new int[10];
        
        //统计各个元素的出现次数
        for(int i = 0; i < arr.length; ++i) ++buckets[arr[i]];
        
        //变换计数桶
        for(int i = 1; i < 10; ++i) buckets[i] += buckets[i - 1];
        
        //辅助数组
        int[] help = new int[arr.length];
        System.arraycopy(arr, 0, help, 0, arr.length);
        
        //遍历统计结果，倒出
        for(int i = arr.length - 1; i > -1; --i) arr[--buckets[help[i]]] = help[i];
    }
}

时间复杂度$O(N)$，空间复杂度$O(N)$。

3. 基数排序完整代码

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
import java.util.Arrays;

public class RadixSort {
    
    private static final int[] RADIX_TABLE = {
        1, 10, 100, 1000, 10000, 10_0000, 100_0000,
        1000_0000, 1_0000_0000, 10_0000_0000
    };
    
    public static void sort(int[] arr) {
        int len = arr.length;
        if(len < 2) return;
        int i, max = arr[0], radix, j;
        
        //申请辅助数组和计数桶数组
        int[] buckets = new int[10], data = new int[len], help = new int[len], t;
        
        //找出数组的最大值，确定最高位是多少
        for(i = 1; i < len; ++i) max = Math.max(max, arr[i]);
        radix = lengthOf(max);
        
        // 这里把数据拷贝到data数组中，便于后续排序
        System.arraycopy(arr, 0, data, 0, len);
        for(i = 0; i < radix; ++i) {// 需要排序radix趟
            Arrays.fill(buckets, 0);
            for(j = 0; j < len; ++j) ++buckets[radixOf(data[j], i)];// 对第i位上的数，计数入桶
            for(j = 1; j < 10; ++j) buckets[j] += buckets[j - 1]; //转换buckets数组，便于后续倒出
            for(j = len - 1; j > -1; --j) help[--buckets[radixOf(data[j], i)]] = data[j];// 倒出
            t = help;
            help = data;
            data = t;
        }
        System.arraycopy(data, 0, arr, 0, len);
    }
    
    private static int lengthOf(int num) {
        int ans = 0;
        while(num != 0) {
            ++ans;
            num /= 10;
        }
        return ans;
    }
    
    private static int radixOf(int num, int i) {// 获取num上的第i位的值，i>=0
        return (num / RADIX_TABLE[i]) % 10;
    }
}

假设数组中的最大值是$max$，那么时间复杂度$O(N*\log_{10}max)$，空间复杂度$O(N)$。

4. 测试程序

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
import java.util.Arrays;
import java.util.Random;

public class RadixSortTest {
    
    public static void main(String[] args) {
        int times = 100_0000, maxArraySize = 1000;
        while(times-- > 0) {
            Random r = new Random();
            int size = r.nextInt(maxArraySize) + 1;
            int[] array1 = new int[size], array2 = new int[size], array3 = new int[size];
            for(int i = 0; i < size; ++i) array1[i] = array2[i] = array3[i] = r.nextInt(10_0001);
            RadixSort.sort(array1);
            Arrays.sort(array2);
            for(int i = 0; i < size; ++i) {
                if(array1[i] != array2[i]) {
                    System.out.println("Oops!, wrong answer!!");
                    System.out.println("array1 is:");
                    System.out.println(Arrays.toString(array1));
                    System.out.println("array2 is:");
                    System.out.println(Arrays.toString(array2));
                    System.out.println("origin array is:");
                    System.out.println(Arrays.toString(array3));
                    return;
                }
            }
            System.out.println("Testcase " + times + " is finished!");
        }
        System.out.println("Test is done successfully!");
    }
}
上一页
2022-11-12 21:47:42 # 算法 # 排序 #基数排序
下一页