各种各样的排序（ Sort ）算法

发表于 分类于 本文字数： 4.4k 阅读时长 ≈ 16 分钟
几种排序算法总结

冒泡排序 - Bubble Sort

定义

冒泡排序（ Bubble Sort ）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

时间复杂度

当最好的情况，也就是要排序的序列本身就是有序的，需要进行（ n -1 ）次比较，没有数据交换，时间复杂度为 $O\left( n\right)$ 。
当最坏的情况，即待排序的表是逆序的情况，此时需要比较次数为：$1+2+3+\ldots +\left( n-1\right) =\dfrac {n\left( n-1\right) }{2}$ 次，并作等数量级的记录移动，因此总的时间复杂度为 $O\left( n^{2}\right)$

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

//Java
public class BubbleSort {

    public static void Sort(int[] array){

        /*
        //1
        for (int i = 0; i < array.length - 1; i++){

            for (int j = 0; j < array.length - i -1; j++){

                if (array[j] > array[j + 1]){

                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
        */

        //2
        boolean changed;
        do {
            changed = false;
            for (int i = 0; i < array.length - 1; i++){
                if (array[i] > array[i + 1]){
                    int temp = array[i];
                    array[i] = array[i + 1];
                    array[i + 1] = temp;
                    changed = true;
                }
            }
        }while (changed);

    }

    public static void main(String[] args){

        int[] array = {20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10};

        Sort(array);

        for (int i = 0; i < array.length; i++){
            System.out.print(array[i] + " ");
        }
    }
}

逆序数求解

何为逆序数？在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
#include <iostream>
#include <random>
#include <vector>
#include <ctime>

using std::cin;
using std::cout;
using std::endl;

static int count = 0;

// 冒泡排序
// O(n^2)
int InverseNumber_BubbleSort(const std::vector<int> & vector)
{

    for (auto iter = vector.cbegin(); iter != vector.cend(); ++iter)
    {
        for (auto iter2 = iter + 1; iter2 != vector.cend(); ++iter2)
        {
            if (*iter > *iter2)
            {
                ++count;
            }
        }
    }


    return count;
}

// ----------------------------

// 归并排序
// O(nlogn)

void printArray(std::vector<int> vector);

std::vector<int> ms_SortArray(std::vector<int> vector);
std::vector<int> ms_MergeArray(std::vector<int> front, std::vector<int> end);

int InverseNumber_MergeSort(const std::vector<int> & vector)
{
    std::vector<int> vec{vector.cbegin(), vector.cend()};

    ms_SortArray(vec);

    return count;
}

std::vector<int> ms_SortArray(std::vector<int> vector)
{
    std::vector<int> vec_front;
    std::vector<int> vec_end;

    // 单个元素直接返回
    if (vector.size() == 1)
    {
        return vector;
    }

    if (vector.size() & 1) // 数组长度为奇数
    {
        vec_front.assign(vector.cbegin(), vector.cbegin() + vector.size() / 2 + 1);
        vec_end.assign(vector.cbegin() + vector.size() / 2 + 1, vector.cend());
        vec_front = ms_SortArray(vec_front);  // 递归,继续拆分前半部分数组至单个元素
        vec_end = ms_SortArray(vec_end);  // 递归，继续拆分后半部分数组至单个元素
    }
    else  // 数组长度为偶数
    {
        vec_front.assign(vector.cbegin(), vector.cbegin() + vector.size() / 2);
        vec_end.assign(vector.cbegin() + vector.size() / 2, vector.cend());
        vec_front = ms_SortArray(vec_front);  // 递归,继续拆分前半部分数组至单个元素
        vec_end = ms_SortArray(vec_end);  // 递归，继续拆分后半部分数组至单个元素
    }

    return ms_MergeArray(vec_front, vec_end);
}

