[Python] 常见的排序与搜索算法

56 阅读 0 评论 37 点赞

我是靠谱客的博主凶狠手机，最近开发中收集的这篇文章主要介绍[Python] 常见的排序与搜索算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

说明：

　　本文主要使用python实现常见的排序与搜索算法：冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序以及二分查找等。

　　对算法的基本思想作简要说明，只要理解了基本的思想，与实现语言无关。

　　本文主要参考网络文章，仅供学习。

　　开发环境：Python3.5

一、冒泡排序

　　冒泡排序（Bubble Sort）算是一种比较常见的排序算法，重复遍历要排序的数列，一次比较相邻的两个元素，如果顺序错误即互相交换位置，遍历直到无需再交换，则此时数列已经排序完成。此算法名字由来：因为越小的元素（升序）经由交换慢慢 “浮”到数列的顶端。

　　1、冒泡排序的基本思想（运作原理）：

　　　 · 比较相邻的元素，如果第一个比第二个大（升序），就交换它们两个。

　　　　· 对每一对相邻的元素作同样的工作，从开始第一对到结尾最后一对，这一步做完后，最后的元素会是最大的数。

　　　　· 针对所有的元素重复以上的步骤，除了最后一个（倒数第二个与其已作比较）。

　　　　· 持续每次对越来越少的元素重复上面的步骤，知道没有任何一对数字需要比较。

　　　　交换过程示意图（第一次）（来自网络）：

　　2、python实现过程：

　　　　这里提供两种实现过程，第二个实现过程为上面示意图所示。　　

 1 # coding=utf-8
 2
 3
 4 def bubble_sort(ls):
 5
"""冒泡排序"""
 6
print("before: ", ls)
 7
for i in range(0, len(ls) - 1):
 8
# i = [0, 1, ...., len(ls) - 2]，每次比较的第一个数的下标
 9
# j = [i + 1, i + 2, ..., len(ls) - 1]，每次比较的第二个数的下标
10
for j in range(i + 1, len(ls)):
11
if ls[i] > ls[j]:
12
ls[i], ls[j] = ls[j], ls[i]
13
print(ls)
14
print("after: ", ls)
15
16
17 def bubble_sort2(ls):
18
"""冒泡排序"""
19
print("before：", ls)
20
for j in range(len(ls) - 1, 0, -1):
21
# j = [len(ls) - 1, len(ls) - 2, ..., 1], 每次需要比较的次数
22
# i = [0, 1, 2, ..., j - 1]，需要比较的下标
23
for i in range(j):
24
if ls[i] > ls[i + 1]:
25
ls[i], ls[i + 1] = ls[i + 1], ls[i]
26
print(ls)
27
print("after：", ls)
28
29
30 if __name__ == "__main__":
31
ls1 = [54, 26, 93, 17, 77, 31, 44, 55, 20]
32
ls2 = [54, 26, 93, 17, 77, 31, 44, 55, 20]
33
34 
bubble_sort(ls1)
35
print("-"*50)
36
bubble_sort2(ls2)

　　　　执行结果（分割线上为 bubble_sort1() 的执行结果，分割线下为 bubble_sort2() 的执行结果）：

　　3、时间复杂度：

　　　　最优时间复杂度：O(n)（表示遍历一次发现没有任何可以交换的元素排序结束，在内循环可以做一个标识判断，如果首次循环没有任何交换，则跳出）

　　　　最坏复杂度：O(n²)

　　　　稳定性：稳定

二、选择排序

　　选择排序（ Selection Sort ）是一种简单直观的排序算法，基本原理：首先在未排序中找到最小（大）的元素，存放在排序序列的起始位置，然后在从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序的末尾，一次类推，直到所有元素均排序完毕。

　　选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个呗移到其最终位置上，因此对 n 个元素的表进行排序共进行至多 n - 1次交换。在所有完成依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

　　1、排序过程，图示（图来源网络）：

　　　　假设右边为已排序，然后从左边未排序中选择一个最大值，放到右边来。

　　2、python实现过程：

　　　　这里代码的思想为：假设左边为已排序，右边为排序。　　　

 1 # coding=utf-8
 2
 3
 4 def selection_sort(ls):
 5
"""选择排序"""
 6
