排序算法（歸并排序法待補充）

要點概論：

1. 冒泡排序法

2. 選擇排序法

3. 插入排序法

4. 快速排序法

5. 歸并排序法

6. python 語言提供的排序算法

1. 冒泡排序法

　　冒泡排序法時最簡單的排序算法。對于包含 N 個元素的清單 A ，按遞增順序排列的冒泡法的算法如下。

　　

　　1）第一輪比較：從第一個元素開始，對清單中所有 N 個元素進行兩兩大小比較，如果不滿足升序關系，則交換。

　　　　即 A[0] 與 A[1] 比較，若A[0] > A[1] ， 則 A[0] 與 A[1] 交換；然後 A[1] 與 A[2] 比較，若A[1] > A[2] ，則 A[1]  與  A[2] 交換； 

　　　　......直至最後 A[N -2] 與 A[N - 1] 比較， 若 A[N - 2] > A[N -1] ，則 A[N -2] 與 A[N - 1] 交換。

　　　　第一輪比較完成後，清單元素中最大的數 “沉” 到清單最後，而那些較小的數如同氣泡一樣上浮一個位置，顧名思義 “冒泡法” 排序

　　2）第二輪比較：從第一個元素開始，對清單中前 N - 1 個元素（第 N 個元素，即 A[N - 1]已經最大，無須參加排序）繼續兩兩大小比較，如果不滿足升序關系，則交換。

　　　　第二輪比較完成後，清單元素中次大的數 “沉” 到最後，即 A[N - 2] 為清單元素中次大的數。

　　3）以此類推，進行第 N - 1 輪比較後，清單中所有元素均按遞增順序排好序。

　　PS：若要按遞減順序對清單排序，則每次兩兩大小比較時，如果不滿足降序關系，則交換即可。

　　冒泡排序法的過程如下表所示：

原始清單	2	97	86	64	50	80	3	71	8	76
第一輪比較	2	86	64	50	80	3	71	8	76	97
第二輪比較	2	64	50	80	3	71	8	76	86	97
第三輪比較	2	50	64	3	71	8	76	80	86	97
第四輪比較	2	50	3	64	8	71	76	80	86	97
第五輪比較	2	3	50	8	64	71	76	80	86	97
第六輪比較	2	3	8	50	64	71	76	80	86	97
第七輪比較	2	3	8	50	64	71	76	80	86	97
第八輪比較	2	3	8	50	64	71	76	80	86	97
第九輪比較	2	3	8	50	64	71	76	80	86	97

　　冒泡排序算法的主要時間消耗時比較次數。

　　當  i = 1 時，比較次數為 N - 1；當 i = 2 時，比較次數為 N - 2；依次類推。總共比較次數為：（N -1）+（N - 2）+ ...... + 2 + 1 = N（N -1）/ 2。

　　故冒泡排序法的時間複雜度為 O(N²).

　　

　　冒泡排序算法的實作（bubbleSort.py）：

def bubbleSort(a):
    for i in range(len(a)-1,-1,-1):     # 外循環
        for j in range(i):                     # 内循環
            if a[j] > a[j + 1]:                # 大數往下沉
                a[j],a[j + 1] = a[j + 1],a[j]
        # print(a)      # 跟蹤調試

def main():
    a = [2,97,86,64,50,80,3,71,8,76]
    bubbleSort(a)
    print(a)

if __name__ == '__main__':
    main()

# 程式運作結果如下：
# [2, 3, 8, 50, 64, 71, 76, 80, 86, 97]         

bubbleSort.py

 　

2. 選擇排序法

　　對于包含 N 個元素的清單 A ，按遞增順序排序的選擇法的基本思想是：每次在若幹無序資料中查找最小數，并放在無序資料中的首位。其算法如下：

　　

　　1）從 N 個元素的清單中找最小值及其下标，最小值與清單的第一個元素交換。

　　2）從清單的第二個元素開始的 N - 1 個元素中再找最小值及其下标，該最小值（即整個清單元素的次小值）與清單第二個元素交換。

　　3）以此類推，進行第 N - 1 輪選擇和交換後，清單中所有元素均按遞增順序排好序。

