Fork me on GitHub

数据结构与算法之美【排序】

冒泡排序、插入排序、选择排序、归并排序、快速排序、桶排序、计数排序、基数排序!

[TOC]

一、如何分析一个“排序算法”

1、排序算法的执行效率

  • 最好、最好、平均时间复杂度

分析三种复杂度,还要分析出最好、最坏时间复杂度对应的要排列的原始数据是什么样的。

  • 时间复杂度的系数、常数、低阶

时间复杂度反应的是数据规模 n 很大的时候的一个增长趋势,所以它表示的时候会忽略系数、常数、低阶。数据规模可能很小,10、100、1000,我们就必须把系数、常数、低阶考虑进来。

  • 比较次数和交换(或移动)次数

基于比较的排序算法的执行过程,会涉及到比较和交换。如果我们在分析排序算法的执行效率的时候,应该把比较次数和交换(或移动)次数也考虑进去。

2、排序算法的内存消耗

算法的内存消耗可以通过空间复杂度来衡量。

  • 原地排序算法

就是指特定空间复杂度是 O(1) 的排序算法。

  • 稳定排序算法

如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。

例子:

稳定排序,电商系统按照金额的排序,相同金额按时间早晚排序(先排时间,后排金额 [相同的后操作紫自动调整])。

二、插入排序、冒泡排序、选择排序 O(n²)

1、冒泡排序

冒泡排序思路

每次冒泡对相邻的两个元素进行比较,看是否满足大小关系,不满足就进行互换,一次冒泡会让至少一个元素移动到它应该在的位置。有 n 个数据,需要重复 n 次。

冒泡排序优化

当某次冒泡过程已经没有数据交换时,说明已经达到完全有序,不用再执行后续的冒泡操作。

冒泡排序是原地排序算法吗?

答:

分析:冒泡的过程只涉及相邻数据的交换操作,只需要常量级的临时空间,所以它的空间复杂度为 O(1),是一个原地排序算法。

■ 冒泡排序是稳定的排序算法吗?

答:

分析:当有相邻的两个元素大小相等的时候,我们不做交换,所以冒泡排序是稳定的排序算法。

■ 冒泡排序的时间复杂度是多少?

最好的情况是数据已经排好序,我们只进行一次冒泡排序就可以了,最好时间复杂度为 O(n) 。最坏的情况是,要排序的数据刚好是倒序排列的,我们只进行 n 此冒泡操作,所以最坏的时间复杂度为 O(n²)平均时间复杂度为 O(n²)。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 冒泡排序,a 表示数组,n 表示数组大小
public void bubbleSort(int[] a, int n) {
if (n <= 1) return;

for (int i = 0; i < n; ++i) {
// 提前退出冒泡循环的标志位
boolean flag = false;
for (int j = 0; j < n - i - 1; ++j) {
if (a[j] > a[j+1]) { // 交换
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true; // 表示有数据交换
}
}
if (!flag) break; // 没有数据交换,提前退出
}
}

2、插入排序

插入排序思想

将数据分为两个区间,未排序和已排序区间。初始化已排序只有一个元素(默认第一个),从未排序选出元素找到合适位置有序的插入,直到结束位置。

■ 插入排序是原地排序算法吗?

答:是。

分析:插入排序的运算并不需要额外的存储空间,所以空间复杂度是 O(1),是一个原地排序算法

插入排序是稳定的排序算法吗?

答:是。

分析: 对于值相同的元素,我们会将后边出现的元素插入到前边出现的元素的后边,所以插入排序是稳定排序

■ 插入排序的时间复杂度是多少?

最好的情况就是数据元素已经排好序,最好的时间复杂度为 O(1)。如果数组是倒序的,最坏的时间复杂度是 O(n²)。在数组中插入数据的平均时间复杂度为 O(n),对于插入排序来说我们每次就相当于数组插入一个新的数据,循环执行n次插入数据,所以平均时间复杂度为 O(n²)。

