数据结构与算法之美3_排序&二分查找

发表于 | | 阅读次数: |
字数统计: 5,461 字 | 阅读时长 ≈ 23 分钟

数据结构与算法之美3_排序&二分查找


本系列文章，算是《极客时间》的《数据结构与算法之美》专栏的读书笔记。

只是一些个人心得与练习，想要得到更详细更好更系统的学习，请去 极客时间APP订阅专栏。

跟着专栏学了好久，也该有点成果不是；

正好趁着最后的几篇练习章节，把之前学到的，做个笔记总结一下。

笔记列表



回顾

排序

分析标准

执行效率（时间复杂度）

  • 最好情况、最坏情况、平均情况的 时间复杂度
  • 时间复杂度的 系数、常数、低阶
  • 比较次数 与 交换（或移动）次数

内存消耗（空间复杂度）

  • 是否原地排序（空间复杂度O(1)）

稳定性

  • 稳定排序算法可以保持两个相同数值的对象，在排序之后的前后顺序不变。

分析方法

在计算 执行效率 的时候，如果用概率论的方法定量分析平均时间复杂度，设计的数学推理和计算会比较复杂，专栏作者使用了一些概念来辅助分析

有序度

有序度指数组中具有有序关系的元素对个数。

比如 4,7,2,1,9,3 数据中，有序度为 7，有序元素对为 (4, 7), (4, 9), (7, 9), (2, 9), (2, 3), (1, 9), (1, 3)

逆序度

逆序度指数组中具有逆序关系的元素对个数

比如 4, 7, 2, 1, 9, 3 数据中，逆序度为 8, 逆序元素对为 (4, 2), (4, 1), (4, 3), (7, 2), (7, 1), (7, 3), (2, 1), (9, 3)


经典排序算法

冒泡排序

概述

不断遍历被排序数列，每次只操作相邻的两个元素，将两者比较，按照大小关系决定是否交换位置。

冒泡排序有两种操作，元素的比较 与 元素的交换。

伪代码
1
2
3
4
5
6
7
8
9
10
11
/*arr 待排序数组；n 待排序数组长度*/
for i:=0 to n-1 do
    isFinish := true
    for j:=0 to n-i do
        if arr[j] < arr[j+1] then 
        	swap arr[j] with arr[j+1]
            isFinish := false
    end
            
    if isFinish then exit
end
分析
执行效率

  • 最好的情况，数组为顺序排列。需要执行 1 次冒泡操作，时间复杂度为 O(1)

  • 最坏的情况，数组为逆序排列。需要执行 n 次冒泡操作，时间复杂度为 O(n^2)

  • 平均的情况，取最好和最坏的中间值，(1 + n*(n - 1)/2)/2 = 1/2 + n*(n- 1)/4 = n*(n - 1)/4，时间复杂度为 O(n^2)

内存消耗

冒泡排序比较并交换相邻元素，只需要常量级的临时空间，空间复杂度为 O(1)，所以 是原地排序 算法。

稳定性

冒泡排序在比较时，可以设定相邻元素大小相等时不交换，因此相同大小的数据顺序在排序前后不会改变顺序，所以是 稳定 的排序算法。

插入排序

概述

数组可以分为两个区间，已排序区间 与 未排序区间；不断取未排序区间的元素插入到已排序区间的合适位置。

插入排序有两种操作，元素的比较 与 元素的移动。

伪代码
1
2
3
4
5
6
7
8
9
10
11
12
13
/*arr 待排序数组；n 待排序数组长度*/
for i:=1 to n-1 do
	waitInsert := arr[i]
	j := i-1
	while j ≥ 0 do
		if arr[j] > waitInsert 
			then arr[j+1] := arr[j]
			else exit
		j := j-1
	end
	
	arr[j+1] := waitInsert
end
分析
执行效率

最好的情况，数组为逆序排列，不需要元素移动，比较一个数据即可插入元素，进行 n 次比较，时间复杂度为 O(n)。

最坏的情况，数组为顺序排列，每次都要与每个已排序区间元素比较并移动每个元素，时间复杂度为 O(n^2)。

平均的情况，每次插入操作都相当于在数组中插入一个数据，在数据中插入一个数据的平均时间复杂度为O(n)，循环执行n次插入操作，所以时间复杂度为 O(n^2)。

内存消耗

插入排序时，不需要额外的存储空间，空间复杂度为 O(1) ，所以 是原地排序 算法。