　　PS：若要按遞減順序對清單排序，隻要每次查找并交換最大值即可。

　　選擇排序法的過程如下表所示：

原始數組	59	12	77	64	72	69	46	89	31	9
第一輪比較	9	12	77	64	72	69	46	89	31	59
第二輪比較	9	12	77	64	72	69	46	89	31	59
第三輪比較	9	12	31	64	72	69	46	89	77	59
第四輪比較	9	12	31	46	72	69	64	89	77	59
第五輪比較	9	12	31	46	59	69	64	89	77	72
第六輪比較	9	12	31	46	59	64	69	89	77	72
第七輪比較	9	12	31	46	59	64	69	89	77	72
第八輪比較	9	12	31	46	59	64	69	72	77	89
第九輪比較	9	12	31	46	59	64	69	72	77	89

　　

　　選擇排序算法的主要時間消耗時比較次數。

　　當 i = 1時，比較次數時 N - 1；當 i = 2 時，比較次數為 N - 2；以此類推。總共比較次數為：（N - 1）+（N - 2）+ ...... + 2 + 1 = N（N - 1）/ 2。

　　故選擇排序算法的時間複雜度為 O(N²)。

　　選擇排序算法的實作：

def selectionSort(a):
    for i in range(0,len(a)):            # 外循環 （0 ~ N-1）
        m = i                            # 目前位置下标
        for j in range(i+1,len(a)):     # 内循環
            if a[j] < a[m]:             # 查找最小值的位置
                m = j                   
        a[i],a[m] = a[m],a[i]           #元素交換
        # print(a)      # 跟蹤調試

def main():
    a = [59,12,77,64,72,69,46,89,31,9]
    selectionSort(a)
    print(a)
    
if __name__ == '__main__':
    main()

# 程式運作結果如下：
# [9, 12, 31, 46, 59, 64, 69, 72, 77, 89]      

selectionSort.py

3. 插入排序法

　　對于包含 N 個元素的清單 A ，按遞增順序排序的插入排序法的基本思想是：依次檢查清單中的每個元素，将其插入到其左側已經排好序的清單中的适當位置。其算法如下：

　　

　　1）第二個元素與清單中其左側的第一個元素比較，如果 A[0] > A[1] ，則交換位置，結果左側兩個元素排序完畢。

　　2）第三個元素依次與其左側的清單的元素比較，直至插入對應的排序位置，結果左側的三個元素排序完畢。

　　3）依次類推，進行第 N-1 輪比較和交換後，清單中所有元素均按遞增順序排好序。

　　PS：若要按遞減順序對清單排序，隻要每次查找并交換最大值即可。

　　插入排序法的過程如下表所示：

原始數組	59	12	77	64	72	69	46	89	31	9
第一輪比較	12	59	77	64	72	69	46	89	31	9
第二輪比較	12	59	77	64	72	69	46	89	31	9
第三輪比較	12	59	64	77	72	69	46	89	31	9
第四輪比較	12	59	64	72	72	69	46	89	31	9
第五輪比較	12	59	64	69	72	77	46	89	31	9
第六輪比較	12	46	59	64	69	72	77	89	31	9
第七輪比較	12	46	59	64	69	72	77	89	31	9
第八輪比較	12	31	46	59	64	69	72	77	89	9
第九輪比較	9	12	31	46	59	64	69	72	77	89

　　在最理想的情況下（清單處于排序狀态），while 循環僅需要一次比較，故總的運作時間為線性；

　　在最差的情況下（清單為逆序狀态），此時内循環指令執行次數為： 1 + 2 + ...... +N - 1 = N（N - 1）/ 2 。

　　故插入排序算法的時間複雜度為 O(N²) 。

　　　插入排序算法的實作（insertSort.py）。

def insertSort(a):
    for i in range(1,len(a)):                   # 外循環 （1 ~ N-1）
        j = i
        print(j)
        # time.sleep(1)
        while (j > 0) and (a[j] < a[j - 1]):   # 内循環
            a[j],a[j - 1] = a[j - 1],a[j]       # 元素交換
            j -= 1                              # 繼續循環
            print(j)
        # print(a)      跟蹤調試

def main():
    a = [59,12,77,64,72,69,46,89,31,9]
    insertSort(a)
    print(a)