■ 插入排序代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 插入排序,a 表示数组,n 表示数组大小(从小到大进行排序)
public void insertionSort(int[] a, int n) {
//如果数组大小为 1 直接返回
if (n <= 1) return;
//否则进行插入排序
for (int i = 1; i < n; ++i) {
int value = a[i];
int j = i - 1;
// 查找插入的位置
for (; j >= 0; --j) {
if (a[j] > value) {
a[j+1] = a[j]; // 数据移动
} else {
break;
}
}
a[j+1] = value; // 插入数据
}
}

3、选择排序

■ 选择排序算法思想

将在未排序期间寻找到最小的数据,并将其放到已排好区间的元素的尾部。

■ 选择排序是原地排序算法吗?

答: 原地排序算法。

分析: 数组中的两个元素需要相互交换,需要用一个变量来存储交换值,选择排序的空间复杂度为O(1),所以,是一种原地排序算法。

选择排序是稳定的排序算法吗?

答 :不是。

分析:选择排序每次都要找到剩余未排序元素的最小值,并和前边的元素交换位置,这样破坏了稳定性。所以说,选择排序是一种不稳定的排序算法。

■ 选择排序的时间复杂度是多少?

最好的时间复杂度为 O(1),最坏的情况就是 O(n²)。平均时间复杂度就是 O(n²)

4、希尔排序

插入排序有很大的优化思路,进而有了希尔排序。

5、思考:为什么插入排序比冒泡排序更受欢迎

移动次数:冒泡排序和插入排序是同样的,不管怎么优化,元素移动的次数也等于原始数据的逆序度。

代码实现:,冒泡排序的数据交换要比插入排序的数据移动要复杂,冒泡排序需要 3 个赋值操作,而插入排序只需要 1 个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//冒泡排序中数据的交换操作:
if (a[j] > a[j+1]) { // 交换
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true;
}

//插入排序中数据的移动操作:
if (a[j] > value) {
a[j+1] = a[j]; // 数据移动
} else {
break;
}

三、归并排序、快速排序 O(nlogn)

1、归并排序

■ 核心思想

假入排序一个数组,先把数组从中间分成前后两个部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就有序了。

■ 实现过程

使用分治思想,分治思想用递归来实现,分析写出递归公式,找出终止条件,最后将递推公式翻译成递归代码。

■ 递推公式

1
2
3
4
5
递推公式:
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))

终止条件:
p >= r 不用再继续分解

■ 递归代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 归并排序算法, A 是数组,n 表示数组大小
merge_sort(A, n) {
merge_sort_c(A, 0, n-1)
}

// 递归调用函数
merge_sort_c(A, p, r) {
// 递归终止条件
if p >= r then return

// 取 p 到 r 之间的中间位置 q
q = (p+r) / 2
// 分治递归
merge_sort_c(A, p, q)
merge_sort_c(A, q+1, r)
// 将 A[p...q] 和 A[q+1...r] 合并为 A[p...r]
merge(A[p...r], A[p...q], A[q+1...r])
}

合并函数(merge函数)+ 哨兵思想

仿照两个有序数组的合并。

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
merge(A[p...r], A[p...q], A[q+1...r]) {
var i := p,j := q+1,k := 0 // 初始化变量 i, j, k
var tmp := new array[0...r-p] // 申请一个大小跟 A[p...r] 一样的临时数组
while i<=q AND j<=r do {
if A[i] <= A[j] {
tmp[k++] = A[i++] // i++ 等于 i:=i+1
} else {
tmp[k++] = A[j++]
}
}

// 判断哪个子数组中有剩余的数据
var start := i,end := q
if j<=r then start := j, end:=r

// 将剩余的数据拷贝到临时数组 tmp
while start <= end do {
tmp[k++] = A[start++]
}

// 将 tmp 中的数组拷贝回 A[p...r]
for i:=0 to r-p do {
A[p+i] = tmp[i]
}
}