稳定性

插入排序时，可以选择将后面出现的元素，插入到前面出现元素的后面，从而保证原有顺序不变，所以是 稳定 的排序算法。

选择排序

概述

选择排序也分为已排序区间与未排序区间，每次选择未排序区间最小的元素，放到已排序区间最后位置。

选择排序只有一种操作，比较元素。

伪代码
1
2
3
4
5
6
7
8
9
10
11
/*arr 待排序数组；n 待排序数组长度*/
for i:=0 to n-2 do
	minIndex := i
	for j:=i+1 to n-1 do
		if arr[minIndex] > arr[j] then 
			minIndex := j
	end
	
	if minIndex ≠ i then 
		swap arr[i] with arr[minIndex]
end
分析
执行效率

选择排序的最好、最差、平均复杂度均为O(n^2)。因为主要步骤是进行元素的比较，此步骤并不会随着初始状态而改变。

内存消耗

选择排序时，只需要常量级的临时空间，空间复杂度为O(1)，所以 是原地排序 算法。

稳定性

选择排序会进行元素的交换，会导致顺序发生变化，所以它是一个 不稳定 的排序算法。

比如，2 2 1，将1与2交换后，2的先后顺序发生了变化。

归并排序

概述

归并排序的核心思想是分治。

可以分为两部分，分解和合并。

分解：先将数组从中间一分为二，每部分继续一分为二，直到每部分只有一个元素。

合并：将相邻两部分按顺序合并，合并到最后。

伪代码
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
/*arr 待排序数组；front首索引；rear尾索引*/
merge_sort(arr, front, rear)
{
    if front ≥ rear then return
    
    mid := (front+rear)/2
    merge_sort(arr, front, mid)
    merge_sort(arr, mid+1, rear)
    
    merge(arr, front, mid, rear)
}

/*arr 待排序数组；front首索引；mid中间索引；rear尾索引；tempArr中间过渡数组*/
merge(arr, front, mid, rear, tempArr)
{
    i := front
    j := mid+1
    k := 0
    
    while i ≤ mid and j ≤ rear do
    	if arr[i] ≤ arr[j] 
    		then 
    			tempArr[k] := arr[i]
    			k := k+1
    			i := i+1
    		else
    			tempArr[k] := arr[j]
    			k := k+1
    			j := j+1
    end
    while i ≤ mid do
    	tempArr[k] := arr[i]
    	k := k+1
    	i := i+1
    end
    while j ≤ rear do
    	tempArr[k] := arr[j]
    	k := k+1
    	j := j+1
    end
    
    for l:=0 to rear-front do
    	arr[front+l] := tempArr[l]
}
分析
执行效率

归并排序的时间复杂度计算比较特别，可以用递推公式来分析一下。

假设对n个元素进行归并排序的时间是 T(n)，merge函数合并两个有序数组时间复杂度是O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
T(1)	=	C;					// n=1时，只需要常量级执行时间，表示为C。
T(n)	=	2*T(n/2) + n;
		= 	2* (2*T(n/4) + n/2) + n 				= 	4*T(n/4) + 2*n
		=	2* (2* (2*T(n/8) + n/4) + n/2) + n 		=	8*T(n/8) + 3*n
        = 	2* (2* (2* (2*T(n/16) + n/8) + n/4) + n/2) + n 	= 	16*T(n/16) + 4*n
        ...
        = 	2^k * T(n/2^k) + k*n
        ...
            
当
T(n/2^k) 	= 	T(1)
n/2^k = 1 	=> 	k = log2n
T(n) 		= 	Cn + nlog2n

而且，归并排序的执行效率与原始数组的有序程度无关，所以最好、最差、平均时间复杂度均为 O(nlogn)。

内存消耗

归并排序，在进行merge操作时候，会存在临时空间，最大不会超过n个数据大小。所以空间复杂度为 O(n)，它 不是原地排序 的算法。

稳定性

归并排序稳定性在合并数组时的处理，只要保证前半部分的先于后半部分的放入最终数组就可以让排序稳定。因此，归并排序 是稳定 的排序算法。

快速排序

概述

快速排序同归并排序一样，也是用的分治的思想。但是，又有些不同。它的思想是，取一个数为基准，将比它小的放在它左边，比它大的放在它右边；每部分再继续，直到区间缩小为1。

由此可见，归并排序是不断向上合并，是自下而上的；快速排序是不断下分，是自上而下的。

