Yonker's Blog

码农，程序猿，未来的昏析师

0%

八大排序算法之基数排序

发表于 更新于 分类于

基本思想

是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间Θ(n)。但桶排序并不是 比较排序，他不受到O(nlog2n)下限的影响。

算法的实现

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
125
package com.zyg.sort;

public class RadixSortAlgorithm
{
    // 基数排序，len为数组长度，maxRadix为数组中数的最大位数
    public static void radixSort(int a[], int len, int maxRadix)
    {
        // 定义二维辅助数组
        int temp[][] = new int[10][len];
        // 当前排序的位数，初始状态为个位
        int partition = 1;
        // 依次从个位数到最高位排序
        <!--more-->
        for (int index = 0; index < maxRadix; index++)
        {
            for (int i = 0; i < len; i++)
            {
                // 根据排序位上的数字放入二维数组，数字取值为0-9
                int loc = (a[i] / partition) % 10;
                temp[loc][i] = a[i];
            }
            // 收集数组
            CollectElement(a, temp);
            // 排序位数左移
            partition = partition * 10;
        }
    }
    
    // 收集数组
    public static void CollectElement(int a[], int temp[][])
    {
        int index = 0;
        for (int i = 0; i < temp.length; i++)
        {
            for (int j = 0; j < temp[0].length; j++)
            {
                // 如果辅助数组中元素值大于零，将其加入数组
                if (temp[i][j] > 0)
                    a[index++] = temp[i][j];
                // 重置辅助数组
                temp[i][j] = 0;
            }
        }
    }
    
    // 合并数组
    public static void mergeArray(int a[], int left[], int right[], int len)
    {
        int index = 0;
        // 负数数组还原，并进行倒转
        for (int i = left.length - 1; i >= 0; i--)
        {
            a[index] = -left[i];
            index++;
        }
        // 数组中零
        for (int i = 0; i < len - left.length - right.length; i++)
        {
            a[index] = 0;
            index++;
        }
        // 加入正数数组
        for (int i = 0; i < right.length; i++)
        {
            a[index] = right[i];
            index++;
        }
    }
    
    // 打印数组
    public static void printArray(int a[])
    {
        for (int i = 0; i < a.length; i++)
        {
            System.out.println(a[i]);
        }
    }
    
    public static void main(String[] args)
    {
        // 定义初始化数组
        int a[] =
        { -4, 3, 6, 7, 33, 0, 90, 0, 777, 50 };
        // 数组长度
        int len = a.length;
        // 负数数组和正数数组
        int left[], right[];
        // 数组中负数和正数个数
        int negativeNum = 0, positiveNum = 0;
        for (int i = 0; i < len; i++)
        {
            if (a[i] < 0)
                negativeNum++;
            if (a[i] > 0)
                positiveNum++;
        }
        // 初始化负数数组和正数数组
        left = new int[negativeNum];
        right = new int[positiveNum];
        int j = 0, k = 0;
        for (int i = 0; i < len; i++)
        {
            // 负数数组赋值，并取其绝对值
            if (a[i] < 0)
            {
                left[j] = -a[i];
                j++;
            }
            // 正数数组
            if (a[i] > 0)
            {
                right[k] = a[i];
                k++;
            }
        }
        // 负数数组基数排序
        radixSort(left, left.length, 3);
        // 正数数组基数排序
        radixSort(right, right.length, 3);
        // 将数组进行合并
        mergeArray(a, left, right, len);
        // 打印数组
        printArray(a);
    }
}

效率

时间复杂度

平均情况：O(d(r+n))
最好情况：O(d(n+rd))
最坏情况：O(d(r+n))

空间复杂度

O(rd+n)

稳定性

稳定