排序演算法對比、總結(Python代碼)

查看更多的專業文章、課程信息、產品信息，請移步至：

「人工智慧LeadAI」公眾號；

官網：www.leadai.org.

作者： CodingFish

原文鏈接：https://www.jianshu.com/p/8e269451795d

排序大的分類可以分為兩種：內排序和外排序。在排序過程中，全部記錄存放在內存，則稱為內排序，如果排序過程中需要使用外存，則稱為外排序。下面講的排序都是屬於內排序。

內排序有可以分為以下幾類：

1、插入排序：直接插入排序、二分法插入排序、希爾排序。

2、選擇排序：直接選擇排序、堆排序。

3、交換排序：冒泡排序、快速排序。

4、歸併排序

5、基數排序

對比

冒泡排序

1.基本思想：兩個數比較大小，較大的數下沉，較小的數冒起來。

2.過程：

比較相鄰的兩個數據，如果第二個數小，就交換位置。

從後向前兩兩比較，一直到比較最前兩個數據。最終最小數被交換到起始的位置，這樣第一個最小數的位置就排好了。

繼續重複上述過程，依次將第2.3...n-1個最小數排好位置。

3.平均時間複雜度：O(n2)

4.優化：

針對問題：

數據的順序排好之後，冒泡演算法仍然會繼續進行下一輪的比較，直到arr.length-1次，後面的比較沒有意義的。

方案：

設置標誌位flag，如果發生了交換flag設置為true；如果沒有交換就設置為false。

這樣當一輪比較結束後如果flag仍為false，即：這一輪沒有發生交換，說明數據的順序已經排好，沒有必要繼續進行下去。

5.Python代碼實現：

@staticmethoddef bubble_sort(arr): for i in range(len(arr)): not_change = True for j in range(len(arr) - 1, i - 1, -1): if arr[j] < arr[j - 1]: tmp = arr[j] arr[j] = arr[j - 1] arr[j - 1] = tmp not_change = False if not_change: breakreturn arr

選擇排序

1.基本思想：

在長度為N的無序數組中，第一次遍歷n-1個數，找到最小的數值與第一個元素交換；

第二次遍歷n-2個數，找到最小的數值與第二個元素交換；

第n-1次遍歷，找到最小的數值與第n-1個元素交換，排序完成。

2.過程：

3.平均時間複雜度：O(n2)

4.python代碼實現：

@staticmethoddef select_sort(arr): for index in range(len(arr)): min_index = index for j in range(index + 1, len(arr)): if arr[j] < arr[min_index]: min_index = j if min_index != index: tmp = arr[index] arr[index] = arr[min_index] arr[min_index] = tmp return arr

插入排序

1.基本思想：

在要排序的一組數中，假定前n-1個數已經排好序，現在將第n個數插到前面的有序數列中，使得這n個數也是排好順序的。如此反覆循環，直到全部排好順序。

2.過程：

3.平均時間複雜度：O(n2)

4.python代碼實現：

@staticmethoddef insert_sort(arr): for index in range(len(arr) - 1): for j in range(index + 1, 0, -1): if arr[j] < arr[j - 1]: tmp = arr[j] arr[j] = arr[j - 1] arr[j - 1] = tmp else: break return arr

希爾排序

1.基本思想：

希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，演算法便終止。

2.過程：

3.平均時間複雜度：O（n*logn）

4.python代碼實現：

def shell_sort(arr): gap = len(arr) while True: gap = int(gap / 2) for arr_index in range(gap): print(arr_index:, arr_index) for element in range(arr_index, len(arr) - 1, gap): print(element:, element) for j in range(element, arr_index, -gap): # print(j, j) if arr[j] < arr[element - gap]: tmp = arr[element - gap] arr[element - gap] = arr[j] arr[j] = tmp else: break if gap == 1: break return arr

快速排序

1.基本思想：（分治）

先從數列中取出一個數作為key值；

將比這個數小的數全部放在它的左邊，大於或等於它的數全部放在它的右邊；

對左右兩個小數列重複第二步，直至各區間只有1個數。

2.過程