std::vector<int> ms_MergeArray(const std::vector<int> front, const std::vector<int> end)
{
    std::vector<int> v;

    size_t total_size = front.size() + end.size();
    size_t front_size = front.size();  // 前半部分数组长度
    size_t end_size = end.size();  // 后半部分数组长度

    size_t merge_count = 0; // 合并后数组长度
    size_t index1 = 0; // 前半段数组的头
    size_t index2 = 0; // 后半段数组的头

    while (merge_count < total_size)
    {
        // 检查是否已经有一段数组排序完成
        if (index1 == front_size)  // 前半段数组合并完成，后半段还有多余元素
        {
            for (size_t i = index2; i < end_size; ++i)
            {
                v.push_back(end.at(i));
                ++merge_count;
                ++index2;
            }
        }
        else if (index2 == end_size) // 后半段数组合并完成，前半段还有多余元素
        {
            for (size_t i = index1; i < front_size; ++i)
            {
                v.push_back(front.at(i));
                ++merge_count;
                ++index1;
            }
        }
        else
        {
            int value1 = front.at(index1);
            int value2 = end.at(index2);

            if (value1 == value2)
            {
                v.push_back(value1);
                ++merge_count;
                ++index1;
            }
            else if (value1 < value2)
            {
                v.push_back(value1);
                ++merge_count;
                ++index1;
            }
            else // (value1 > value2)
            {
                v.push_back(value2);
                ++merge_count;
                ++index2;
                count += front_size - index1;
            }

        }

    }

    return v;

}

// -------------------------------------

// 随机数组生成
std::vector<int> vecGen(size_t length)
{
    std::vector<int> vec(length);

    // 以随机值播种，若可能
    std::random_device random_device;

    // 生成无符号随机整数
    static std::default_random_engine engine(random_device());
    // 生成 0 到 9 之间（包含）均匀分布的随机数
    static std::uniform_int_distribution<int> u(1, 9);

    for (int i = 0; i < length; ++i)
    {
        vec[i] = u(engine);
    }

    return vec;
}

// -------------------------------------

// 输出数组
void printArray(std::vector<int> vector)
{
    for (const int i : vector)
    {
        cout << i << " ";
    }
    cout << endl;
}

int main()
{
    size_t len;
    clock_t tbegin, tend;

    cout.setf(std::ios::fixed, std::ios::floatfield);

    cout << "求逆序数：" << endl;
    cout << "请输入数组长度：" << endl;
    cin >> len;

    std::vector<int> vector = vecGen(len);
    printArray(vector);

    cout << "求逆序数后：" << endl;
    cout << endl;

    tbegin = clock();
    cout << "逆序数为：" << InverseNumber_BubbleSort(vector) << endl;
    tend = clock();
    cout << "花费时间为：" << double(tend - tbegin) / CLOCKS_PER_SEC * 1000<< " ms" << endl;
    cout << endl;

    count = 0;
    tbegin = clock();
    cout << "逆序数为：" << InverseNumber_MergeSort(vector) << endl;
    tend = clock();
    cout << "花费时间为：" << double(tend - tbegin) / CLOCKS_PER_SEC * 1000<< " ms" << endl;


    return 0;
}

插入排序 - Insert Sort

定义

直接插入排序的基本操作是将一个记录插入到已经排好的有序表中，从而得到一个新的、记录数增一的有序表。对于给定的一组记录，初始时假定第一个记录自成一个有序序列，其余记录为无序序列。接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直到最后一个记录插到有序序列中为止。

时间复杂度

当最好的情况，也就是要排序的表本身就是有序的，此时只有数据比较，没有数据移动，时间复杂度为 $O\left( n\right)$。
当最坏的情况，即待排序的表是逆序的情况，此时需要比较次数为：$2+3+\ldots +n =\dfrac {\left( n+2\right) \times \left( n-1\right) }{2}$ 次,而记录移动的最大值也达到了 $\dfrac {\left( n+4\right) \times \left( n-1\right) }{2}$ 次。
如果排序记录是随机的，那么根据概率相同的原则，平均比较和移动次数约为 $\dfrac {n^{2}}{2}$ 次，，因此，得出直接插入排序发的时间复杂度为 $O\left( n^{2}\right)$。

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

//Java
import java.util.Arrays;

public class InsertSort {

    public static void insertSort(int[] a) {
        int i, j, insertNote;// 要插入的数据
        for (i = 1; i < a.length; i++) {// 从数组的第二个元素开始循环将数组中的元素插入
            insertNote = a[i];// 设置数组中的第2个元素为第一次循环要插入的数据
            j = i - 1;
            while (j >= 0 && insertNote < a[j]) {
                a[j + 1] = a[j];// 如果要插入的元素小于第j个元素,就将第j个元素向后移动
                j--;
            }
            a[j + 1] = insertNote;// 直到要插入的元素不小于第j个元素,将insertNote插入到数组中
        }
    }