代码分析

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
package com.test.xiaolu;


/**
* 归并排序
* @author 小鹿
*
*/
public class MergeSort {
public static void main(String[] args) {
MergeSort mSort = new MergeSort();
int[] a = new int[] {4,3,7,2,9,1};
mSort.mergeSort(a,0,a.length-1);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]);
}
}

/**
* 功能:递归分治数据
* @param a 要分治的数组
* @param p 数组起始位置
* @param r 数组终止位置
*/
public void mergeSort(int[] a,int p,int r) {
//终止条件
if(p >= r) return;

//取p到r之间的中间位置q,防止(p+r)的和超过int类型最大值
int q = p + (r - p)/2;

//递归分治
mergeSort(a,p,q);
mergeSort(a,q+1,r);

//两个有序数组的合并
merge(a, p, q, r);

}

/**
* 功能: 合并 mergr
* @param a 要合并的数组
* @param p 数组起始的下标
* @param q 第二个数组起始的下标
* @param r 数组结束的下标
*/
public void merge(int[] a,int p,int q,int r) {
int i = p,j = q+1,k = 0;
int[] temp = new int[r-p+1];

//两个有序数组合并
while(i <= q && j <= r) {
if(a[i] <= a[j]) {
temp[k++] = a[i++];
}else {
temp[k++] = a[j++];
}
}

int s = i;
int e = q;
if(j <= r) {
s = j;
e = r;
}

//剩余的数据添加到尾部
while(s <= e) {
temp[k++] = a[s++];
}

//将 temp 数据搬移到原数组
for (int l = 0; l <= r-p; l++) {
a[p+l] = temp[l];
}
}
}

性能分析

  • 归并排序是否是稳定排序算法?

答:是的。

分析:只看 merge 合并函数,如果有两个相同的元素,当然先放排在最前边的元素,两个相同元素的位置不变,所以说,归并排序是稳定排序。

  • 归并排序是否是原地排序算法?

1、不能用递归思想了,用完系统直接释放掉了。

2、merge 额外的空间 temp。在任意时刻,CPU 只有一个函数在使用,也就是说我们呢开辟一个 n 大小数组空间就可以了,空间复杂度为 O(n)。因此,归并排序不是原地排序算法。

  • 归并排序的时间复杂度是多少?

答:O(nlogn)。

分析:

1、 A 问题分为 B 问题和 C 问题,时间复杂度为 B 问题加上 C 问题再加上合并的时间。

2、假设对 n 个元素进行归并排序的时间复杂度为 T(n) 。分解两个子数组的时间为 2*T(n/2)。合并两个有序子数据的时间复杂度为 n(n),我们就可以推导出时间复杂度的计算公式。

1
2
1T(1) = C;   n=1 时,只需要常量级的执行时间,所以表示为 C。
O(n) = 2T(n) = 2*T(n/2) + n; n>1
1
2
3
4
5
6
7
T(n) = 2*T(n/2) + n
= 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
= 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
= 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
......
= 2^k * T(n/2^k) + k * n
......

可以推导出 T(n) = 2^kT(n/2^k)+kn ,当 T(n/2^k)=T(1) 时,也就是 n/2^k=1,我们得到 k=log2n ,我们将 k 值代入上面的公式,得到 T(n)=Cn+nlog2n 。所以归并排序的时间复杂度为 O(nlogn)

  • 稳定性

归并排序和原始数据的有序程度无关,所以时间复杂度与是非常稳定的。

2、快速排序

核心思想

有一组数据,数组中的下标是 p 到 r 。在 p 到 r 之间任意选择一个数据作为 pivot (区分点)。大于区分点的放到右边(q+1 到 r),小于区分点的放到左边(p 到 q-1),将 pivot 数据放中间。

递推公式

1
2
3
4
5
递推公式:
quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1, r)