# 假设左边为已排序，右边为未排序
 7
 8
print("before：", ls)
 9
for i in range(0, len(ls) - 1):
10
# i = [0, 1, 2,,, len(ls) - 2]
11
# j = [i + 1, i + 2,,, len(ls) - 1]
12
min_index = i
13
for j in range(i + 1, len(ls)):
14
if ls[j] < ls[min_index]:
15
min_index = j
16
17
if min_index != i:
18
ls[min_index], ls[i] = ls[i], ls[min_index]
19
print(ls)
20
print("after：", ls)
21
22
23 if __name__ == "__main__":
24
ls = [54, 26, 93, 17, 77, 31, 44, 55, 20]
25
26
selection_sort(ls)

　　3、时间复杂度：

　　　　最优时间复杂度：O(n²)

　　　　最坏时间复杂度：O(n²)

　　　　稳定性：不稳定（考虑升序每次选择最大的情况）

三、插入排序

　　插入排序（Insert ion Sort），其工作原理：通过构建有序序列，对于未排序数据中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后面向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

　　1、排序过程，图示意（图片来自网络）：

　　2、python实现过程：

　　　　从小标为 1 开始，往 0 遍历，比较交换。

 1 # coding=utf-8
 2
 3
 4 def insert_sort(ls):
 5
"""插入排序"""
 6
# 假设左边已排序，右边为未排序，每次从右边取一个数，遍历已排序的子序列，直到找到次数的位置。
 7
print("before: ", ls)
 8
for j in range(1, len(ls)):
 9
for i in range(j, 0, - 1):
10
if ls[i] < ls[i - 1]:
11
ls[i], ls[i - 1] = ls[i - 1], ls[i]
12
print(ls)
13
print("after: ", ls)
14
15
16 if __name__ == "__main__":
17
ls = [54, 26, 93, 17, 77, 31, 44, 55, 20]
18
19
insert_sort(ls)

　　　　执行结果：

　　3、时间复杂度：

　　　　最优时间复杂度：O(n)（升序序列，序列已经处于升序状态）

　　　　最坏时间复杂度：O(n²)

　　　　稳定性：稳定

四、希尔排序

　　希尔排序（Shell Sort）是插入排序的一种。也称为增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是把纪录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个序列恰被分成一组，算法便终止。

　　1、希尔排序过程：

　　　　基本思想：将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表识为了更好理解这算法，算法本身还是使用数组进行排序。

　　　　例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中进行更好的描述算法，这样它们就应该看起来是这样（竖着的元素是步长组成）：

　　　　最后以 1 步长进行排序（此时就是简单的插入排序）

　　2、python实现过程：

　　　　实现过程基本和插入排序类似，只是插入排序的 step 固定为 1，而希尔排序的 step 会变化直至为 1。

 1 # coding=utf-8
 2
 3
 4 def shell_sort(ls):
 5
"""希尔排序"""
 6
print("before: ", ls)
 7
 8
step = len(ls) // 2
# 初始步长
 9
10
while step > 0:
11
# 插入排序
12
for j in range(step, len(ls)):
13
for i in range(j, 0, - step):
14
if ls[i] < ls[i - step]:
15
ls[i], ls[i - step] = ls[i - step], ls[i]
16
step //= 2
17
print(ls)
18
print("shell_sort ：", ls)
19
20
21 if __name__ == "__main__":
22
ls = [54, 26, 93, 17, 77, 31, 44, 55, 20]
23
24
shell_sort(ls)

　　　　执行结果：

　　3、时间复杂度：

　　　　最优时间复杂度：根据步长序列的不同而不同。

　　　　最坏时间复杂度：O(n²)。

　　　　稳定性：不稳定。

五、快速排序

　　快速排序（Quick Sort），又称为划分交换排序（Partition-exchange Sort），通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要笑，然后在按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

　　1、快速排序过程：

　　　　① 从数列中选出一个元素，称为“基准”（pivot）。

　　　　② 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准大的摆在基准的后面（相同的数，可以放到任意一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

　　　　③ 递归（recursive）把小于基准值元素子数列和大于基准值元素的子数列排序。

　　　　递归的的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。

　　2、python实现过程：