伪代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*arr 待排序数组；low低位索引；high高位索引*/
quick_sort(arr, low, high)
{
	if low ≥ high then return
	
    q = partition(arr, low, high);
    quick_sort(arr, low, q - 1);
    quick_sort(arr, q + 1, high);
}

/* 将数组分成两部分, arr待排序数组，low低位索引，high高位索引 */
partition(arr, low, high)
{
    standard := arr[high]
    i := low
    for j:=low to high-1 do
    	if arr[j] < standard then
    		swap arr[i] with arr[j]
    		i := i+1
    end
    swap arr[i] with arr[high]
    return i
}
分析
执行效率

快速排序的执行效率也可以通过递推公式来分析，如同归并排序一样

1
2
T(1) = C
T(n) = T(n/m) + T(n*(m-1)/m) + n

m的取值在于每次选的标准，即把数组分割的比例。

最好的情况，就是每次都将数组平分，即同归并排序的时间复杂度 O(nlogn)

最坏的情况，就是每次都是极端分割，时间复杂度退化到 O(n^2)

平均的情况，其实大部分的情况时间复杂度都可以达到 O(nlogn)；而且还有一些方法可以避免分割不均衡的发生。

内存消耗

快速排序内存消耗主要在partition函数中，使用交换的方式进行替代了开辟新空间，所以快速排序时间复杂度是 O(1)，是原地排序 的算法。

稳定性

上面分析内存消耗的时候讲到，快速排序用交换的方式实现原地排序，但正是因为这样，就无法保证数据的稳定性了（参考选择排序）。所以快速排序 不是稳定 的排序算法。

优化

快速排序是常用的排序算法之一，但是它的时间复杂度最坏情况能退化到O(n^2)，这个是我们不想看到的，下面介绍几种可以尽量避免分区不平衡的方法。

  1. 三数取中法：每次从区间的 头、中、尾 分别取出一个数，对比大小取中间值作为分区标准。当然，根据数据规模，可以扩展为n数取中。
  2. 随机法：每次从待排序区间，随机取一个元素作为分区标准，从概率学角度上讲相对于取固定位置值要好。

桶排序

概述

将待排序数组分到几个有序的桶中，每个桶的数据再排序，之后将每个桶的数据按照顺序依次取出即排序完成。

桶排序不是基于比较的比较排序，是一种线性排序。

桶排序比较适合用在外部排序中，外部排序就是数据存储在外部磁盘中，由于数据量比较大，内存有限，无法将数据全部加载到内存。

伪代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*arr 待排序数组，假定数组只有正数且范围在[0, 100), m为桶的数量*/
bucket_sort(arr, n)
{
	m := 10
	
    buckets := new array of m empty lists
    for i:=0 to n-1 do
    	insert arr[i] into buckets[arr[i]/10]
    end
    
    for i:=0 to m-1 do
    	sort(buckets[i])
    end
    
    
    return conncation of buckets[0], ..., buckets[m-1]
}
分析
执行效率

将n个数据平均分配到m个桶中，每个桶内有 k=n/m 个元素；

每个桶的内部用比较排序，时间复杂度就是 O(k logk)，m个桶排序的时间复杂度就是 O(m k logk)，也就是 O(m n/m log(n/m)) = O(n log(n/m)) ；

当桶的个数m接近n时，log(n/m)会很小，此时桶排序时间复杂度接近 O(n)。

最好的情况，当m接近n，时间复杂度接近 O(n)。

最差的情况，只有一个桶，时间复杂度即是内部排序时间复杂度 O(nlogn)

平均的情况，时间复杂度为 O(n * log(n/m))

内存消耗

桶排序需要的空间复杂度肯定不是O(1)了，最起码要分桶，而且如果想要达到O(n)的时间复杂度，桶的数量是不可少的。桶排序的空间复杂度为 O(n + m)，所以 不是原地排序 的算法。

稳定性

桶排序，先将数据分到桶内，这个是稳定的；再是桶内的排序，这个取决于采用的算法，也可以看做是稳定的；然后就是合并，这个步骤是稳定的。所以，桶排序 是稳定 的排序算法。

计数排序

概述

计数排序是桶排序的一种特殊情况。它通常对已知数量范围的数组进行排序，需要借助辅助数组C。

例如，