终止条件:
p >= r

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
// 快速排序,A 是数组,n 表示数组的大小
quick_sort(A, n) {
quick_sort_c(A, 0, n-1)
}
// 快速排序递归函数,p,r 为下标
quick_sort_c(A, p, r) {
if p >= r then return

// 获取分区点(一般情况,选择最后一个元素)
q = partition(A, p, r)
quick_sort_c(A, p, q-1)
quick_sort_c(A, q+1, r)
}

partition() 分区函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private static int partition(int[] a, int p, int r) {
int pivot = a[r];
int i = p;
for(int j = p; j < r; ++j) {
if (a[j] < pivot) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
++i;
}
}

int tmp = a[i];
a[i] = a[r];
a[r] = tmp;

System.out.println("i=" + i);
return i;
}

注意:要想实现原地排序,不能用两个数组的合并了,必须在数组内完成,所以有了下边的操作。

  • 交换技巧

如果插入数据,数据搬移,非常耗时。上述的数据插入正是一种交换的技巧,在 O(1) 时间内进行插入小于pirot 的位置。

■ 代码实现

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
package com.test.xiaolu;


/**
* 功能:快速排序
* @author 小鹿
*
*/
public class QuickSort {


public static void main(String[] args) {
QuickSort quickSort = new QuickSort();
int[] a = new int[] {4,3,7,2,9,1};
quickSort.quickSort(a, 6);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+" ");
}
}

public void quickSort(int a[],int n) {
quickSortInternally(a,0,n-1);
}

/**
* 功能:快速排序递归函数
* @param a 数组
* @param i 起始位置
* @param j 终止位置
*/
private void quickSortInternally(int[] a, int p, int r) {
//终止条件
if(p >= r) return;

//获取区分点 pivot
int q = partition(a, p, r);

//区分点两端开始递归
quickSortInternally(a,p,q-1);
quickSortInternally(a,q+1,r);
}

/**
* 功能:获取区分点
* @param a 数组
* @param p 起始位置
* @param r 终止位置
* @return 返回区分点
*/
public int partition(int[] a,int p,int r) {
//将最后一个元素作为区分点
int pivot = a[r];
int i = p;

for (int j = p; j < r; ++j) {
if(a[j] < pivot) {
//确保 i 永远指向第一个大于 pivot 的数
if(i == j) {
i++;
}else {
int tmp = a[i];
a[i++] = a[j];
a[j] = tmp;
}
}
}

int temp = a[i];
a[i] = a[r];
a[r] = temp;

System.out.println("i=" + i);
return i;
}
}

■ 性能分析

  • 快排是否为稳定排序算法?

答:不是。

分析:排序函数 partition 随机的位置,交换会导致相同元素位置会发生改变,所以快排是不稳定算法。

  • 快排是否为原地排序算法?

答:是的。

分析:在空间复杂度 O(1) 内进行对数据的排序,所以是原地排序算法。

  • 快排的复杂度分析?

最好时间复杂度:O(nlogn)。

分析:每次选择的 pivot 合适,正好将区间一分为二,但是不切合实际情况。

最坏时间复杂度: O(n2) 。

一个有序数据,每次分区点都是最后一个,需要进行 n 次分区才能完成快排,每次分区扫描 n/2 个元素,时间复杂度退化到 O(n2) 。

平均时间复杂度:O(nlogn)

分析:快排的大部分情况的时间复杂度为 O(nlogn),只有极端情况为 O(n²) , 有很多方法可以降低这种极端情况下的概率。

4、归并排序和快速排序的区别

1、归并排序数据的有序性是从下到上的,而快速排序的数据有序性是从上到下的。

2、归并排序是稳定的排序算法(和数据的有序性无关),但是不是原地排序算法,合并不能在原地执行,空间复杂度为O(n)。

3、快速排序解决了归并排序占用太多内存空间的问题,在原地就可以实现排序。

6、思考:如何用快排思想在 O(n) 内查找第 K 大元素?

实现思路