　　　　这里提供两种快速排序的方式，基本思想一样，第一种是在原有列表进行操作（通过游标进行），第二种则是新建左右子列表进行存储。

 1 # coding=utf-8
 2
 3
 4 def quick_sort1(ls, start, end):
 5
"""
 6 
快速排序-1
 7 
low 和 high 分别指向序列的头和尾
 8 
low += 1， high -= 1
 9 
在low自增过程中，直到找到大于 mid_val 的下标
10 
在high自增减过程中，直到找到小于 mid_val 的小标
11 
然后将这两个值交换
12
"""
13
14
# 递归退出条件
15
if start >= end:
16
return
17
18
low = start
19
high = end
20
mid_val = ls[low]
21
22
while low < high:
23
while low < high and ls[high] > mid_val:
24
high -= 1
25
ls[low] = ls[high]
26
27
while low < high and ls[low] < mid_val:
28
low += 1
29
ls[high] = ls[low]
30
31
ls[low] = mid_val
32
33
print("mid:", mid_val, ls)
34
35
quick_sort1(ls, start, low - 1)
# 左边的子序列
36
quick_sort1(ls, low + 1, end)
# 右边的子序列
37
38
return ls
39
40
41 def quick_sort2(ls):
42
"""快速排序-2"""
43
44
# 递归退出条件
45
if len(ls) <= 1:
46
return ls
47
48
left_ls, right_ls = [],[]
49
mid_val = ls[0]
50
for i in range(1, len(ls)):
51
if ls[i] < mid_val:
52 
left_ls.append(ls[i])
53
else:
54 
right_ls.append(ls[i])
55
56
print(left_ls, mid_val, right_ls)
57
58
# 递归调用，左右子列表
59
left_res = quick_sort2(left_ls)
60
right_res = quick_sort2(right_ls)
61
62
return left_res + [mid_val] + right_res
63
64
65
66 if __name__ == "__main__":
67
ls1 = [54, 26, 93, 17, 77, 31, 44, 55, 20]
68
ls2 = [54, 26, 93, 17, 77, 31, 44, 55, 20]
69
70
print("before：", ls1)
71
res1 = quick_sort1(ls1, 0, len(ls1) - 1)
72
print("quick sort1: ", res1)
73
74
print("-"*50)
75
print("before: ", ls2)
76
res2 = quick_sort2(ls2)
77
print("quick sort2：", res2)

　　　　执行结果：

　　3、时间复杂度：

　　　　最优时间复杂度：O(nlogn)

　　　　最坏时间复杂度：O(n²)

　　　　稳定性：不稳定

六、归并排序

　　归并排序是采用分治法的一种非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。

　　将数组分解最小之后，然后合并两个有序数组，基本思路：比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直到一个数组为空，最后把另外一个数组的剩余部分复制过来即可。

　　1、归并排序过程，图示：

　　2、python实现过程：

　　　　先把序列拆分成 left_ls 和 right_ls ，然后再合并成一个res。

 1 # coding=utf-8
 2
 3
 4 def merge_sort(ls):
 5
"""归并排序"""
 6
n = len(ls)
 7
 8
# 递归退出条件
 9
if n <= 1:
10
return ls
11
12
mid = n // 2
13
14
# 1、拆分子序列
15
left_ls = merge_sort(ls[:mid])
16
right_ls = merge_sort(ls[mid:])
17
18
# 2、合并子序列：left_ls 和 right_ls
19
left_point, right_point = 0, 0
20
res = []
21
22
# 当left_ls或者right_ls 结束，就会退出 while，而另外一个则可能未结束，所有后面需要 res +=
23
while left_point < len(left_ls) and right_point < len(right_ls):
24
# 比较两个子序列，小的先加入到 res[]
25
if left_ls[left_point] < right_ls[right_point]:
26 
res.append(left_ls[left_point])
27
left_point += 1
28
else:
29 
res.append(right_ls[right_point])
30
right_point += 1
31
print("res:", res)
32
33
res += left_ls[left_point:]
34
res += right_ls[right_point:]
35
36
return res
37
38
39 if __name__ == "__main__":
40
ls = [54, 26, 93, 17, 77, 31, 44, 55, 20]
41
42
print("before: ", ls)
43
res = merge_sort(ls)
44
print("merge sort: ", res)

