冒泡排序算法。

冒泡排序

冒泡排序是的多次通过整个列表。它比较相邻的项目并交换无序的项目。每一次完成一个列表都会把最大值放在合适的位置。实质上，每个项目都会’冒泡’在它所属的位置。

冒泡排序和选择排序的区别？

冒泡排序：两个元素相比较，如果发现较小的在后面，就要交换两个相邻的元素。

选择排序：先从a[0]开始，哪个元素最小就记下它所在的位置p，等这一轮排序后，把a[0]和a[p]的数交换。

选择排序每扫描一遍，只需要一次真正的交换。而冒泡排序一轮中需要交换很多次。

图展示了冒泡排序的第一遍。阴影部分查看它们是否有序。如果列表中有n个项目，那么在第一遍中会有n-1对项目被比较。值得注意的是，一旦最大值是一对的一部分，它将不断移动，直到通过完成。

在第二轮开始时，现在已经有了最大值，有n-1个项目需要排序，意味这有n-2对需要比较。由于每论比较都会产生一个最大值，因此需要n-1轮进行比较。完成n-1轮后，最小的项目在其正确的位置，不需要做任何的处理。代码展示了bubbleSort功能。将列表作为参数，并根据需要通过交换项目修改它。

这种交换操作，有时被称为替换，大多数的编程语言和python的实现方式不一样。通常，交换列表中的两个元素需要临时变量。代码如下。

temp = alist[i]
alist[i] = alist[j]
alist[j] = temp

交换列表中的第i个和第j个项目，如果没有临时存储，其中的一个值将会被覆盖。

在PYthon中，可以执行同时分配。语句a,b=b,a将导致两个赋值语句同时执行。使用同时分配，交换操作可以在一个语句中完成。

在代码中使用前面介绍的三部过程中执行第i和i+1项目的交换。但是在python可以使用同时分配来交换数据。

# -*- coding:utf-8 -*-

def bubbleSort(alist):
    for passnum in range(len(alist)-1,0,-1): #一共 len(alist)-1 轮排序
        for i in range(passnum):  #每passnum轮中有(n-passnum)次比较
            if alist[i]>alist[i+1]:
                temp = alist[i]
                alist[i] = alist[i+1]
                alist[i+1] = temp 

alist = [54,26,93,17,77,31,44,55,20]
bubbleSort(alist)
print(alist)

分析冒泡排序，我买你注意不管项目如何排列在初始列表中，在一个长度为n的列表中，会有n-1轮排序。下图展示了在每一轮中需要比较的个数。总共比较次数是1到(n-1)的整数和。仍然是O(n^2)，在最好的情况下，如果列表已经排序好，不需要进行交换。但是在最坏的情况下，每次比较都会进行交换。平均而言，我们换了一般的时间。

Pass    Comparisons
1        n−1
2        n−2
3        n−3
...        ...
n−1        1

冒泡排序通常被认为是最无效的排序方法，因为它必须知道最终位置之前交换项目。这种浪费的交换操作非常耗时，由于冒泡排序使得通过列表的整个未排序部分，所以它能够执行大多数排序算法不能做的事情。特别是，在一轮中没有数据交换，我们知道这个列表是已经排序好的。如果发现已经是排序好的，则可以修改停止冒泡排序。这意味着列表需要更少的轮排序。冒泡排序可能具有的优势，因为它会识别已排序的列表并停止。下面的代码，被称为优化的冒泡排序。

这段优化的代码会判断一下这是否已经是一个排序好的列表，如果是就退出了。

# -*- coding:utf-8 -*-

def shortBubbleSort(alist):
    exchanges = True  #是否交换
    passnum = len(alist) - 1 # 轮数
    while passnum > 0 and exchanges:
        exchanges = False
        for i in range(passnum):
            if alist[i] > alist[i+1]:
                exchanges = True 
                temp = alist[i]
                alist[i] = alist[i+1]
                alist[i+1] = temp
        passnum = passnum-1 

alist =  [20,30,40,90,50,60,70,80,100,110]
shortBubbleSort(alist)
print(alist)