1）初始時 i = 0; j = 9; key=72

從j開始向前找一個比key小的數。當j=8，符合條件，a[0] = a[8] ; i++ ; 將a[8]挖出再填到上一個坑a[0]中。

這樣一個坑a[0]就被搞定了，但又形成了一個新坑a[8]，這怎麼辦了？簡單，再找數字來填a[8]這個坑。

這次從i開始向後找一個大於key的數，當i=3，符合條件，a[8] = a[3] ; j-- ; 將a[3]挖出再填到上一個坑中。

2）此時 i = 3; j = 7; key=72

從j開始向前找，當j=5，符合條件，將a[5]挖出填到上一個坑中，a[3] = a[5]; i++;

從i開始向後找，當i=5時，由於i==j退出。

此時，i = j = 5，而a[5]剛好又是上次挖的坑，因此將key填入a[5]。

3）可以看出a[5]前面的數字都小於它，a[5]後面的數字都大於它。因此再對a[0…4]和a[6…9]這二個子區間重複上述步驟就可以了。

3.平均時間複雜度：O(N*logN)

4.Python代碼實現：

def quick_sort(self, arr, left, right): if left >= right: return key = arr[left] i = left j = right while i < j: while i < j and arr[j] >= key: j -= 1 if i < j: arr[i] = arr[j] i += 1 while i < j and arr[i] < key: i += 1 if i < j: arr[j] = arr[i] j -= 1 arr[i] = key self.quick_sort(arr, left, i - 1) self.quick_sort(arr, i + 1, right) return arr

堆排序

堆排序是利用堆這種數據結構而設計的一種排序演算法，堆排序是一種選擇排序，它的最壞，最好，平均時間複雜度均為O(nlogn)，它也是不穩定排序。首先簡單了解下堆結構。

堆

堆是具有以下性質的完全二叉樹：每個結點的值都大於或等於其左右孩子結點的值，稱為大頂堆；或者每個結點的值都小於或等於其左右孩子結點的值，稱為小頂堆。如下圖：

同時，我們對堆中的結點按層進行編號，將這種邏輯結構映射到數組中就是下面這個樣子

該數組從邏輯上講就是一個堆結構，我們用簡單的公式來描述一下堆的定義就是：

大頂堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小頂堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

堆排序基本思想及步驟

堆排序的基本思想是：將待排序序列構造成一個大頂堆，此時，整個序列的最大值就是堆頂的根節點。將其與末尾元素進行交換，此時末尾就為最大值。然後將剩餘n-1個元素重新構造成一個堆，這樣會得到n個元素的次小值。如此反覆執行，便能得到一個有序序列了。

步驟一 構造初始堆。將給定無序序列構造成一個大頂堆（一般升序採用大頂堆，降序採用小頂堆)。

假設給定無序序列結構如下

1、此時我們從最後一個非葉子結點開始（葉結點自然不用調整，第一個非葉子結點 arr.length/2-1=5/2-1=1，也就是下面的6結點），從左至右，從下至上進行調整。

2、找到第二個非葉節點4，由於[4,9,8]中9元素最大，4和9交換。

這時，交換導致了子根[4,5,6]結構混亂，繼續調整，[4,5,6]中6最大，交換4和6。

步驟二 將堆頂元素與末尾元素進行交換，使末尾元素最大。然後繼續調整堆，再將堆頂元素與末尾元素交換，得到第二大元素。如此反覆進行交換、重建、交換。

3、將堆頂元素9和末尾元素4進行交換

4、重新調整結構，使其繼續滿足堆定義

5、再將堆頂元素8與末尾元素5進行交換，得到第二大元素8.

後續過程，繼續進行調整，交換，如此反覆進行，最終使得整個序列有序

再簡單總結下堆排序的基本思路：

a.將無需序列構建成一個堆，根據升序降序需求選擇大頂堆或小頂堆;

b.將堆頂元素與末尾元素交換，將最大元素"沉"到數組末端;

c.重新調整結構，使其滿足堆定義，然後繼續交換堆頂元素與當前末尾元素，反覆執行調整+交換步驟，直到整個序列有序。