　　　　执行结果：

　　3、时间复杂度：

　　　　最优时间复杂度：O(nlogn)

　　　　最坏时间复杂度：O(nlogn)

　　　　稳定性：稳定

七、二分查找

　　二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好，其缺点是要求待查找表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

　　基本思想：假设表中元素是按升序排序，将表中间位置记录关键字与查找关键字比较，如果两者相等，则查找成功，否则利用中间位置记录分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一个子表。重复以上过程，知道找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

　　1、二分查找过程，图示（图片来源网络）：

　　2、python实现过程：

　　　　这里主要两种实现方式，一种递归，另一种非递归。

 1 # coding=utf-8
 2
 3
 4 def binary_search_recursion(ls, item):
 5
"""二分查找---递归"""
 6
n = len(ls)
 7
if n < 1:
 8
return False
 9
10
mid = n // 2
11
12
# 与中间值比较
13
if item == ls[mid]:
14
return True
15
16
# 去左边子序列查找
17
elif item < ls[mid]:
18
return binary_search_recursion(ls[:mid], item)
19
20
# 去右边子序列查找
21
else:
22
return binary_search_recursion(ls[mid + 1:], item)
23
24
25 def binary_search(ls, item):
26
"""二分查找---非递归"""
27
n = len(ls)
28
start = 0
29
end = n - 1
30
31
while start <= end:
32
mid = (start + end) // 2
33
34
if item == ls[mid]:
35
return True
36
elif item < ls[mid]:
37
end = mid - 1
38
else:
39
start = mid + 1
40
return False
41
42
43 if __name__ == "__main__":
44
ls = [17, 20, 26, 31, 44, 54, 55, 77, 93]
45
46
num = int(input("请输入一个整数:"))
47
res = binary_search(ls, num)
48
print("查找结果：", res)

八、完整代码


1 # coding=utf-8

2

3

4 def bubble_sort(ls):

5
"""冒泡排序"""

6
print("before: ", ls)

7
for i in range(0, len(ls) - 1):

8
# i = [0, 1, ...., len(ls) - 2]，每次比较的第一个数的下标

9
# j = [i + 1, i + 2, ..., len(ls) - 1]，每次比较的第二个数的下标
 10
for j in range(i + 1, len(ls)):
 11
if ls[i] > ls[j]:
 12
ls[i], ls[j] = ls[j], ls[i]
 13
print(ls)
 14
print("after: ", ls)
 15
 16
 17 def bubble_sort2(ls):
 18
"""冒泡排序"""
 19
print("before：", ls)
 20
for j in range(len(ls) - 1, 0, -1):
 21
# j = [len(ls) - 1, len(ls) - 2, ..., 1], 每次需要比较的次数
 22
# i = [0, 1, 2, ..., j - 1]，需要比较的下标
 23
for i in range(j):
 24
if ls[i] > ls[i + 1]:
 25
ls[i], ls[i + 1] = ls[i + 1], ls[i]
 26
print(ls)
 27
print("after：", ls)
 28
 29
 30 def selection_sort(ls):
 31
"""选择排序"""
 32
# 假设左边为已排序，右边为未排序
 33
 34
print("before：", ls)
 35
for i in range(0, len(ls) - 1):
 36
# i = [0, 1, 2,,, len(ls) - 2]
 37
# j = [i + 1, i + 2,,, len(ls) - 1]
 38
min_index = i
 39
for j in range(i + 1, len(ls)):
 40
if ls[j] < ls[min_index]:
 41
min_index = j
 42
 43
if min_index != i:
 44
ls[min_index], ls[i] = ls[i], ls[min_index]
 45
print(ls)
 46
print("after：", ls)
 47
 48
 49 def insert_sort(ls):
 50
"""插入排序"""
 51
# 假设左边已排序，右边为未排序，每次从右边取一个数，遍历已排序的子序列，直到找到次数的位置。
 52
print("before: ", ls)
 53
for j in range(1, len(ls)):
 54
for i in range(j, 0, - 1):
 55
if ls[i] < ls[i - 1]:
 56
ls[i], ls[i - 1] = ls[i - 1], ls[i]
 57