有一个大胃王比赛，总共有7个巨型包子，找10个人来参赛，成绩分别是 A[3, 1, 0, 2, 2, 5, 7, 1, 2, 0]。

因为，总共就7个包子，所以元素范围就是 [0, 7]，创建数组C[8]。

然后，遍历每个人吃的包子数量，填满数组C，比如第一个人吃了3个，C[0] += 1, C[1] += 1, C[2] += 1, C[3] += 1；数组内数字表示的是吃的包子数小于等于该下标的人数量，得到数组C[2, 4, 7, 8, 8, 9, 9, 10]。

最后，从后向前遍历原数组A，

根据原数组元素，在C数组找到在R数组的位置，并填入；比如元素0，在C数组0下标元素为2，表示小于等于0的元素有2个，它的位置为2，但是下标是从0开始，所以，位置修正为1。

遍历到头，得到最终数组R

1
2
3
4
5
6
7
8
9
10
11
12
13
14
原数组	  	 A[3, 1, 0, 2, 2, 5, 7, 1, 2, 0]

1: 		R[, 0, , , , , , , , ]					C[2-1, 4, 7, 8, 8, 9, 9, 10]
2: 		R[, 0, , , , , 2, , , ]					C[1, 4, 7-1, 8, 8, 9, 9, 10]
3: 		R[, 0, , 1, , , 2, , , ]				C[1, 4-1, 6, 8, 8, 9, 9, 10]
4: 		R[, 0, , 1, , , 2, , , 7]				C[1, 3, 6, 8, 8, 9, 9, 10-1]
5: 		R[, 0, , 1, , , 2, , 5, 7]				C[1, 3, 6, 8, 8, 9-1, 9, 9]
6: 		R[, 0, , 1, , 2, 2, , 5, 7]				C[1, 3, 6-1, 8, 8, 8, 9, 9]
7: 		R[, 0, , 1, 2, 2, 2, , 5, 7]			C[1, 3, 5-1, 8, 8, 8, 9, 9]
8: 		R[0, 0, , 1, 2, 2, 2, , 5, 7]			C[1-1, 3, 4, 8, 8, 8, 9, 9]
9: 		R[0, 0, 1, 1, 2, 2, 2, , 5, 7]			C[0, 3-1, 4, 8, 8, 8, 9, 9]
10: 	R[0, 0, 1, 1, 2, 2, 2, 3, 5, 7]			C[0, 2, 4, 8-1, 8, 8, 9, 9]

排序后数组 	R[0, 0, 1, 1, 2, 2, 2, 3, 5, 7]
伪代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*arr 待排序数组，假定数组只有正数且范围在[0, 100), k为C数组大小*/
count_sort(arr, n)
{
    for i:=0 to n-1 do
    	C[arr[i]] := C[arr[i]] + 1
    end
    for i:=0 to k-1 do
    	C[k] := C[k] + C[k-1]
    end
    for i:=n-1 to 0 do
    	C[arr[i]] := C[arr[i]]-1
    	R[C[arr[i]]] = arr[i]
    end
    
    return R
}
分析
执行效率

计数排序的时间复杂度，最好、最坏、平均是一样的，都需要遍历两边数组，假定C的大小为k，时间复杂度均为 O(n + k)。

内存消耗

很显然，计数排序需要额外的数组C，假定C的大小为k，空间复杂度为 O(n+k)，所以计数排序 不是原地排序 的算法。

稳定性

通过倒序遍历原数组构造最终数组，可以保证排序的稳定性。所以计数排序 是稳定 的排序算法。

基数排序

概述

基数排序，也像是桶排序的变种。

每次遍历只排序每个元素的某同位置的顺序，然后将所有元素按顺序取出，再次排序下一个位置。

可以从低位到高位依次排序，称为LSD法（Least Significant Digit first）；也可以从高位到低位排序，称为MSD法（Most Significant Digit first）。

基数排序，可以分为两个步骤：

  1. 根据某个位置分配元素到桶中
  2. 收集各个桶中元素

不断重复，直到没有位数了。

例如，有10个元素进行排序 [13, 55, 42, 30, 66, 89, 43, 79, 2, 81]，此处用LSD法排序。（LSD法适合位数小的排序，MSD法适合位数多的排序）

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
第一趟，根据个位数分配到各个桶中：
0 - 30
1 - 81
2 - 42, 2
3 - 13, 43
4 - 
5 - 55
6 - 66
7 - 
8 - 
9 - 89, 79
将各个桶中元素收集: 30, 81, 42, 2, 13, 43, 55, 66, 89, 79

