何谓「排序(Sort)」?

排序是指一组资料中，将资料以「由大到小」或「由小到大」的方式重新排列。
常见的排序演算法有下列几种：

1. 气泡排序法(Bubble Sort)
2. 选择排序法(Selection Sort)
3. 插入排序法(Insertion Sort)
4. 合并排序法(Merge Sort)
5. 快速排序法(Quick Sort)
6. 堆积排序法(Heap Sort)

接下来会逐日开始探讨各种排序演算法，今天就先来看看气泡排序法吧！

气泡排序(Bubble Sort)

在我们讨论气泡排序时，先来点影片，了解气泡排序是怎麽运作。在理解演算法时，影片辅助会相对图片效果较好。

影片参考：https://www.youtube.com/watch?v=xli_FI7CuzA

气泡排序是重复进行「由右往左，将相邻的数字相比後重新排列」的操作

气泡排序的比较次数是，第一次n-1次，第二次n-2次，一直到第n-1次。总次数为(n-1)+(n-1)+...+1=n^2/2，重新排列的次数与排列顺序无关，而是与输入数据有关。最极端的情况就是数据已经由小到大排列好，不需重新排序（交换次数0。气泡排序法的时间复杂度为O(n^2)。

Bubble sort 运作如下：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最後一对。这步做完後，最後的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最後一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

import random

# 从1-100中不重复随机产生9组数字
A = random.sample(range(1,100),9)
# print(A)

#外层变数i，控制内层变数j的上限
for i in range(len(A)-1,0,-1):
    for j in range(i):
        if A[j] > A[j+1]:
            #交换数字
            A[j],A[j+1] = A[j+1],A[j]
    print("气泡排序外层回圈执行第", 9-i,"次")
    # print( )
    for item in A:
        print(item,' ',end="")

执行结果：

气泡排序外层回圈执行第 1 次
9  29  65  46  94  66  35  54  95  
气泡排序外层回圈执行第 2 次
9  29  46  65  66  35  54  94  95  
气泡排序外层回圈执行第 3 次
9  29  46  65  35  54  66  94  95  
气泡排序外层回圈执行第 4 次
9  29  46  35  54  65  66  94  95  
气泡排序外层回圈执行第 5 次
9  29  35  46  54  65  66  94  95  
气泡排序外层回圈执行第 6 次
9  29  35  46  54  65  66  94  95  
气泡排序外层回圈执行第 7 次
9  29  35  46  54  65  66  94  95  
气泡排序外层回圈执行第 8 次
9  29  35  46  54  65  66  94  95

气泡排序会有两种情况，最佳与最好，在两种情况下，比较及交换次数也有所差异：
第一种情况：最佳情况

• 说明：假设排序顺序最终目标为由小到大，而输入资料为由小到大排序，则为最佳情况。换句话说，就是不需要进行任何排序
• 比较次数：O(n^2)
• 交换次数：0

第二种情况：最差情况

• 说明：假设排序顺序为由小到大，但输入资料为由大到小排序，则为最差情况。也就是说，所有资料要重新排序。
• 比较次数：O(n^2)
• 交换次数：O(n^2)