Leetcode-排序-冒泡排序

冒泡排序（Bubble Sort）是一种很原始的排序方法，就是通过不断交换“大数”的位置达到排序的目的。因为不断出现“大数”类似于水泡不断出现，因此被形象地称为冒泡算法。

原理

从一组数列（列表）中挑选一个最大的数，如果这个数列比较小，有可能我们一眼就看出谁最大，但是如果数列比较大，那么就不好确定了，冒泡排序不需要直接找出数列中最大的那个数，只需要在两个数中找出最大的就可以了。

冒泡算法的原理是比较两个相邻数字的大小，将两个数中比较大的那个数交换到靠后的位置。这样不断交换下去就可以将最大的那个数放到最后的位置，然后从头开始将第二大的数放到倒数第二的位置上，如此反复，知道将数列变成有序数列。

举例：

7 3 5 1 9 4

1.第一轮排序

第1次排序，按照冒泡排序的原理，比较相邻两个数的大小，从数列头开始第一次比较7和3的大小，7比3大，交换7和3的位置，把7放在靠后的位置。交换的代码为：

   if iList[i]>=iList[i+1]
        iList[i],iList[i+1]=iList[i+1],iList[i]
    #这里你可能会疑惑为什么iList[1]被覆盖了，还能给iList[i+1]赋值，这里为python的序列解包，相关语法可查python官方文档。

交换后如图所示

3 7 5 1 9 4

第2次比较7和5的大小，发现7比5大，交换7和5的位置，结果如图：

3 5 7 1 9 4

第3次比较7和1的大小，7比1大，交换位置，结果如图：

3 5 1 7 9 4

第4次比较7和9的大小，7比9小，不交换位置，结果如图：

3 5 1 7 9 4

第5次比较9和4的位置，9比4大，交换位置，结果如下：

3 5 1 7 4 9

到此，第一轮排序已经结束，成功序列中最大的值9放入最后的位置。然后再进行下一轮排序。

2.第二轮排序

第一次  3 5 1 7 4 9
第二次  3 1 5 7 4 9
第三次  3 1 5 7 4 9
第四次  3 1 5 4 7 9

3.第三轮排序

第一次  1 3 5 4 7 9
第二次  1 3 5 4 7 9
第三次  1 3 4 5 7 9

4.第四轮排序

第一次  1 3 4 5 7 9
第二次  1 3 4 5 7 9

5.第五轮排序

第一次  1 3 4 5 7 9

代码实现

建立无序序列

#实现创建一个无序的数组,名字为randomList
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)

对无序序列进行冒泡排序

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) - 1):
            if iList[j] >= iList[j + 1]:  # 比较相邻两数的大小
                iList[j], iList[j + 1] = iList[j + 1], iList[j]  # 将较大的数交换到靠后的位置

    return iList
if __name__=="__main__":
    print(iList)
    print(bubbleSort(iList))
    print(timeit.timeit("bubbleSort(iList)","from __main__ import bubbleSort,iList",number=100))#用bubbleSort函数排序100遍用的时长

整理于2020年10月13日早