    public static void main(String[] args) {
        int a[] = { 38,65,97,76,13,27,49 };
        insertSort(a);
        System.out.println(Arrays.toString(a));
    }
}

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
#include <iostream>
#include <random>
#include <vector>
#include <ctime>

using std::cin;
using std::cout;
using std::endl;

// ---------

// 插入排序
// O(n^2)

std::vector<int> insertSort(const std::vector<int> & v)
{
    std::vector<int> vector{v.cbegin(), v.cend()};

    int insertNode;
    int i, j;

    for (i = 1; i < vector.size(); ++i)
    {
        insertNode = vector.at(static_cast<u_long>(i));
        j = i - 1;
        while (j >= 0 && insertNode < vector.at(static_cast<u_long>(j)))
        {
            vector.at(static_cast<u_long>(j) + 1) = vector.at(static_cast<u_long>(j));
            --j;
        }
        vector.at(static_cast<u_long>(j) + 1) = insertNode;
    }

    return vector;
}

// -------------------------------------

// 随机数组生成
std::vector<int> vecGen(size_t length)
{
    std::vector<int> vec(length);

    // 以随机值播种，若可能
    std::random_device random_device;

    // 生成无符号随机整数
    static std::default_random_engine engine(random_device());
    // 生成 0 到 99 之间（包含）均匀分布的随机数
    static std::uniform_int_distribution<int> u(0, 99);

    for (int i = 0; i < length; ++i)
    {
        vec[i] = u(engine);
    }

    return vec;
}

// -------------------------------------

// 输出数组
void printArray(std::vector<int> vector)
{
    for (const int i : vector)
    {
        cout << i << " ";
    }
    cout << endl;
}

int main() {

    size_t len;
    clock_t tbegin, tend;

    cout.setf(std::ios::fixed, std::ios::floatfield);

    cout << "求逆序数：" << endl;
    cout << "请输入数组长度：" << endl;
    cin >> len;

    std::vector<int> vector = vecGen(len);
    printArray(vector);

    cout << "插入排序后：" << endl;
    cout << endl;

    tbegin = clock();
    printArray(insertSort(vector));
    tend = clock();
    cout << "花费时间为：" << double(tend - tbegin) / CLOCKS_PER_SEC * 1000<< " ms" << endl;
    cout << endl;

    return 0;
}

归并排序 - Merge Sort

定义

归并排序是一个分治算法（ Divide and Conquer ）的一个典型实例，把一个数组分为两个大小相近（最多差一个）的子数组，分别把子数组都排好序之后通过归并（ Merge ）手法合成一个大的排好序的数组。
归并排序需要额外的空间来存储临时数据，不过它的最坏运行时间都是 $O\left( n\log n\right)$。

代码

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

//Java
import java.util.Arrays;

public class MergeSort {

    public void sortArray(int[] array, int start, int end){

        //单个元素直接返回
        if (start == end){
            return;
        }

        int sort_size = end - start +1; //数组长度
        int separate; //数组的中间元素

        if (sort_size % 2 == 0){ //数组长度为偶数
            separate = start + sort_size/2 - 1;
        }
        else { //数组长度为奇数
            separate = start +sort_size/2;
        }

        sortArray(array,start,separate);  //递归,继续拆分前半部分数组至单个元素
        sortArray(array,separate +1,end);  //递归，继续拆分后半部分数组至单个元素

        mergeArray(array,start,separate,end);   //排序合并

    }

    public void mergeArray(int[] array, int start, int separate, int end){

        int total_size = end - start +1;
        int size1 = separate - start +1;  //前半部分数组长度
        int size2 = end -separate;  //后半部分数组长度

        int[] array1 = new int[size1];
        int[] array2 = new int[size2];

        for (int i = 0; i< size1; i++){
            array1[i] = array[start + i];
        }

        for (int i = 0; i < size2; i++){
            array2[i] = array[separate + 1 + i];
        }

        int merge_count = 0;  //合并后数组长度
        int index1 = 0;     //前半段数组的头
        int index2 = 0;     //后半段数组的头

        while (merge_count < total_size){

            //检查是否已经有一段数组排序完成
            if (index1 == size1){  //前半段数组合并完成，后半段还有多余元素
                for (int i = index2; i< size2; i++){
                    array[start + merge_count] = array2[i];
                    merge_count++;
                    index2++;
                }
            }
            else if (index2 == size2){ //后半段数组合并完成，前半段还有多余元素
                for (int i = index1; i < size1; i++){
                    array[start + merge_count] = array1[i];
                    merge_count++;
                    index1++;
                }
            }
            else{
                int value1 = array1[index1];
                int value2 = array2[index2];

                if (value1 == value2){
                    array[start + merge_count] = value1;
                    array[start + merge_count +1] = value2;
                    merge_count += 2;
                    index1++;
                    index2++;
                }
                else if (value1 < value2){
                    array[start + merge_count] = value1;
                    merge_count++;
                    index1++;
                }
                else {
                    // (value1 > value2)
                    array[start + merge_count] = value2;
                    merge_count++;
                    index2++;
                }
            }

        }

    }

