最近因为业务需要，开始学习Python，作为C/C++程序员，一开始写Python总是忍不住在每行后面加个‘;’。当然除了语法，还是要把基本的数据结构和算法都简单的复习一遍的，下面开始从几类常见的排序开始实现，虽然python自带的sorted方法很好用，但是可以用自己的方法与它做一下比较。以下的代码均在Python 3.6环境下验证通过，排序对象为整形列表，按照由小到大的方式排序。
冒泡排序的原理非常简单，就是个双层循环的过程，列表元素像水里的一串气泡，第一趟冒泡从第一个气泡开始，与它相邻的气泡做比较，大的气泡交换到上面去，这个冒泡的过程就是内循环，需要n-1次。每经过一趟冒泡的过程，可以使一个最大的元素冒出来，需要排序的元素数目就会减1，如果列表里面有n个元素，则冒n-1次就可以完成全部过程，这就是外循环。
基于这种原理，用Python3的方法实现如下：
1
2
3
4
5
6
7
8
9
10
| def bubble_sort1(lists):
"""冒泡排序"""
if list_check(lists) is False:
return lists
for i in range(len(lists) - 1):
for j in range(len(lists) - i - 1):
if lists[j] > lists[j + 1]:
lists[j], lists[j + 1] = lists[j + 1], lists[j]
return lists
|
可以看出这个二层循环的过程，在最坏的情况下，时间复杂度为O(n²)，但是换一种思路，如果有一趟冒泡并没有发生交换，我们就可以确定此时列表已经是有序的了，不需要再去执行下一趟的冒泡过程。于是可以设置一个flag用来记录交换是否发生，则可以将算法优化如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| def bubble_sort2(lists):
"""冒泡排序添加flag版"""
if list_check(lists) is False:
return lists
for i in range(len(lists) - 1):
flag = True
for j in range(len(lists) - i - 1):
if lists[j] > lists[j + 1]:
lists[j], lists[j + 1] = lists[j + 1], lists[j]
flag = False
if flag:
return lists
return lists
|
为了比较这两种算法，以及与Python自带的sorted方法的效率，下面用一个装饰器来计算函数执行时间。代码如下：
1
2
3
4
5
6
7
8
9
10
| def time_usage(func):
"""时间计算函数"""
def wrapper(*args, **kwargs):
"""用装饰器和timeit提高计算精度"""
start_time = timeit.default_timer()
ret = func(*args, **kwargs)
use_time = timeit.default_timer() - start_time
print('{} elapsed time: {} seconds!'.format(func.__name__, use_time))
return ret
return wrapper
|
然后从0~20000之间取10000个随机整数组成列表进行排序并统计时间，完整代码如下：
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
|
"""常见排序算法的Python实现"""
import timeit
import numpy.random as nprnd
RAND_LIST = nprnd.randint(20000, size=10000).tolist()
def list_check(lists):
"""list类型入参检查函数"""
if not isinstance(lists, list):
print('Only support list!')
return False
if not lists:
print('The list is empty!')
return False
def time_usage(func):
"""时间计算函数"""
def wrapper(*args, **kwargs):
"""用装饰器和timeit提高计算精度"""
start_time = timeit.default_timer()
ret = func(*args, **kwargs)
use_time = timeit.default_timer() - start_time
print('{} elapsed time: {} seconds!'.format(func.__name__, use_time))
return ret
return wrapper
@time_usage
def bubble_sort1(lists):
"""冒泡排序"""
if list_check(lists) is False:
return lists
for i in range(len(lists) - 1):
for j in range(len(lists) - i - 1):
if lists[j] > lists[j + 1]:
lists[j], lists[j + 1] = lists[j + 1], lists[j]
return lists
@time_usage
def bubble_sort2(lists):
"""冒泡排序添加flag版"""
if list_check(lists) is False:
return lists
for i in range(len(lists) - 1):
flag = True
for j in range(len(lists) - i - 1):
if lists[j] > lists[j + 1]:
lists[j], lists[j + 1] = lists[j + 1], lists[j]
flag = False
if flag:
return lists
return lists
if __name__ == '__main__':
time_usage(sorted)(RAND_LIST)
SORT_LIST = copy.deepcopy(RAND_LIST)
bubble_sort1(SORT_LIST)
SORT_LIST = copy.deepcopy(RAND_LIST)
bubble_sort2(SORT_LIST)
|
执行一下比较它们的效率：
可以看出事与愿违，第二种反而比第一种慢了一点点，多次排序比较后依然如此，作为对比我又用C++去实现了一遍，结果是一样的，如下图所示，第二种比第一种慢一点点：
其原因可能是因为flag只有在大部分数都排序好的情况下才用得上，对于这种大规模随机数，每次循环的过程中都要对flag的赋值与判断，占用的时间累积起来却是得不偿失。
但是不管是哪种冒泡排序，同内置的sorted函数的0.003s执行时间相比，效率仍然低了几个数量级。
冒泡排序的实现简单，适合教科书中详解循环的用法，但是它效率低下，在数据规模很小的场景下使用比较方便，对于大规模数据的处理，还是需要考虑使用别的排序方法。