資料結構與算法：排序算法的穩定性以及各性能比較python實作

招聘筆試中經常會考到排序算法，在此做一個總結。

一、算法概念

1.排序算法的穩定性

假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序後的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩定的；否則稱為不穩定的。

1.簡單選擇排序

一趟簡單排序的操作為：通過n-i次關鍵字間的比較，從n-i+1個記錄中選出關鍵字最小的記錄，并和第i（1<=i<=n）個記錄交換之。

• 時間複雜度:

  

• 空間複雜度:

  

• 穩定性：不穩定

#選擇排序
def selection_sort(list1):
    print('selection_sort:')
    list2 = list1.copy()
    n = len(list2)
    for i in range(0, n - 1):
        min_ = i
        print(list2)
        for j in range(i + 1, n):
            if list2[j] < list2[min_]:
                min_ = j
        list2[i],list2[min_] = list2[min_],list2[i]
    print(list2,'\n')
           

2.冒泡排序

它重複地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果他們的順序（如從大到小、首字母從A到Z）錯誤就把他們交換過來。走訪元素的工作是重複地進行直到沒有相鄰元素需要交換，也就是說該元素已經排序完成。

• 時間複雜度：

  

• 空間複雜度：

  

• 穩定性：穩定

#冒泡排序
def bubble_sort(list1):
    print('bubble_sort:')
    list2 = list1.copy() 
    n = len(list2)
    for i in range(0, n - 1):
        print(list2)
        for j in range(0, n - i - 1 ):
            if list2[j] > list2[j+1]:
                list2[j],list2[j+1] = list2[j+1],list2[j]
    print(list2,'\n')
           

3.插入排序 

将序列的第一個元素當做已經排序好的序列，然後從後面的第二個元素開始，逐個元素進行插入，直到整個序列有序為止。第i趟操作為：在含有i-1個記錄的有序子序列r[1...i-1]中插入一個記錄r[i]後，變成含有i個記錄的有序子序列r[1..i]。

• 時間複雜度：

  

• 空間複雜度：

  

• 穩定性：穩定

#插入排序
def insertion_sort(list1):
    print('insertion_sort:')
    list2 = list1.copy()
    n = len(list2)
    for i in range(1,n):
        print(list2)
        value = list2[i]
        pos = i
        while pos > 0 and value< list2[pos - 1]:
            list2[pos] = list2[pos - 1]
            pos -= 1
        list2[pos] = value
    print(list2)
           

4.希爾排序

希爾排序（有時稱為“遞減遞增排序”縮小增量排序 Diminishing Increment Sort）通過将原始清單分解為多個較小的子清單來改進插入排序，每個子清單使用插入排序進行排序。 選擇這些子清單的方式是希爾排序的關鍵。不是将清單拆分為連續項的子清單，希爾排序使用增量i（有時稱為 

gap

），通過選擇 i 個項的所有項來建立子清單。

下圖1中顯示增量為3得到的子清單。個子清單可以通過插入排序進行排序。完成這些排序後，我們得到如圖2所示的清單。雖然這個清單沒有完全排序，但發生了很有趣的事情。 通過排序子清單，我們已将項目移動到更接近他們實際所屬的位置。

圖1-2 

圖3展示了使用增量為 1 的插入排序; 換句話說，标準插入排序。注意，通過執行之前的子清單排序，我們減少了将清單置于其最終順序所需的移位操作的總數。對于這種情況，我們隻需要四次移位完成該過程。

圖3 

• 時間複雜度：

  

   當n在某個特定範圍内，希爾排序所需的比較和移動次數約為

  

  ,當

  

  時，可以減少到

  

• 空間複雜度：

  

• 穩定性：不穩定

#希爾排序
def shell_sort(list1, gap):
    print('shell_sort')
    list2 = list1.copy()
    n = len(list2)
    sub_n = n//gap
    for i in range(gap):
#         print(i, list2)       
        for j in range(1, sub_n):
            pos = j 
            value = list2[pos * gap + i]
#             print(value)
            while pos > 0 and value < list2[(pos - 1) * gap + i]:
#                 print(list2)
#                 print(pos, value, list2[(pos - 1) * gap + i])
                list2[pos*gap+i] = list2[(pos - 1) * gap + i]
                pos -= 1 
            list2[pos*gap+i] = value
            print('move:', list2)
    insertion_sort(list2)
           

5.堆排序

詳細原理介紹請看相關博文：

https://blog.csdn.net/qq_18888869/article/details/88886270

6.歸并排序

首先介紹一下分治法（Divide and Conquer）

