冒泡排序

1、什么是冒泡排序

冒泡排序需要多次遍历列表。它比较相邻的项并交换那些无序的项。每次遍历列表将下一个最大的值放在其正确的位置。假如有n个项需要排序，第一遍遍历有n-1项需要比较，第二遍就有n-2项需要比较，以此类推，最终得遍历n-1次才完成排序。
以下是第一次遍历，可以看到最大的93被移到了最后。而且93前面的称为无序区，已经排序号的称为有序区。

image.png

2、冒泡排序中交换

交换列表中的两个元素通常是需要使用临时的存储位置，

temp = L[i]
L[i] = L[j]
L[j] = temp

image.png

但是在Python中，可以执行同时赋值，

a,b = b,a

image.png

3、冒泡排序的Python实现

# -*- coding: utf-8 -*-
def bubbleSort(alist):
    for passnum in range(len(alist)-1, 0, -1):
        for i in range(passnum):
            if alist[i]>alist[i+1]:
                # temp = alist[i]
                # alist[i] = alist[i+1]
                # alist[i+1] = temp
                alist[i], alist[i+1] = alist[i+1], alist[i]


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

4、分析冒泡排序

不管项如何在初始列表中排列，都会进行n-1次遍历以排序大小为n的列表。那么每次遍历的比较次数是多少？第一次遍历是n-1次，第二次遍历是n-2，以此类推，比较的总数是第n-1个整数的和。前 n 个整数的和是 1/2n^2 + 1/2n。 第 n-1 个整数的和为 1/2n^2 + 1/2n -n，其为 1/2n^2 - 1/2n。 这仍然是 O(n^2 ）比较。每次比较完了之后进行交换，最好的情况是不会进行交换，最坏的情况是，每次比较都得交换元素。

image.png

5、短冒泡排序

冒泡排序的优点：

• 识别排序列表，如果第n次遍历中没有交换元素，则我们可以知道该列表已经是一个排序列表。
• 停止排序，如果在第n次遍历中没有交换元素，我们可以知道该列表已经是排序列表，并且停止继续遍历。

上面的写法在已经是排序列表之后并不会停下来，它还是会完成n-1次排序，我们需要修改它，使它可以停止下来，这种可以判断称为短冒泡排序。

# 短冒泡排序
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
                alist[i], alist[i+1] = alist[i+1], alist[i]
        passnum = passnum-1

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