Introduction

最近需要对24102个数据进行排序,第一次遇到这么多的数据,以前排序都是直接调用系统的包,或者直接来写一个冒泡,这次正好有机会,可以测试一下各个排序算法的性能。这里测试的算法有:冒泡排序,快速排序。

语言 :python
数据 :24102个整型数字 sortData

Keywords
冒泡排序 交换,优化
快速排序 最快,分治递归,栈溢出,两个哨兵,pivot,>=,<=,右哨兵先动
堆排序 结构性:完全二叉树,堆序性,建堆调整所有父节点

准备工作

1
2
3
4
5
6
7
8
9
10
11
12
13
'''
获取数据
'''
def get_data():

fr = open('sortData.txt','r',encoding = 'utf_8_sig')
source = fr.read()
listt = source.split(' ')# 数字之间按照空格进行存储
num_list = []
for num in listt:
num_list.append(int(num))

return num_list

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def bubble_sort(listt):
i = len(listt) - 1
while i > 0:
j = 0
flag = True
while j < i:
if listt[j] > listt[j+1]:
flag = False
# swtich
listt[j],listt[j+1] = listt[j+1],listt[j]
j = j + 1
if flag == True:# 如果在遍历一次后,发现不需要交换,说明数组已经有序
break
i = i - 1

快速排序

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
# 升序排序,降序排序只需要将while循环中>= <= 改成 <=  >=即可
def quick_sort(listt,start,end):

if start >= end: # 只剩一个元素,返回
return

pivot = listt[start] # 将数组第一个值当作pivot
flag1 = start
flag2 = end

while flag1 < flag2:
# 哨兵2先出发
while listt[flag2] >= pivot and flag1 < flag2:
flag2 = flag2 - 1
while listt[flag1] <= pivot and flag1 < flag2:
flag1 = flag1 + 1

if flag1 < flag2: # switch
listt[flag1], listt[flag2] = listt[flag2],listt[flag1]

# 此时flag1 == flag2
# flag2 指向的位置就是pivot应该在的地方,将数组分成两半
listt[start], listt[flag1] = listt[flag1], listt[start]

quick_sort(listt,start,flag1-1)
quick_sort(listt,flag1+1,end)

confirm

1
2
3
4
5
6
7
8
9
10
11
12
# 验证是否有序
def confirm(listt):
flag = True

for i in range(len(listt)):
if listt[0] >= listt[1]: #降序排序
if i != len(listt) - 1 and listt[i] < listt[i+1]:
flag = False
else: # 升序排序
if i != len(listt) - 1 and listt[i] > listt[i+1]:
flag = False
print(flag)

实验结果

通过实验我们发现,传统的 bubblesort 排序算法,面对大量的数据(24102条数据)时非常的低效的,在我这台CPU 2.6GHZ的电脑上,需要跑两分钟才能算完,而且即使加入了优化处理(flag),在面对完全无序的数组时,依然时没有什么效果的,还是两分钟左右跑完。但是 quick_sort 只需要不到1秒中的时间,就搞定了。。。

冒泡排序 冒泡排序(优化) 快速排序
时间 120s 120s 82ms

这让我想到了算法时间复杂度的定义:时间复杂度并不是表示一个程序解决问题需要花多少时间,而是当问题规模扩大后,程序需要的时间长度增长得有多快。

冒泡排序的时间复杂度时 O(N2),而快速排序的时间复杂度为 NlogN,两者的比值为:N/logN, 24102/log24102 = 1656, 而最后运行的时间作比值: 120000/82 = 1463,我们可以看到 1656约等于1463,也就是说给定数据量N,快速排序的速度是冒泡排序的N/logN倍,所以:当我们的数据量很小时,两者的排序时间差距不是很明显,但是当数据量越来越大,快速排序的优势就越来越明显

实现细节

快速排序的思想看似简单,但是实现起来,确是有很多陷阱。陷阱主要有二:
1、两个哨兵谁先动?
2、两个哨兵与pivot比较的时候到底要不要加 = 号?


首先来看第二个问题,我们以升序排序来举一个例子。我们默认第一个元素为pivot,第一个哨兵与pivot比较的时候,如果设置了 listt[flag1] < pivot,那么第一个哨兵初始值指向的就是pivot,此时listt[flag1] == pivot,所以条件不成立,这意味着pivot一开始就要与哨兵2指向的某个值交换掉,这显然是错误的,所以我们应该设置成 listt[flag1] <= pivot。再看一下第二个哨兵,第二个哨兵负责找比pivot小的数与第一个哨兵交换,如果我们将循环条件设置成 listt[flag2] > pivot 就继续循环,那么即使遇到了与pivot相同的数暂停了循环,也没有问题,同样可以交换到pivot前面,所以哨兵而可以不用加 = 号

综上,我们在写循环条件的时候,都加上 = 号即可。

0 1 2 3 4 5 6 7 8
原数组 6 1 6 7 9 6 5 10 8
哨兵1 listt[flag1] < pivot 5 1 6 7 9 6 6 10 8 pivot第一次交换就被换掉,错误!

快速排序(升序)在实现的时候,最容易出错的地方在于两个哨兵谁先动,实际上应该是后面的那个哨兵先动。


我们再来看看第一个问题,两个哨兵谁先动?我们还是以升序排序举例:

假设让哨兵1先动,第一个哨兵的职责是找比pivot大的数与pivot交换,他有两种停下来的可能:

  1. 遇到了比pivot大的数,然后等待哨兵2找到比pivot小的数交换
  2. 遇到了哨兵2,停止

问题就出现在了第一种可能,当哨兵2遇到了比pivot大的数停下来后,哨兵2不一定能找到比pivot小的数,这样直到哨兵2与哨兵1相遇,此时两者指向的都是比pivot大的数,而按照程序的规则,这个数是要与pivot作交换的、比pivot小的数,也就是说,我们最终要找到的与pivot交换的数,必须是比pivot小的数,而哨兵1找的是比pivot大的数,如果最后两者都落在了哨兵1指向的数,那相当于我们将一个比pivot大的数放在了pivot之前,这肯定是错误的。所以必须让哨兵2先动

哨兵2停下来也有两种可能:

  1. 遇到了比pivot小的数,然后等待哨兵1找到比pivot大的数交换
  2. 遇到了哨兵1

第一中情况,就算哨兵1没有找到比pivot大的数,与哨兵2汇合,那么两者指向的数还是比pivot小的数
第二种情况,就算pivot2在遍历中遇到了哨兵1,但是哨兵1指向的数是之前已经与哨兵2交换过的仍然是比pivot小的数。

所以,应该让哨兵2先动。同理,逆序也是哨兵2先动。

吃饭的时候,我又想了一下为什么哨兵2先动。现在概括一下:
我们最终想要找到的与pivot交换的数是比pivot小的数,而哨兵1负责找比pivot大的数,所以哨兵2先动

另外,有一点需要注意,快速排序虽然在乱序的时候是最快的,但是其用到了递归(分治 二叉树的思想),如果序列是比较有序的,而且排序数量比较多,那么可能导致栈溢出