    public static void main(String[] args){

        int array[] = { 10,9,8,7,6,5,4,3,2,1,0,-1 };

        System.out.println("Original array: "+Arrays.toString(array));

        MergeSort ms = new MergeSort();
        ms.sortArray(array,0,array.length-1);

        System.out.println("Merge sorted array: "+Arrays.toString(array));
    }
}

计数排序 - Counting Sort

定义

计数排序（Counting sort）是一种稳定的线性时间排序算法。计数排序使用一个额外的数组 C ，其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数。然后根据数组 C 来将 A 中的元素排到正确的位置。

当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 $O\left( n+k\right)$。计数排序不是比较排序，排序的速度快于任何比较排序算法。

步骤

  1. 找出待排序的数组中最大和最小的元素
  2. 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项
  3. 对所有的计数累加（ 从 C 中的第一个元素开始，每一项和前一项相加 ）
  4. 反向填充目标数组：将每个元素 i 放在新数组的第 C ( i ) 项，每放一个元素就将 C ( i ) 减去 1

图解

counting-sort

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
64
65
66
67
68
69
70

//Java
import java.util.Arrays;

public class CountingSort {

    /*
    计数排序实现
     */

    public void Sort(int[] array){

        //获得最大最小值
        int max_value = array[0];
        int min_value = array[0];

        for (int i = 0; i < array.length; i++){

            if (array[i] < min_value){
                min_value = array[i];
            }
            if (array[i] > max_value){
                max_value = array[i];
            }

        }

        //新建用于统计出现次数的数组
        int[] couting_array = new int[max_value - min_value + 1];

        //计数，array 数组中每出现一个元素，则 counting_array 对应位置计数+1
        for (int i = 0; i < array.length; i++){

            int temp_value = array[i];
            couting_array[temp_value - min_value] += 1;
        }

        //新建临时数组，保存现在 array 中的值
        int[] temp_array = new int[array.length];
        for (int i = 0; i < array.length; i++){
            temp_array[i] = array[i];
        }

        //数组每个元素与前一个叠加，意义为统计小于等于 i 的元素
        for (int i = 1; i < couting_array.length; i++){
            couting_array[i] += couting_array[i - 1];
        }

        //整理
        for (int i = temp_array.length -1; i >=0; i--){
            int temp_value = temp_array[i];
            array[couting_array[temp_value - min_value] - 1] = temp_value;
            couting_array[temp_value - min_value] -= 1;
        }

    }

    public static void main(String[] args){

        CountingSort cs = new CountingSort();

        int[] array = {1, 4, 5, 4, 2, 3, 1};

        System.out.println("Array: "+Arrays.toString(array));
        cs.Sort(array);
        System.out.println("After counting sort: "+Arrays.toString(array));
    }

}

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <iostream>
#include <random>
#include <vector>
#include <ctime>

using std::cin;
using std::cout;
using std::endl;

// ---------

// 插入排序
// O(n^2)

std::vector<int> insertSort(const std::vector<int> & v)
{
    std::vector<int> vector{v.cbegin(), v.cend()};

    int insertNode;
    int i, j;

    for (i = 1; i < vector.size(); ++i)
    {
        insertNode = vector.at(static_cast<u_long>(i));
        j = i - 1;
        while (j >= 0 && insertNode < vector.at(static_cast<u_long>(j)))
        {
            vector.at(static_cast<u_long>(j) + 1) = vector.at(static_cast<u_long>(j));
            --j;
        }
        vector.at(static_cast<u_long>(j) + 1) = insertNode;
    }

    return vector;
}

// 计数排序
// O(n + k)