print(ls)
 58
print("after: ", ls)
 59
 60
 61 def shell_sort(ls):
 62
"""希尔排序"""
 63
print("before: ", ls)
 64
 65
step = len(ls) // 2
# 初始步长
 66
 67
while step > 0:
 68
# 插入排序
 69
for j in range(step, len(ls)):
 70
for i in range(j, 0, - step):
 71
if ls[i] < ls[i - step]:
 72
ls[i], ls[i - step] = ls[i - step], ls[i]
 73
step //= 2
 74
print(ls)
 75
print("shell_sort ：", ls)
 76
 77
 78 def quick_sort1(ls, start, end):
 79
"""
 80 
快速排序-1
 81 
low 和 high 分别指向序列的头和尾
 82 
low += 1， high -= 1
 83 
在low自增过程中，直到找到大于 mid_val 的下标
 84 
在high自增减过程中，直到找到小于 mid_val 的小标
 85 
然后将这两个值交换
 86
"""
 87
 88
# 递归退出条件
 89
if start >= end:
 90
return
 91
 92
low = start
 93
high = end
 94
mid_val = ls[low]
 95
 96
while low < high:
 97
while low < high and ls[high] > mid_val:
 98
high -= 1
 99
ls[low] = ls[high]
100
101
while low < high and ls[low] < mid_val:
102
low += 1
103
ls[high] = ls[low]
104
105
ls[low] = mid_val
106
107
print("mid:", mid_val, ls)
108
109
quick_sort1(ls, start, low - 1)
# 左边的子序列
110
quick_sort1(ls, low + 1, end)
# 右边的子序列
111
112
return ls
113
114
115 def quick_sort2(ls):
116
"""快速排序-2"""
117
118
# 递归退出条件
119
if len(ls) <= 1:
120
return ls
121
122
left_ls, right_ls = [],[]
123
mid_val = ls[0]
124
for i in range(1, len(ls)):
125
if ls[i] < mid_val:
126 
left_ls.append(ls[i])
127
else:
128 
right_ls.append(ls[i])
129
130
print(left_ls, mid_val, right_ls)
131
132
# 递归调用，左右子列表
133
left_res = quick_sort2(left_ls)
134
right_res = quick_sort2(right_ls)
135
136
return left_res + [mid_val] + right_res
137
138
139 def merge_sort(ls):
140
"""归并排序"""
141
n = len(ls)
142
143
# 递归退出条件
144
if n <= 1:
145
return ls
146
147
mid = n // 2
148
149
# 1、拆分子序列
150
left_ls = merge_sort(ls[:mid])
151
right_ls = merge_sort(ls[mid:])
152
153
# 2、合并子序列：left_ls 和 right_ls
154
left_point, right_point = 0, 0
155
res = []
156
157
# 当left_ls或者right_ls 结束，就会退出 while，而另外一个则可能未结束，所有后面需要 res +=
158
while left_point < len(left_ls) and right_point < len(right_ls):
159
# 比较两个子序列，小的先加入到 res[]
160
if left_ls[left_point] < right_ls[right_point]:
161 
res.append(left_ls[left_point])
162
left_point += 1
163
else:
164 
res.append(right_ls[right_point])
165
right_point += 1
166
print("res:", res)
167
168
res += left_ls[left_point:]
169
res += right_ls[right_point:]
170
171
return res
172
173
174 def binary_search_recursion(ls, item):
175
"""二分查找---递归"""
176
n = len(ls)
177
if n < 1:
178
return False
179
180
mid = n // 2
181
182
# 与中间值比较
183
if item == ls[mid]:
184
return True
185
186
# 去左边子序列查找
187
elif item < ls[mid]:
188
return binary_search_recursion(ls[:mid], item)
189
190
# 去右边子序列查找
191
else:
192
return binary_search_recursion(ls[mid + 1:], item)
193
194
195 def binary_search(ls, item):
196
"""二分查找---非递归"""
197
n = len(ls)
198
start = 0
199
end = n - 1
200
201
while start <= end:
202
mid = (start + end) // 2
203
204
if item == ls[mid]:
205
return True
206
elif item < ls[mid]:
207
end = mid - 1
208
else:
209
start = mid + 1
210
return False