代碼實現：

@staticmethoddef heap_sort(arr): # 調整大頂堆（僅是調整過程，建立在大頂堆已構建的基礎上） def adjuct_heap(array, index, length): # 先取出當前元素i temp = array[index] # 從i結點的左子結點開始，也就是2i + 1處開始 k = index * 2 + 1 while k < length: # 如果左子結點小於右子結點，k指向右子結點 if k + 1 < length and array[k] < array[k + 1]: k += 1 # 如果子節點大於父節點，將子節點值賦給父節點（不用進行交換） if array[k] > temp: array[index] = array[k] index = k else: break k = 2 * k + 1 # 將temp值放到最終的位置 array[index] = temp # 構建最大堆 for i in range(int(len(arr) / 2 - 1), -1, -1): # 從第一個非葉子節點從下至上，從右至左調整結構 adjuct_heap(arr, i, len(arr)) for j in range(len(arr) - 1, -1, -1): tmp = arr[j] arr[j] = arr[0] arr[0] = tmp adjuct_heap(arr, 0, j) return arr

歸併排序

歸併排序（MERGE-SORT）是利用歸併的思想實現的排序方法，該演算法採用經典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然後遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)。

可以看到這種結構很像一棵完全二叉樹，本文的歸併排序我們採用遞歸去實現（也可採用迭代的方式去實現）。分階段可以理解為就是遞歸拆分子序列的過程，遞歸深度為log2n。

合併相鄰有序子序列

來看看治階段，我們需要將兩個已經有序的子序列合併成一個有序序列，比如上圖中的最後一次合併，要將[4,5,7,8]和[1,2,3,6]兩個已經有序的子序列，合併為最終序列[1,2,3,4,5,6,7,8]，來看下實現步驟。

Python代碼：

def merge_sort(self, lists): def merge(left, right): i, j = 0, 0 result = [] while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[I]) i += 1 else: result.append(right[j]) j += 1 result += left[I:] result += right[j:] return result # 歸併排序 if len(lists) <= 1: return lists num = int(len(lists) / 2) left = self.merge_sort(lists[:num]) right = self.merge_sort(lists[num:]) return merge(left, right)

基數排序

不需要直接對元素進行相互比較，也不需要將元素相互交換，你需要做的就是對元素進行「分類」。這也是基數排序的魅力所在，基數排序可以理解成是建立在「計數排序」的基礎之上的一種排序演算法。在實際項目中，如果對效率有所要求，而不太關心空間的使用時，我會選擇用計數排序（當然還有一些其他的條件），或是一些計數排序的變形。

基數排序（radix sort）屬於「分配式排序」（distribution sort），又稱「桶子法」（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些「桶」中，藉以達到排序的作用，基數排序法是屬於穩定性的排序，其時間複雜度為O (nlog(r)m)，其中r為所採取的基數，而m為堆數，在某些時候，基數排序法的效率高於其它的穩定性排序法。

如果我們的無序是 T = [ 2314, 5428, 373, 2222, 17 ]，那麼其排序的過程就如下兩幅所示。

上面這幅圖，或許你已經在其他的博客里見到過。這是一個很好的引導跟說明。在基數排序里，我們需要一個很大的二維數組，二維數組的大小是 （10 * n）。10 代表的是我們每個元素的每一位都有 10 種可能，也就是 10 進位數。在上圖中，我們是以每個數的個位來代表這個數，於是，5428 就被填充到了第 8 個桶中了。下次再進行填充的時候，就是以十位進行填充，比如 5428 在此時，就會選擇以 2 來代表它。

基數排序過程圖-1

基數排序過程圖-2

python代碼：

@staticmethoddef radix_sort(lists, radix=10): # k = int(math.ceil(math.log(max(lists), radix))) k = radix bucket = [[] for i in range(radix)] for i in range(k): for j in lists: bucket[int(j / (radix ** (i - 1)) % (radix))].append(j) # bucket[int(j % (radix))].append(j) del lists[:] for z in bucket: lists += z del z[:] print(lists) return lists

參考鏈接：