std::vector<int> CountingSort(const std::vector<int> & v)
{
    std::vector<int> vector(v.size());

    // 最大最小值
    int max_value = *std::max_element(v.cbegin(), v.cend());
    int min_value = *std::min_element(v.cbegin(), v.cend());

    // 用于存放统计出现次数
    std::vector<int> store(static_cast<u_long>(max_value - min_value + 1));

    // 计数，vector 中每出现一个元素，则 store 对应位置计数 + 1
    for (const auto & i : v)
    {
        ++store.at(static_cast<u_long >(i - min_value));
    }

    // 数组每个元素与前一个叠加，意义为统计小于等于 i 的元素

    for (size_t j = 1; j < store.size(); ++j)
    {
        store.at(j) += store.at(j - 1);
    }


    for (size_t k = vector.size() - 1; k >= 0 && k < vector.size() /* 注意：size_t 是无符号类型 */; --k)
    {
        int value = v.at(k);
        vector.at(static_cast<u_long>(--store.at(static_cast<u_long>(value - min_value)))) = value;
    }

    return vector;
}

// -------------------------------------

// 随机数组生成
std::vector<int> vecGen(size_t length)
{
    std::vector<int> vec(length);

    // 以随机值播种，若可能
    std::random_device random_device;

    // 生成无符号随机整数
    static std::default_random_engine engine(random_device());
    // 生成 0 到 99 之间（包含）均匀分布的随机数
    static std::uniform_int_distribution<int> u(0, 99);

    for (int i = 0; i < length; ++i)
    {
        vec[i] = u(engine);
    }

    return vec;
}

// -------------------------------------

// 输出数组
void printArray(std::vector<int> vector)
{
    for (const int i : vector)
    {
        cout << i << " ";
    }
    cout << endl;
}

int main() {

    size_t len;
    clock_t tbegin, tend;

    cout.setf(std::ios::fixed, std::ios::floatfield);

    cout << "计数排序：" << endl;
    cout << "请输入数组长度：" << endl;
    cin >> len;

    std::vector<int> vector = vecGen(len);
    printArray(vector);

    cout << "计数排序后：" << endl;

    tbegin = clock();
    printArray(CountingSort(vector));
    tend = clock();
    cout << "花费时间为：" << double(tend - tbegin) / CLOCKS_PER_SEC * 1000<< " ms" << endl;
    cout << endl;

    cout << "插入排序：" << endl;
    cout << "插入排序后：" << endl;

    tbegin = clock();
    printArray(insertSort(vector));
    tend = clock();
    cout << "花费时间为：" << double(tend - tbegin) / CLOCKS_PER_SEC * 1000<< " ms" << endl;
    cout << endl;

    return 0;
}

基数排序 - Radix Sort

定义

基数排序是一种非比较型整数排序算法，其原理是将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

效率

基数排序的时间复杂度是 $O\left( k\times n\right)$，其中 n 是排序元素个数，k 是数字位数。注意这不是说这个时间复杂度一定优于，k 的大小取决于数字位的选择（ 比如比特位数 ），和待排序数据所属数据类型的全集的大小；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

//Java
import java.util.Arrays;

public class RadixSort {

    /*
    基数排序实现,最低位优先比较
    radix 为基数，digit 为最大出现数字的位数
     */
    public void SortArray(int[] array, int radix, int digit){

        //临时数组
        int[] temp_array = new int[array.length];
        //count 数组记录某位上是 i 的数字的个数
        int[] count_array = new int[radix];

        //从个位开始比较
        int rate = 1;

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

            //临时数组初始化
            Arrays.fill(count_array, 0);
            //数组拷贝
            System.arraycopy(array, 0, temp_array, 0, array.length);

            //统计每个位上数字出现的次数
            for (int j = 0; j < array.length; j++){
                int temp_value = (temp_array[j] / rate) % radix;
                count_array[temp_value]++;
            }

            //统计 count_array 数组前 n 位元素（包括 n ）有多少元素
            for (int j = 1; j < radix; j++){
                count_array[j] += count_array[j - 1];
            }

            //从后往前整理，保证稳定性
            for (int j = array.length - 1; j >= 0; j--){
                int temp_value = (temp_array[j] / rate) % radix;
                array[--count_array[temp_value]] = temp_array[j];
            }

            //前进一位
            rate *= radix;

        }
    }

    public static void main(String[] args){

        int[] array = {1234, 123, 89, 72, 345, 23, 12, 1};

        RadixSort rs = new RadixSort();

        System.out.println("Origin array: " + Arrays.toString(array));
        rs.SortArray(array,10,4);
        System.out.println("Radix sort: "+ Arrays.toString(array));
    }

}

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <iostream>
#include <random>
#include <vector>
#include <ctime>