很多有用的算法結構上是遞歸的，為了解決一個特定問題，算法一次或多次遞歸調用其自身以解決若幹子問題。這些算法遵循分值的思想。分治法在每層遞歸時有三個步驟：

• 分解：分解原問題為若幹子問題，這些子問題是原問題的規模最小的執行個體
• 解決：解決這些子問題，遞歸的求解這些子問題。當子問題規模足夠小，就可以直接求解
• 合并：合并這些子問題的解成原問題的解

下面介紹歸并排序如何利用分治法解決問題：

考慮我們排序這個數組：[10,23,51,18,4,31,13,5] ，我們遞歸地将數組進行分解 

 當數組被完全分隔成隻有單個元素的數組時，我們需要把它們合并回去，每次兩兩合并成一個有序的序列。

python實作： 

• 分解：将待排序的n個元素分成各包含n/2個元素的子序列
• 解決：使用歸并排序遞歸排序兩個子序列
• 合并：合并兩個已經排序的子序列以産生已排序的答案
• 時間複雜度：

  

• 空間複雜度：

  

• 穩定性：穩定

#歸并排序
def merging_sort(list1, ):
    list2 = list1.copy()
    length_list2 = len(list2)
    if length_list2 <= 1:
        return list2
    else:
        mid = int(length_list2/2)
        left_list = merging_sort(list2[:mid])
        right_list = merging_sort(list2[mid:])
        merged_list = merge_sorted_list(left_list, right_list)
        
        return merged_list
    
    

def merge_sorted_list(left_list, right_list):
    left_n = len(left_list)
    right_n = len(right_list)
    mergedlist = list()
    i = j = 0
    while i < left_n and j < right_n:
        if left_list[i] < right_list[j]:
            mergedlist.append(left_list[i])
            i += 1
        else:
            mergedlist.append(right_list[j])
            j += 1
    if i < left_n:
        mergedlist.extend(left_list[i:])
    if j < right_n:
        mergedlist.extend(right_list[j:])
    
    return mergedlist
           

7.快速排序

快排（與歸并排序一樣）也是一種分而治之(divide and conquer)的政策。歸并排序把數組遞歸成隻有單個元素的數組，之後再不斷兩兩 合并，最後得到一個有序數組。這裡的遞歸基本條件就是隻包含一個元素的數組，當數組隻包含一個元素的時候，我們可以認為它本來就是有序的（當然空數組也不用排序）。

快排的工作過程其實比較簡單，三步走：

• 選擇基準值 pivot 将數組分成兩個子數組：小于基準值的元素和大于基準值的元素。這個過程稱之為 partition
• 對這兩個子數組進行快速排序。
• 合并結果

• 時間複雜度：

  

• 空間複雜度：

  

• 穩定性：不穩定

#快速排序
def quick_sort(list2, low, high):
    print('quick_sort:')
#     list2 = list1.copy()
    if len(list2[low:high+1]) <= 1:
        return list2
    else:
        list2, pivot = partition(list2, low, high)
        print(list2)
        quick_sort(list2, low, pivot-1 )
        quick_sort(list2, pivot+1, high)
    
    print(list2)
    
def partition(list2, low, high):
#     list2 = list1.copy()
    pivotkey = list2[low] 
    while low < high:
#         print('low, high: {},{}'.format(low, high))
        while low < high and pivotkey < list2[high]:
            high -= 1
#             print('high:',high)
        list2[low] = list2[high]
        while low < high and pivotkey > list2[low]:
            low += 1
#             print('low:', low)
        list2[high] = list2[low]
        
    list2[low] = pivotkey
    
    return list2, low
           

8.基數排序

排序方法	平均時間複雜度	最好時間複雜度	最壞時間複雜度	輔助空間	穩定性	備注
冒泡排序	O（n2）	O（n）	O（n2）	O（1）	穩定	n小時較好
簡單選擇排序	O（n2）	O（n2）	O（n2）	O（1）	不穩定	n小時較好
直接插入排序	O（n2）	O（n）	O（n2）	O（1）	穩定	大部分已排序時較好
希爾排序	O（nlogn）~O（n2）	O（n1.3）	O（n2）	O（1）	不穩定	s是所選分組
堆排序	O（nlogn）	O（nlogn）	O（nlogn）	O（1）	不穩定	n大時較好
歸并排序	O（nlogn）	O（nlogn）	O（nlogn）	O（n）	穩定	n大時較好
快速排序	O（nlogn）	O（n）	O（n2）	O（nlogn）~O（n）	不穩定	n大時較好

github代碼：https://github.com/makang101/python-data-structure 

參考：

problem-solving-with-algorithms-and-data-structure-using-python 中文版

資料結構（C語言版）嚴蔚敏