求某数据中第 K 大数据,先将 r[n-1] 作为区分点划分,如果 p+1 = k,则 a[p] 就是要找到的数据(数组下标从 0 开始的)。如果 k < p+1 第 k 大数据在 [0,p] 之间,如果 k > p+1 ,第 k 大数据在 [p+1,r] 之间。进而继续划分查找。

代码实现

复杂度分析

每次查找都是数据的一半,所以查找的时间复杂度就是(n/2+n/4+n/8+… = 2n-1),O(n)。另一种方法是每次寻找数据中的最小值放到数据的首部,查找 n 次就可以了,时间复杂度为 K*n,当 k 小的时候可以,当 k 为 n/2 或者 n 的时候,时间复杂度退化成 O(n²);

7、扩展提高

现在你有 10 个接口访问日志文件,每个日志文件大小约 300MB,每个文件里的日志都是按照时间戳从小到大排序的。你希望将这 10 个较小的日志文件,合并为 1 个日志文件,合并之后的日志仍然按照时间戳从小到大排列。如果处理上述排序任务的机器内存只有 1GB,你有什么好的解决思路,能“快速”地将这 10 个日志文件合并吗?

同时指向10个文件的第一条数据,进行比较选出最小时间戳的数据放入新文件,一次类推,有 n个数据需要比较 n 次,时间复杂度为 O(n) ,空间复杂度为 O(1) 。

四、桶排序、计数排序、基数排序

1、桶排序(Bucket sort)

算法思想

对每个桶划定范围,将数据分别放到不同的桶中进行排序,然后依次取出每个桶中的数据,组成的序列就是有序的了。

时间复杂度分析

答:O(n)。

分析:假设有 n 个数据,分到 m 个桶中,每个桶中平均放 k=n/m 。每个桶中的数据以时间复杂度 O(k logk) 进行排序,m 个桶时间复杂度为 mk*logk ,因为 k = n/m ,所以时间复杂度为 O(n*log(n/m)) 。当桶的个数趋近于数据的个数的时候(m->n),桶排序的时间复杂度为 O(n)。

适用条件

1、桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中,数据量比较大,内存有限,无法将数据全部加载到内存中。

2、各个桶内的数据必须是均匀分布的。在极端情况下,分布到同一个桶中,时间复杂度退化到 O(nlogn)。

实例分析

  • 问题

有 10GB 的订单数据,我们希望按订单金额(假设金额都是正整数)进行排序,但是内存有限,只有几百 MB,没办法一次性把 10GB 的数据都加载到内存中。这个时候该怎么办呢?

  • 解决思路

步骤一:

扫描一遍文件,假设订单金额数据范围,最小 1 元,最高 10 万元。然后划定金额平均分到 100 个桶中,每个桶中 1 - 1000 ,以此类推。然后从 0 编号,到 99 号桶。

步骤二:

① 情况一:平均分配到桶中。

每个桶进行快速排序,100 个桶排好之后,依次按照编号进行取出数据。

② 情况二:不平均分配每个桶。

每个桶中的数据各不相同,有的桶中的数据会大于内存,继续划分桶内数据多的,比如 1 - 1000 比较多,我们划分 10 个区间,然后进行快速排序。

2、计数排序(Counting sort)

算法思想

计数排序是桶排序的一种特殊情况,当要排序 n 个数据的时候,所处的范围并不大,最大值为 K ,将数据划分为 K 个桶,每个桶内的值都是相同的,省去了桶内排序的时间。

适用条件

① 计数排序应用于数据范围不大的场景中,如果数据范围 k 要比排序的数据 n 大很多,就不适用了。

② 计数排序只能给非负整数排序,可以再不改变相对大小的情况下,转化为非负整数。

算法过程

  • 实例分析

有八个考生,分数分别再0-5之间,将这八个考生的成绩放入到数组A【8】中,它们分别是 2,5,3,0,2,3,0,3 。

  • 步骤

① 给定一组数据 ,先寻找数组中的最大值 max。(上述中是 5)

