人工智能排序算法(8):基数排序 人工智能算法大全_AI算法 第1张

一、前言

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

二、算法思想

基本思想:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

算法步骤:

  • 将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。

  • 从最低位开始,依次进行一次排序。

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

基数排序的方式可以采用 LSD(Least significant digital)或 MSD(Most significant digital),LSD 的排序方式由键值的最右边开始,而 MSD 则相反,由键值的最左边开始。

不妨通过一个具体的实例来展示一下基数排序是如何进行的。 设有一个初始序列为: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。

我们知道,任何一个阿拉伯数,它的各个位数上的基数都是以 0~9 来表示的,所以我们不妨把 0~9 视为 10 个桶。

我们先根据序列的个位数的数字来进行分类,将其分到指定的桶中。例如:R[0] = 50,个位数上是 0,将这个数存入编号为 0 的桶中。

 人工智能排序算法(8):基数排序 人工智能算法大全_AI算法 第2张

分类后,我们在从各个桶中,将这些数按照从编号 0 到编号 9 的顺序依次将所有数取出来。这时,得到的序列就是个位数上呈递增趋势的序列。

按照个位数排序: {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。

接下来,可以对十位数、百位数也按照这种方法进行排序,最后就能得到排序完成的序列。

动态效果示意图:

 人工智能排序算法(8):基数排序 人工智能算法大全_AI算法 第3张

编辑


1、代码

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

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


#include <iostream>

#include <vector>

 

using namespace std;

 

// 求出数组中最大数的位数的函数

int MaxBit(vector<int> input){

    // 数组最大值

    int max_data = input[0];

    for (int i = 1; i < input.size(); i++){

        if (input[i] > max_data){

            max_data = input[i];

        }

    }

 

    // 数组最大值的位数

    int bits_num = 0;

    while (max_data){

        bits_num++;

        max_data /= 10;

    }

 

    return bits_num;

}

 

// 取数xxx上的第d位数字

int digit(int num, int d){

    int pow = 1;

    while (--d > 0){

        pow *= 10;

    }

    return num / pow % 10;

}

 

// 基数排序

vector<int> RadixSort(vector<int> input, int n){

    // 临时数组,用来存放排序过程中的数据

    vector<int> bucket(n);                    

    // 位记数器,从第0个元素到第9个元素依次用来记录当前比较位是0的有多少个...是9的有多少个数

    vector<int> count(10);                

    // 从低位往高位循环

    for (int d = 1; d <= MaxBit(input); d++){

        // 计数器清0

        for (int i = 0; i < 10; i++){

            count[i] = 0;

        }

 

        // 统计各个桶中的个数

        for (int i = 0; i < n; i++){

            count[digit(input[i],d)]++;

        }

 

        /*

        * 比如某次经过上面统计后结果为:[0, 2, 3, 3, 0, 0, 0, 0, 0, 0]则经过下面计算后 结果为: [0, 2,

        * 5, 8, 8, 8, 8, 8, 8, 8]但实质上只有如下[0, 2, 5, 8, 0, 0, 0, 0, 0, 0]中

        * 非零数才用到,因为其他位不存在,它们分别表示如下:2表示比较位为1的元素可以存放在索引为1、0的

        * 位置,5表示比较位为2的元素可以存放在4、3、2三个(5-2=3)位置,8表示比较位为3的元素可以存放在

        * 7、6、5三个(8-5=3)位置

        */

        for (int i = 1; i < 10; i++){

            count[i] += count[i - 1];

        }

 

        /*

        * 注,这里只能从数组后往前循环,因为排序时还需保持以前的已排序好的顺序,不应该打

        * 乱原来已排好的序,如果从前往后处理,则会把原来在前面会摆到后面去,因为在处理某个

        * 元素的位置时,位记数器是从大到到小(count[digit(arr[i], d)]--)的方式来处

        * 理的,即先存放索引大的元素,再存放索引小的元素,所以需从最后一个元素开始处理。

        * 如有这样的一个序列[212,213,312],如果按照从第一个元素开始循环的话,经过第一轮

        * 后(个位)排序后,得到这样一个序列[312,212,213],第一次好像没什么问题,但问题会

        * 从第二轮开始出现,第二轮排序后,会得到[213,212,312],这样个位为3的元素本应该

        * 放在最后,但经过第二轮后却排在了前面了,所以出现了问题

        */

        for (int i = n - 1; i >= 0; i--){

            int k = digit(input[i], d);

            bucket[count[k] - 1] = input[i];

            count[k]--;

        }

 

        // 临时数组复制到 input 中

        for (int i = 0; i < n; i++){

            input[i] = bucket[i];

        }

    }

 

    return input;

}

 

void main(){

    int arr[] = { 50, 123, 543, 187, 49, 30, 0, 2, 11, 100 };

    vector<int> test(arr, arr + sizeof(arr) / sizeof(arr[0]));

    cout << "排序前:";

    for (int i = 0; i < test.size(); i++){

        cout << test[i] << " ";

    }

    cout << endl;

    

    vector<int> result = test;

    result = RadixSort(result, result.size());

    cout << "排序后:";

    for (int i = 0; i < result.size(); i++){

        cout << result[i] << " ";

    }

    cout << endl;

    system("pause");

}


运行结果如下图所示:

 人工智能排序算法(8):基数排序 人工智能算法大全_AI算法 第4张

编辑


Python

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

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


# -*- coding:utf-8 -*-

 

def RadixSort(input_list):

    '''

    函数说明:基数排序(升序)

    Author:

        www.cuijiahua.com

    Parameters:

        input_list - 待排序列表

    Returns:

        sorted_list - 升序排序好的列表

    '''

    def MaxBit(input_list):

        '''

        函数说明:求出数组中最大数的位数的函数

        Author:

            www.cuijiahua.com

        Parameters:

            input_list - 待排序列表

        Returns:

            bits-num - 位数

        '''

        max_data = max(input_list)

        bits_num = 0

        while max_data:

            bits_num += 1

            max_data //= 10

        return bits_num

 

    def digit(num, d):

        '''

        函数说明:取数xxx上的第d位数字

        Author:

            www.cuijiahua.com

        Parameters:

            num - 待操作的数

            d - 第d位的数

        Returns:

            取数结果

        '''    

        p = 1

        while d > 1:

            d -= 1

            p *= 10

        return num // p % 10

 

 

    if len(input_list) == 0:

        return []

    sorted_list = input_list

    length = len(sorted_list)

    bucket = [0] * length

    

    for d in range(1, MaxBit(sorted_list) + 1):

        count = [0] * 10

 

        for i in range(0, length):

            count[digit(sorted_list[i], d)] += 1

 

        for i in range(1, 10):

            count[i] += count[i - 1]

 

        for i in range(0, length)[::-1]:

            k = digit(sorted_list[i], d)

            bucket[count[k] - 1] = sorted_list[i]

            count[k] -= 1

        for i in range(0, length):

            sorted_list[i] = bucket[i]

 

    return sorted_list

 

if __name__ == '__main__':

    input_list = [50, 123, 543, 187, 49, 30, 0, 2, 11, 100]

    print('排序前:', input_list)

    sorted_list = RadixSort(input_list)

    print('排序后:', sorted_list)



三、算法分析

1、基数排序的性能

 人工智能排序算法(8):基数排序 人工智能算法大全_AI算法 第5张

编辑


其中,d代表数组元素最高为位数,n代表元素个数。

2、时间复杂度

这个时间复杂度比较好计算:count * length;其中 count 为数组元素最高位数,length为元素个数;所以时间复杂度:O(n * d)

3、空间复杂度

空间复杂度是使用了两个临时的数组:10 + length;所以空间复杂度:O(n)。

4、算法稳定性

在基数排序过程中,每次都是将当前位数上相同数值的元素统一“装桶”,并不需要交换位置。所以基数排序是稳定的算法。