什么是冒泡排序？冒泡排序算法的实现过程

冒泡排序实现原理

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

冒泡算法的基本原理：比较相邻两个数字的大小。将两数中比较大的那个数交换到靠后的位置。

不断地交换下去就可以将最大的那个数放到队列的尾部。然后重头再次交换，直到将数列排成有序数列。接下来我们以以数列[5, 9, 3, 1, 2, 8, 4, 7, 6]为例，演示冒泡排序的实现过程，最初的数列顺序如下图所示：

第一轮排序：按照冒泡排序的原理，比较相邻两个数字的大小。从数列末端开始，第1次比较7和6的大小。7>6，交换7和6的位置。把较大的那个数7交换到靠后的位置。

第2次排序比较4和6的大小。6比4大，不需要交换位置。第3次排序比较8和4的大小。4比8小，交换4和8的位置位置。

第4次排序比较2和4的大小。4比2大，不需要交换位置。第5次排序比较2和1的大小。2比1大，不需要交换位置。

第6次排序比较1和3的大小。1比3小，交换1和3的位置。第7次排序比较1和9的大小。1比9小，交换1和9的位置。

第8次排序比较1和5的大小。1比5小，交换1和5的位置。

第一轮排序结束, 成功的将序列中最小的数1交换到了队列最前面。

第二轮排序：过程与前一轮类似，依然从末尾开始进行相邻两个元素的比较当前面的元素比后面的元素大，交换两个元素的位置，第二轮排序只需要进行7次比较

经过第二轮排序后，数列中最小的两个元素已经交换到数列的最前面。

第三轮排序：依旧是回到数列的末尾，重新比较相邻的两个元素。

经过六次比较后，第三轮排序完成， 1,2,3三个最小的元素移动到了数列的头部。

第四轮排序：经过五次比较，第四轮排序完成后，1,2,3,4四个最小的元素移动到了数列的头部。

完整的排序过程需要经过八轮比较(9个元素)，后四轮的排序过程与前面类似，经过八轮排序后，排序过程完成。

一个n个数的数列需要排序n-1轮。这样可以确保得到一个有序的数列。因此冒泡排序的时间复杂度是O(n² )。

冒泡排序代码

在写冒泡排序的代码前，先编写一段程序，创建无序数列，用于测试排序算法。创建无序数列的程序randomList.py，代码如下：

import random

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

if __name__ == "__main__":
    tlist = getrandomlist(10)
    print(tlist)

冒泡排序的程序bubbleSort.py的代码如下：

def bubblesort(tlist):
    '''冒泡排序 '''
    if len(tlist) <= 1:
        return tlist
    for i in range(1, len(tlist)): # 一共进行n-1轮比较(交换)
        for j in range(len(tlist)-1, i-1, -1): # 从列表末尾开始比较,每比较一轮减少一个元素
            if tlist[j-1] >= tlist[j]: #比较相邻两数的大小
                tlist[j-1], tlist[j] = tlist[j], tlist[j-1] #将大数交换到靠后的位置
    return tlist

def bubblesort(tlist):
    '''冒泡排序 '''
    if len(tlist) <= 1:
        return tlist
    for i in range(1, len(tlist)): # 一共进行n-1轮比较(交换)
        for j in range(len(tlist)-1, i-1, -1): # 从最后开始比较,每轮比较结束减少一个元素
            if tlist[j-1] >= tlist[j]: #比较相邻两数的大小
                tlist[j-1], tlist[j] = tlist[j], tlist[j-1] #将大数交换到靠后的位置
    return tlist
if __name__ == "__main__":
    list_ = getrandomlist(10) # 获取随机大小的10个元素
    print(list_) # 打印
    print(bubblesort(list_)) # 打印 排序结果