② 再新定义一个数组 C[max+1] ,将其初始化为 0。(计数数组,下标对应着分数 0-5 分)

③ 将遍历所有的数据根据下标(分数)统计的相同分数的学生个数放入到对应下标分数的数组 C 。

④ 对数组 C 中存储的相同分数学生的个数顺序依次求和,重新放回数组 C 中。

⑤ 从数组 A[8] 中,倒序依次取数据做判断,根据数组中存取的数据与数组 C 找下标相同的数据,C 中与该分数相同的数字下标存储的就是当前包括该分数在内的小于该分数的学生个数。

⑥ 我们将新定义一个数组R,其实该个数就是该学生的排名,放在 R 数组中就需要 -1 (毕竟数组是从 0 开始的)。

⑦ 依次倒序遍历上述的数组 A 中的数据,重复上述过程,直到将数据排好序,将排序结果复制到 A 数组中。

代码实现

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
// 计数排序,a 是数组,n 是数组大小。假设数组中存储的都是非负整数。
public void countingSort(int[] a, int n) {
// 判断数组是否有数据
if (n <= 1) return;

// 1、查找数组中数据的最大值,给定范围
int max = a[0];
for (int i = 1; i < n; ++i) {
if (max < a[i]) {
max = a[i];
}
}

// 2、申请一个计数数组 c,下标大小 [0,max]
int[] c = new int[max + 1];
for (int i = 0; i <= max; ++i) {
c[i] = 0;
}

// 3、计算每个元素的个数,放入 c 中
for (int i = 0; i < n; ++i) {
c[a[i]]++;
}

// 4、依次累加
for (int i = 1; i <= max; ++i) {
c[i] = c[i-1] + c[i];
}

// 5、6、临时数组 r,存储排序之后的结果
int[] r = new int[n];
for (int i = n - 1; i >= 0; --i) {
int index = c[a[i]]-1;
r[index] = a[i];
c[a[i]]--;
}

// 7、将结果拷贝给 a 数组
for (int i = 0; i < n; ++i) {
a[i] = r[i];
}
}

实际实例

在高考中怎么知道自己排名?假如有 50 万考生,最高分是 900 分,最低分是 0 分,我们就划分为 901 个桶。将 50 万的学生成绩分别放到这 901 个桶中。然后遍历桶中的数据依次放入一个数组中,那么就排好序了!

技巧扩展

1、如果是小数,精确到小数点后一位,先将所有数据乘以 10,转化成整数,再放到 9010 个桶中。

2、如果排序的数据有负数,数据范围为【-1000,1000】,需要先对每个数据加 1000,转化成非负数。

3、基数排序(Radix sort)

算法思路

借助稳定排序算法,先将低位的进行排序(或相同数据),然后以此类推。

适用条件

1、数据分割成 “位” 来比较,位之间有递进关系。

2、每一位的数据范围不能太大,否则无法做到时间复杂度为 O(n) 了。

时间复杂度

如果要排序的数据有 k 位,就要进行 k 次桶排序或者计数排序,总时间复杂度为 O(K*n)。当 K 不大的时候,基数排序的复杂度就接近于 O(n)。

举例分析

  • 问题

对十万个手机号从小到大进行排序。

  • 解决

先按照最后一位来排序手机号码,然后,再按照倒数第二位重新排序,以此类推,最后按照第一位重新排序。经过 11 次排序之后,手机号码就都有序了。

扩展思考

给牛津的 20 万单词进行排序。单词长短不齐,我们补充 0 ,因为所有字母都大于 “0”,不会影响顺序,然后进行基数排序。

4、思考:如何根据年龄给 100 万用户排序?

答:桶排序

分析: 假设年龄范围为 1 到 120 岁,分为 120 个桶并编号 0 - 119,将 100 万数据放到相对应的桶中,然后依次按照桶的编号取出数据,这样都得到了 100 万的数据,时间复杂度为 O(n)。