第二趟，根据十位数分配到各个桶中：
0 - 2
1 - 13
2 - 
3 - 30
4 - 42, 43
5 - 55
6 - 66
7 - 79
8 - 81, 89
9 - 
将各个桶中元素收集: 2, 13, 30, 42, 43, 55, 66, 79, 81, 89

没有三位数情况，所以第二趟收集的元素，即为最终排序后的数组
伪代码
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
/*arr 待排序数组，n为数组长度，k为最大位数，m为桶个数*/
radix_sort(arr, n)
{
    for i:=1 to k do
		m := 10
		buckets := new array of m empty lists
    	
    	for j:=0 to n-1 do
    		if i ≤ 1 then
    			radix := arr[j]%pow(10, i)
    		else
    			radix := (arr[j]%pow(10, i))/pow(10, i-1)
    		end
    		insert arr[j] into buckets[radix]
    	end
    	
    	clear arr
    	for j:=0 to m-1 do
    		for k:=0 to len(buckets[j]-1) do
	    		insert buckets[j][k] into arr
	    	end
    	end
    end
    
    return arr
}
分析
执行效率

基数排序的时间复杂度跟数组内最大位数 k 相关，也跟桶的数量 m 相关，时间复杂度为 O(n*(k + m))。

内存消耗

基数排序需要额外的桶来不断分配，所以它的空间复杂度为 O(n + m)，基数排序 不是原地排序 的算法。

稳定性

基数排序在排序过程中是用分配的方式进行，有固定的顺序，所以不会打乱原先数组元素顺序。因此，基数排序 是稳定 的排序算法。


总结

排序算法 时间复杂度 是否稳定 是否原地
冒泡排序 O(n^2) 是 是
插入排序 O(n^2) 是 是
选择排序 O(n^2) 不是 是
快速排序 O(nlogn) 不是 是
归并排序 O(nlogn) 是 不是
桶排序 O(n) 是 不是
计数排序 O(n) 是 不是
基数排序 O(n) 是 不是



二分查找

定义

二分查找是对一个有序数组的集合，利用分治思想进行查找。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一般，直到找到查找的元素，或区间缩小为0即未找到。

时间复杂度

二分查找非常的高效，每次查找都会将查找区间缩小一半，即 n, n/2, n/4, n/8, n/16 … n/2^k ，时间复杂度为 O(logn) 。

实现

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*arr 待排序数组，n为数组长度，aim为要查找的数值*/
binary_search(arr, n, aim)
{
    low := 0
    high := n-1
    
    while low ≤ high do
    	mid := (low + high)/2
    	if arr[mid] < aim then
    		low = mid + 1
    	else if arr[mid] > aim then
    		high = mid - 1
    	else
    		return mid
    	end
    end
    
    return -1
}

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*arr 待排序数组，n为数组长度，aim为要查找的数值*/
binary_search(arr, n, aim)
{
    return block_binary_search(arr, 0, n-1, aim)
}

recursive_binary_search(arr, low, high, aim)
{
    if low > high then
    	return -1
    	
    mid := low + (high - low)/2
    if arr[mid] < aim then
    	return recursive_binary_search(arr, mid + 1, high, aim)
    else if arr[mid] > aim then
    	return recursive_binary_search(arr, low, mid - 1, aim)
    else
    	return mid
    end
}

局限

前面说了二分查找这么厉害，它是不是就是查找算法的万能钥匙呢？显然不是。它有以下四个局限性

  • 依赖顺序表结构，即数组。 因为它利用了根据下标随机访问，如果用链表，复杂度将提高很多。
  • 针对有序数据。 每次都用中间的元素来判断，下一个区间是哪一个。
  • 不适合小数据量查找。 如果比较操作非常耗时，那么还是推荐用二分查找，减少比较次数。
  • 不适合太大数据量查找。 因为二分查找依赖顺序表结构，会将占用连续一整块内存，如果数据量过大，会对存储造成大的麻烦。



练习

排序

必知必会

实现各种排序算法

  • 归并排序
  • 快速排序
  • 插入排序
  • 冒泡排序
  • 选择排序

实现O(n)时间复杂度找到数据中第K大的元素

LeetCode



二分查找

必知必会

实现有序数组二分查找

实现模糊二分查找（大于等于给定值的第一个元素）

LeetCode