using std::cin;
using std::cout;
using std::endl;

// 计数排序
// O(n + k)

std::vector<int> countingSort(const std::vector<int> & v)
{
    std::vector<int> vector(v.size());

    // 最大最小值
    int max_value = *std::max_element(v.cbegin(), v.cend());
    int min_value = *std::min_element(v.cbegin(), v.cend());

    // 用于存放统计出现次数
    std::vector<int> store(static_cast<u_long>(max_value - min_value + 1));

    // 计数，vector 中每出现一个元素，则 store 对应位置计数 + 1
    for (const auto & i : v)
    {
        ++store.at(static_cast<u_long >(i - min_value));
    }

    // 数组每个元素与前一个叠加，意义为统计小于等于 i 的元素

    for (size_t j = 1; j < store.size(); ++j)
    {
        store.at(j) += store.at(j - 1);
    }


    for (size_t k = vector.size() - 1; k >= 0 && k < vector.size() /* 注意：size_t 是无符号类型 */; --k)
    {
        int value = v.at(k);
        vector.at(static_cast<u_long>(--store.at(static_cast<u_long>(value - min_value)))) = value;
    }

    return vector;
}

// 基数排序
// O(n * k)

// radix 代表位数，digit 代表出现最大值的位数
std::vector<int> radixSort(const std::vector<int> & v, int radix, int digit)
{
    std::vector<int> temp_vector{v.cbegin(), v.cend()};
    std::vector<int> vector(v.size());

    // 从个位开始比较
    int rate = 1;

    for (int i = 0; i < digit; ++i)
    {
        std::vector<int> count_vector(static_cast<u_long>(radix));

        // 统计每个位上数字出现的次数
        for (int j = 0; j < v.size(); ++j)
        {
            int temp_value = (temp_vector.at(static_cast<u_long>(j)) / rate) % radix;
            ++count_vector.at(static_cast<u_long>(temp_value));
        }

        // 统计 count_array 数组前 n 位元素（包括 n）有多少元素
        for (int k = 1; k < radix; ++k)
        {
            count_vector.at(static_cast<u_long>(k)) += count_vector.at(static_cast<u_long>(k - 1));
        }

        // 从后往前整理，类似于计数排序
        for (int l = static_cast<int>(v.size()) - 1; l >= 0; --l)
        {
            int temp_value = (temp_vector.at(static_cast<u_long>(l)) / rate) % radix;
            vector.at(static_cast<u_long>(--count_vector.at(static_cast<u_long>(temp_value)))) = temp_vector.at(static_cast<u_long>(l));
        }

        rate *= radix;
        temp_vector = {vector.cbegin(), vector.cend()};
    }

    return vector;
}

// -------------------------------------

// 随机数组生成
std::vector<int> vecGen(size_t length)
{
    std::vector<int> vec(length);

    // 以随机值播种，若可能
    std::random_device random_device;

    // 生成无符号随机整数
    static std::default_random_engine engine(random_device());
    // 生成 0 到 99 之间（包含）均匀分布的随机数
    static std::uniform_int_distribution<int> u(0, 99);

    for (int i = 0; i < length; ++i)
    {
        vec[i] = u(engine);
    }

    return vec;
}

// -------------------------------------

// 输出数组
void printArray(std::vector<int> vector)
{
    for (const int i : vector)
    {
        cout << i << " ";
    }
    cout << endl;
}

int main() {

    size_t len;
    clock_t tbegin, tend;

    cout.setf(std::ios::fixed, std::ios::floatfield);

    cout << "基数排序：" << endl;
    cout << "请输入数组长度：" << endl;
    cin >> len;

    std::vector<int> vector = vecGen(len);
    printArray(vector);

    cout << "基数排序后：" << endl;

    tbegin = clock();
    printArray(radixSort(vector, 10, 2));
    tend = clock();
    cout << "花费时间为：" << double(tend - tbegin) / CLOCKS_PER_SEC * 1000<< " ms" << endl;
    cout << endl;

    cout << "计数排序：" << endl;
    cout << "计数排序后：" << endl;

    tbegin = clock();
    printArray(countingSort(vector));
    tend = clock();
    cout << "花费时间为：" << double(tend - tbegin) / CLOCKS_PER_SEC * 1000<< " ms" << endl;
    cout << endl;

    return 0;
}

参考