算法：排序

Coding

在看《啊哈！算法》这本书，打算做一份读书笔记。

第一章是排序，讲述了桶排序，冒泡排序和快速排序三种方法。

桶排序

刚开始觉得方便，便用python复刻了下原书中C的代码 不会C语言

这个方法的原理就好比给一列数字排序时，这列数字中最大值(n)有多大，就设置(n+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
flag = True
number_list = [] #输入的数字列表
book = [] #桶

#让用户输入数字，将数字添加到列表中，如果用户输入“done”，就结束输入
while flag:
    number = input("give me number to input:\n")
    if number == 'done':
        flag = False
        break
    number_list.append(int(number))
    flag = True

#桶的数量，加上1是因为要包含0
length = int(max(number_list)) + 1

#将这些桶的旗帜数量统统设为0
for i in range(length):
    book.append(i)
    book[i] = 0

#将数字列表中的数作为旗帜插入对应的桶里
for i in number_list:
    book[int(i)] += 1

#从大到小将桶遍历，range(a,b,-1) a是遍历的起点(包含),b是终点(不包含)
for i in range(len(book)-1, -1, -1):
    #如果旗帜数量大于等于1
    if book[i] >= 1:
        #有几个旗帜就打印几次
        for j in range(0, int(book[i])):
            print(i)

如果输入为 (为了省空间用空格代替回车键)

10 320 44 44 32 10 done

那么输出为

320 44 44 32 10 10
时间复杂度上，一共进行了O(M+M+N+M+N)次，也就是忽略掉coefficient 2和3，一共是O(M+N)次。这是一个非常快的排序算法，但缺点也是很明显的：如果我们只需要对比5个4位数的数字（如1000,2000,4444,3333,9999），我们依然要建立10000个桶，非常浪费空间！另外如果我们需要排序小数，如1.12,2.333,2.33343时，桶排序似乎就没有用了。

这时我们引进另一个排序方法，冒泡排序。

冒泡排序

冒泡排序的基本思想是：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来

举个例子：比如有五个数字：2, 4, 3, 9, 7

如果想要从大到小排序，则首先对比第一个数字 2

因为2比4小，所以调换位置：

4, 2, 3, 9, 7 第一次遍历

同理，接下来与3比较：

4, 3, 2, 9 ,7

4, 3, 9, 2, 7

4, 3, 9, 7, 2 遍历4次

因为2从开始一直交换到末尾，就像泡泡浮出水面一样，所以很形象地称之为冒泡排序

接下来也是一样的道理：

4, 3, 9, 7, 2 第二次遍历

4, 3, 9, 7, 2

4, 9, 3, 7, 2

4, 9, 7, 3, 2 遍历3次 （2已经是最小的了）

4, 9, 7, 3, 2 第三次遍历

9, 4, 7, 3, 2

9, 7, 4, 3, 2 遍历2次

9, 7, 4, 3, 2 第四次遍历

9, 7, 4, 3, 2 遍历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
27
28
29
30
31
#输入总列表
total_list = []

#输入数字，输入名字，将数字与名字作为一个列表输入总的列表中
flag = True
while flag:
    cache_list = []
    number = input("give me number to input:\n")
    cache_list.append(number)
    name = input("give me name to input:\n")
    cache_list.append(name)
    total_list.append(cache_list)
    check = input("Done?")
    if check == 'yes' or check == 'Yes':
        flag = False
    else:
        flag = True

#有n个输入就遍历(n-1)次
for i in range(len(total_list)-1):
    #如上面演示的一样，已经排序好的就不必再比对了，节省空间
    for j in range(len(total_list)-1-i):
        #如果a<b，则替换ab
        if int(total_list[j][0]) < int(total_list[j+1][0]):
            cache = total_list[j]
            total_list[j] = total_list[j+1]
            total_list[j+1] = cache

#依据数字从高到低打印匹配的名字
for i in range(0, len(number_list)):
    print(total_list[i][1])

因为冒泡排序是双重嵌套循环，所以时间复杂度是O(N2)。

假如我们的计算机每秒钟可以运行10亿次，那么对1亿个数进行排序，桶排序只需要0.1秒，而冒泡排序则需要1千万秒，达到115天之久！

快速排序

假设我们对9, 4, 3, 7, 2, 6, 5这七个数排序

先将最左边的9设置为基准数，然后从右往左找比9更小的数字，从左往右找比9更大的数字：

9, 4, 3, 7, 2, 6, 5 从右往左 –> 5就是比9小的数字

9, 4, 3, 7, 2, 6, 5 从左往右 –> 9没有遇到比他更大的数字，而是遇到了5， 当两个数字相遇时，则这个数字与基准数互换

5, 4, 3, 7, 2, 6, 9 再实行一遍这个步骤 （5为基准数）从右往左 –> 2比5小

5, 4, 3, 7, 2, 6, 9 从左往右 –> 7比5大

5, 4, 3, 2, 7, 6, 9 互换 2， 7

2, 4, 3, 5, 7, 6, 9 从右往左 –> 7 与 2重合， 与基准数5互换位置

这样基准数5左边的都比5小，右边的都比5大，按这样的方法继续排序5的左边与右边：

2, 4, 3, 5, 6, 7, 9

2, 3, 4, 5, 6, 7, 9 这样就全部排序好了

快速排序之所以比较快，是因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的书全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样只能在相邻的数之间进行交换，交换的距离就大的多了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的，O(N2)，它的平均时间复杂度为O(NlogN)。

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
#输入数字列表
number_list = []

#定义快速排序放大方法
def quicksort (left, right):
    #如果最左边大于最右边，说明已经操作完成，直接返回
    if left > right:
        return
    temp = int(number_list[left])  #列表中最左边的数（基准数）
    i = left
    j = right
    while i != j: #如果i和j没有接触的话
        while int(number_list[j]) >= temp and i < j: #从列表最右边的数字开始寻找比基准数小的数字
            j -= 1

        while int(number_list[i]) <= temp and i < j: #从列表最左边的数字开始寻找比基准数大的数字
            i += 1

        if i < j: #如果找到的两个数字没有重叠，互换这两个数字
            t = int(number_list[i])
            number_list[i] = number_list[j]
            number_list[j] = t


    number_list[left] = number_list[i] #当最终两个数字接触后，基准数与接触的数字互换位置
    number_list[i] = temp
    quicksort (left, i-1) #对基准数左边进行排序
    quicksort(i+1, right) #对基准数右边进行排序

#用户输入数字，'done' 结束输入
flag = True
while flag:
    number = input("give me number to input:\n")
    if number == 'done':
        flag = False
        break
    number_list.append(number)
    flag = True

#最左边的数是0，最右边的数是长度-1（因为包含0）
quicksort(0, len(number_list)-1)
print(number_list)
  • Copyrights © 2020-2024 Yangyang Cui

请我喝杯咖啡吧~

支付宝
微信