if __name__ == '__main__':
    main()

# 程式運作結果如下：
# [9, 12, 31, 46, 59, 64, 69, 72, 77, 89]      

insertSort.py

4. 快速排序法

　　快速排序法是對冒泡排序的一種改進，其基本思想是：

　　通關過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料要小；然後遞歸對這兩部分資料分别進行快速排序。

　　

　　快速排序算法的一趟排序和操作步驟如下：

　　1）設定兩個變量 i 和 j ，分别為清單首末元素的下标，即  i = 0 ，j = N - 1。

　　2）設定清單的第一個元素作為關鍵資料，即 key = A[0]。

　　3）從 j 開始向前搜尋，找到第一個小于 key 的值 A[ j ] ，将 A[ j ] 和 A[ i ] 互換。

　　4）從 i  開始向後搜尋，找到第一個大于 key 的值 A[ i ] ，将 A[ i ] 和 A[ j ] 互換。

　　5）重複第（3）和（4）步，直到 i = j 。

　　快速排序的一趟排序的算法如下表所示：

下标	1	2	3	4	5	6	7	8	9
原始數組	59	12	77	64	72	69	46	89	31	9
第一輪比較交換	9	12	77	64	72	69	46	89	31	59
第二輪比較交換	9	12	59	64	72	69	46	89	31	77
第三輪比較交換	9	12	31	64	72	69	46	89	59	77
第四輪比較交換	9	12	31	59	72	69	46	89	64	77
第五輪比較交換	9	12	31	46	72	69	59	89	64	77
第六輪比較交換	9	12	31	46	59	69	72	89	64	77
第七輪比較交換	9	12	31	46	59	69	72	89	64	77

　　快速排序最壞情況下，每次劃分選取的基準都是目前無序清單中關鍵字最小（或最大）的記錄，時間複雜度為 O(N²) ；

　　平均情況下，其時間複雜度為 O(Nlog2N) 。

　　快速排序算法的實作（quickSort.py）。

def quickSort(a,low,high):      # 對清單 a 快速排序，下界為 low ，上界為 high
    i = low                     # i 等于清單下界
    j = high                    # j 等于清單上界
    if i >= j:                  # 如果下界大于等于上界，法妞結果清單 a
        return a
    key = a[i]                  # 設定清單的第一個元素作為關鍵資料
    # print(key)        # 跟蹤調試
    while i < j:        # 循環直到 i = j
        while i < j and a[j] >= key:    # j 開始向前搜尋，找到第一個小于 key 的值 a[j]
            j = j - 1
        a[i] = a[j]
        while i < j and a[i] <= key:    # i 開始向後搜尋，找到第一個大于 key 的 a[i]
            i = i + 1
        a[j] = a[i]
    a[i] = key                  # a[i] 等于關鍵資料
    # print(a)      # 跟蹤調試
    quickSort(a,low,i - 1)      # 遞歸調用快速排序算法（清單下界為 low ，上界為 i - 1 ）
    quickSort(a,j + 1,high)     # 遞歸調用快速排序算法（清單下界為 j + 1 ，上界為 high）

def main():
    a = [59,12,77,64,72,69,46,89,31,9]
    quickSort(a,0,len(a) - 1)
    print(a)

if __name__ == '__main__':
    main()

# 程式運作結果如下
# [9,12,31,46,59,64,69,72,77,89]      

quickSort.py

5. 歸并排序法（待補充）

6. python 語言提供的排序算法

　　python 語言提供了下列排序算法：

　　1）内置資料類型 list 中的方法 sort() ，把清單的項按升序重新排列。

　　2）内置函數 sorted() 則保持原清單不變，函數傳回一個新的包含按升序排列的項的清單。

　　python 系統排序方法使用了一種歸并排序算法的版本，但使用了 python 無法編寫的底層實作，進而避免了 python 本身附加的大量開銷，故其速度比 mergeSort.py 快很多（10 ~ 20倍）。

　　系統排序方法同樣用于任何可比較的資料類型，例如，python 内置的 str ，int 和 float 資料類型，

　　

　　

轉載于:https://www.cnblogs.com/HZY258/p/8469454.html