【和我一起学算法】排序篇——冒泡排序

【和我一起学算法】排序篇——冒泡排序

最近在图书馆借了一本有关算法的书，是用Python写的，我之前没有系统的学过Python，正好趁着这次重温算法的机会，学习一下Python。

怎么说呢，从我的角度看Python就觉得Python比我之前学过的C、C++、C#、Java都要简洁明了，而且更容易读懂代码，可读性很高，就很适合零基础入门的一种语言，有了之前学习其他编程语言的基础，对我来说，学习Python是更加容易的。好了，废话不多说了，开始了。

目录

冒泡排序

算法原理

举例

 第一轮排序

第二轮排序

第三轮排序

第四轮排序

第五轮排序

算法伪代码

 完整代码

---

排序算法算是算法中最简单、最基础的了，排序就是将一组数列（多是打乱顺序的整数数列）按照顺序从小到大或从大到小重新排列。

冒泡排序 算法原理

排序算法的基本原理就是比较相邻两个数字的大小，将两数中比较大的那个数换到后面来，不断交换顺序就可以将最大的那个数放到数列的末尾，然后再重头交换，直到将数列排成有序数列。

举例

以数列[7,3,5,1,9,4]为例，最初的数列顺序是：

初始队列 735194  第一轮排序

按照冒泡排序的原理，依次比较相邻两个数的大小，大的放后面。

7和3比，7大放后面：

第一轮 交换7和3 375194

7和5比，7大放后面：

第一轮 交换7和5 357194

7和1比，7大放后面：

第一轮 交换7和1 351794

7和9比，7小，不用交换；

9和4比，9大放后面：

第一轮 交换9和4 351749

第一轮排序结束，最大数9已在末尾。回到起点，重新比较相邻两个数的大小，开始新一轮冒泡排序。

第二轮排序

3和5比，3小，不用交换；

5和1比，5大放后面：

第二轮 交换5和1 315749

5和7比，5小，不用交换；

7和4比，7大，放后面：

第二轮 交换7和4 315479

7和9比，7小，不用交换；

这样倒数第二大的数已经在倒数第二的位置了，第二轮冒泡排序就结束了。

第三轮排序

第三轮排序开始，依旧是回到数列的开头，依次比较相邻两个数的大小，将较大数放后面。

3和1比，3大放后面：

第三轮 交换3和1 135479

 3和5比，3小不用交换；

5和4比，5大放后面：

第三轮 交换5和4 134579

 这一轮排序，将第三大的数交换到了数列倒数第三的位置。

第四轮排序

开启第四轮排序，重新回到数列开头。

1和3比，不用交换位置；

3和4比，不用交换位置；

第五轮排序

开启第五轮排序，重新回到数列开头，比较相邻两个数的大小。

1和3比，不用交换位置；

五轮排序过后，冒泡排序完毕。一共6个数，排序5轮。说明一个n个数的数列需要排序n-1轮。冒泡排序的时间复杂度是。

算法伪代码

iList = randomList(20)
if len(iList) <= 1:
    return iList
for i in range(1, len(iList):
    for j in range(0, len(iList)-i):
        if iList[j] >= iList[j+1]:
            iList[j], iList[j+1] = iList[j+1], iList[j]

 完整代码

bubbleSort.py

from randomList import randomList
import timeit

iList = randomList(20)

def bubbleSort(iList):
    '''冒泡排序 '''
    if len(iList) <= 1:
        return iList
    for i in range(1, len(iList)):
        for j in range(0, len(iList)-i): 
            if iList[j] >= iList[j+1]: #比较相邻两数的大小
                iList[j], iList[j+1] = iList[j+1], iList[j] #将大数交换到靠后的位置
        # print("第 %d 轮排序结果:" %i, end="")
        # print(iList)
    return iList

if __name__ == "__main__":
    print(iList)
    print(bubbleSort(iList))
    print(timeit.timeit("bubbleSort(iList)", "from __main__ import bubbleSort,iList", number=100))

构建随机数列

randomList.py

import random

def randomList(n):
    '''返回一个长度为n的整数列表，数据范围[0,1000) '''
    iList = []
    for i in range(n):
        iList.append(random.randrange(1000))
    return iList

if __name__ == "__main__":
    iList = randomList(10)
    print(iList)

下一篇文章会写选择排序，明天一定写完【狗头】