排序演算法最強總結及其程式碼實現(PythonJava)
前言
此為知乎之前文章的重置版,整理和消除了部分錯誤,適合收藏用。
本文總結了常用的全部排序演算法,內容包括:
排序演算法的定義和思路,動畫演示
排序演算法的程式碼實現:Python和Java,包括實現中需要注意的細節
排序演算法效能分析:時間空間複雜度分析,穩定排序演算法背誦口訣等
不同排序演算法最佳使用場景
此文乾貨頗多,煩請收藏後慢慢研讀。
面試知識點複習手冊
此文屬於知識點複習手冊專欄內容,你還可以
透過以下兩種途徑檢視全複習手冊文章導航
:
關注我的公眾號:Rude3Knife 點選公眾號下方:技術推文——面試衝刺
全複習手冊文章導航(CSDN)
-----正文開始-----
演算法效能分析
圖中糾正:歸併排序空間複雜度應該是O(n),快排是O(logn)-O(n)
穩定性定義:
假定在待排序的記錄序列中,存在多個具有相同的關鍵字的記錄,若經過排序,這些記錄的相對次序保持不變,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序後的序列中,r[i]仍在r[j]之前,則稱這種排序演算法是穩定的;否則稱為不穩定的。
例如,對於如下氣泡排序演算法,原本是穩定的排序演算法,如果將記錄交換的條件改成r[j]>=r[j+1],則兩個相等的記錄就會交換位置,從而變成不穩定的演算法。
再如,快速排序原本是不穩定的排序方法,但若待排序記錄中只有一組具有相同關鍵碼的記錄,而選擇的軸值恰好是這組相同關鍵碼中的一個,此時的快速排序就是穩定的。
只需記住一句話(快些選一堆美女一起玩兒)是不穩定的,其他都是穩定的。
補充效能圖:
不同情況下的合適排序方法
初始資料越無序,快速排序越好。
已經基本有序時,用直接插入排序最快。
在隨機情況下,快速排序是最佳選擇。
既要節省空間,又要有較快的排序速度,堆排序是最佳選擇,其不足之處是建堆時需要消耗較多時間。
若希望排序是穩定的,且有較快的排序速度,則可選用2路歸併排序,其缺點需要較大的輔助空間分配。
演算法實現
基於比較的排序演算法
氣泡排序
思路:
氣泡排序的原理非常簡單,它重複地走訪過要排序的數列,一次比較兩個元素,如果他們的順序錯誤就把他們交換過來。
步驟:
比較相鄰的元素。如果第一個比第二個大,就交換他們兩個。
對第0個到第n-1個數據做同樣的工作。這時,最大的數就“浮”到了陣列最後的位置上。
針對所有的元素重複以上的步驟,除了最後一個。
持續每次對越來越少的元素重複上面的步驟,直到沒有任何一對數字需要比較。
Python:
def bubble_sort(array):
n = len(array)
for i in range(n): # i從0到n
for j in range(1, n-i): # 1開始,即j-1=0開始
if array[j-1] > array[j]:
array[j-1], array[j] = array[j], array[j-1]
return array
#最佳化1:某一趟遍歷如果沒有資料交換,則說明已經排好序了,因此不用再進行迭代了。
#用一個標記記錄這個狀態即可。
def bubble_sort2(ary):
n = len(ary)
for i in range(n):
flag = 1 #標記
for j in range(1,n-i):
if ary[j-1] > ary[j] :
ary[j-1],ary[j] = ary[j],ary[j-1]
flag = 0
if flag : #全排好序了,直接跳出
break
return ary
#最佳化2:記錄某次遍歷時最後發生資料交換的位置,這個位置之後的資料顯然已經有序了。
# 因此透過記錄最後發生資料交換的位置就可以確定下次迴圈的範圍了。
def bubble_sort3(ary):
n = len(ary)
k = n #k為迴圈的範圍,初始值n
for i in range(n):
flag = 1
for j in range(1,k): #只遍歷到最後交換的位置即可
if ary[j-1] > ary[j] :
ary[j-1],ary[j] = ary[j],ary[j-1]
k = j #記錄最後交換的位置
flag = 0
if flag :
break
return ary
Java:
public void bubble_sort(int [] a) {
int n = a。length;
for(int i=0;i for(int j=1;j if (a[j-1] > a[j]) { int temp = a[j-1]; a[j-1] = a[j]; a[j] = temp; } } } } //兩種最佳化不寫了 選擇排序 思路: 選擇排序無疑是最簡單直觀的排序。它的工作原理如下。 步驟: 在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。 再從剩餘未排序元素中繼續尋找最小(大)元素,然後放到已排序序列的末尾。 以此類推,直到所有元素均排序完畢。 Python: def selection_sort(array): n = len(array) for i in range(n): minIndex = i for j in range(i+1, n): if array[j] < array[minIndex]: minIndex = j array[i], array[minIndex] = array[minIndex], array[i] # 或者使用minNum儲存數值,避免每次都讀array[minIndex],但如果每次都儲存新的minNum,也會有損耗。 def selection_sort(array): n = len(array) for i in range(n): minNum = array[i] minIndex = i for j in range(i+1, n): if array[j] < minNum: minIndex = j minNum = array[j] array[i], array[minIndex] = array[minIndex], array[i] Java: public void selection_sort(int [] a) { int n = a。length; for(int i=0;i int minIndex = i; for(int j=i;j if (a[j] < a[minIndex]) { minIndex = j; } } int temp = a[i]; a[i] = a[minIndex]; a[minIndex] = temp; } } 插入排序 思路: 從左邊第二個數開始,往前遍歷,將大於他的數都往後一個個移位,一旦發現小於等於他的數,就放在那個位置(之前的數已經被移到後面一位了) 插入排序的工作原理是,對於每個未排序資料,在已排序序列中從後向前掃描,找到相應位置並插入。 步驟: 從第一個元素開始,該元素可以認為已經被排序 取出下一個元素,在已經排序的元素序列中從後向前掃描 如果被掃描的元素(已排序)大於新元素,將該元素後移一位 重複步驟3,直到找到已排序的元素小於或者等於新元素的位置 將新元素插入到該位置後 重複步驟2~5 Python: def insert_sort(array): n = len(array) for i in range(1,n): # 從第二個數開始 if array[i-1] > array[i]: # 前面比後面大,需要調整位置 num = array[i] index = i for j in range(i-1, -1, -1): if array[j] > num: array[j+1] = array[j] index = j else: # 找到位置,插入 array[index] = num break Java: public void insert_sort(int [] a) { int n = a。length; for(int i=1;i if (a[i-1] > a[i]) { int num = a[i]; int index = i; for(int j=i-1;j>-1;j——) { if (a[j] > num) { a[j+1] = a[j]; index = j; } else { a[index] = num; break; } } } } } 希爾排序(遞減增量排序演算法,實質是分組插入排序) 思路: 希爾排序的基本思想是:將陣列列在一個表中並對列分別進行插入排序,重複這過程,不過每次用更長的列(步長更長了,列數更少了)來進行。最後整個表就只有一列了。將陣列轉換至表是為了更好地理解這演算法,演算法本身還是使用陣列進行排序。 例如,假設有這樣一組數, [ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ] 如果我們以步長為5開始進行排序,我們可以透過將這列表放在有5列的表中來更好地描述演算法,這樣他們就應該看起來是這樣: 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 然後我們對每列進行排序: 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 將上述四行數字,依序接在一起時我們得到: [ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ] 。這時10已經移至正確位置了,然後再以3為步長進行排序: 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 排序之後變為: 10 14 13 25 23 33 27 25 59 39 65 73 45 94 82 94 最後以1步長進行排序(此時就是簡單的插入排序了)。 具體實現:外面套一個gap,while內做插入排序,並且將gap不斷除2,直到小於0出迴圈 Python: def shell_sort(ary): n = len(ary) gap = round(n/2) # 初始步長 , 用round取整(注意0。5向下取) while gap > 0 : for i in range(gap,n): # 每一列進行插入排序 , 從gap 到 n-1 temp = ary[i] index = i while ( index >= gap and ary[index-gap] > temp ): # 插入排序 ary[index] = ary[index-gap] index = index - gap ary[index] = temp gap = round(gap/2) # 重新設定步長 return ary Java: public void shell_sort(int [] a) { int n = a。length; int gap = n / 2; while (gap > 0) { for (int i=gap;i int temp = a[i]; int j = i; while (j>=gap && a[j-gap] > temp) { a[j] = a[j-gap]; j = j - gap; } a[j] = temp; } gap = gap / 2; } } 歸併排序(遞迴合併) 思路: 拆拆拆到單個數字,合併合併合併 歸併排序是採用分治法的一個非常典型的應用。歸併排序的思想就是先遞迴分解陣列,再合併陣列。 先考慮合併兩個有序陣列,基本思路是比較兩個陣列的最前面的數,誰小就先取誰,取了後相應的指標就往後移一位。然後再比較,直至一個數組為空,最後把另一個數組的剩餘部分複製過來即可。 再考慮遞迴分解,基本思路是將陣列分解成left和right,如果這兩個陣列內部資料是有序的,那麼就可以用上面合併陣列的方法將這兩個數組合並排序。如何讓這兩個陣列內部是有序的?可以再二分,直至分解出的小組只含有一個元素時為止,此時認為該小組內部已有序。然後合併排序相鄰二個小組即可。 Python: def merge_sort(array): # 遞迴 if len(array) <= 1: return array # python每次都是新的陣列,可以用陣列長度小於等於1來判斷 num = len(array) // 2 # py27 3/2和3//2相同,python3 3//2才是地板除 left = merge_sort(array[:num]) right = merge_sort(array[num:]) return merge(left, right) def merge(left, right): # 合併 l,r = 0,0 result = [] while l < len(left) and r < len(right): if left[l] < right[r]: result。append(left[l]) l = l + 1 else: result。append(right[r]) r += 1 # 一邊沒有之後,加上所有的 result += left[l:] result += right[r:] return result Java: //注意:新建的temp長度和原陣列是一樣的,所以額外空間是O(n),temp陣列一開始並未賦值,在合併時慢慢給其填充數值,所以說一共只有一個temp陣列 public void mergeSort(int[] arr) { mergeSort(arr, new int[arr。length], 0, arr。length - 1); } private static void mergeSort(int[] arr, int[] temp, int left, int right) { if (left < right) { // Java則透過左右指標來判斷 int center = (left + right) / 2; mergeSort(arr, temp, left, center); // 左邊 mergeSort(arr, temp, center + 1, right); // 右邊 merge(arr, temp, left, center + 1, right); // 合併兩個有序 } } private static void merge(int[] arr, int[] temp, int leftPos, int rightPos, int rightEnd) { int leftEnd = rightPos - 1; // 左邊結束下標 int tempPos = leftPos; // 從左邊開始算 int numEle = rightEnd - leftPos + 1; // 元素個數 while (leftPos <= leftEnd && rightPos <= rightEnd) { if (arr[leftPos] <= arr[rightPos]) temp[tempPos++] = arr[leftPos++]; else temp[tempPos++] = arr[rightPos++]; } while (leftPos <= leftEnd) { // 左邊如果有剩餘 temp[tempPos++] = arr[leftPos++]; } while (rightPos <= rightEnd) { // 右邊如果有剩餘 temp[tempPos++] = arr[rightPos++]; } // 將temp複製到arr,覆蓋原來這裡的位置 for (int i = 0; i < numEle; i++) { arr[rightEnd] = temp[rightEnd]; rightEnd——; } } 快速排序 快速排序通常明顯比同為Ο(n log n)的其他演算法更快 ,因此常被採用,而且快排採用了分治法的思想,所以在很多筆試面試中能經常看到快排的影子。可見掌握快排的重要性。 快排特點: 每經過一趟快排,軸點元素都必然就位,也就是說,一趟下來至少有關鍵字key節點在其最終位置,所以考察各個選項,看有幾個元素就位即可。 逆序的數列,選擇首位為key,則會退化到O(n^2),可以隨機選擇一個元素作為基準元素。 兩種交換方法: 指標交換法 :youtube影片: https://www。 youtube。com/watch? v=gl_XQHTJ5hY (下圖程式碼實現的方法,並且是兩兩交換,最後將key與left交換) 挖坑填數法 : http:// blog。csdn。net/morewindo ws/article/details/6684558 (key一開始就被 挖坑填寫了別的數 ,我認為第二種是做 牛客網選擇題 時需要掌握的,應為選擇題答案的排序結果通常是按照這種演算法得到的排序結果) 快排最佳化方法: https:// blog。csdn。net/cpcpcp123 /article/details/52739285 選擇基準的方式:三數取中(median-of-three) 舉例:待排序序列為:8 1 4 9 6 3 5 2 7 0 左邊為:8,右邊為0,中間為6。 我們這裡取三個數排序後,中間那個數作為樞軸,則樞軸為6 下圖分別對應第一種和第二種排序的中間結果: Python(指標交換): def quick_sort(ary): return _quick_sort(ary, 0, len(ary)-1) def _quick_sort(ary, left, right): if left >= right: return ary key = ary[left] # 每次都選最左邊為key lp = left rp = right while (lp < rp): while ary[rp] >= key and lp < rp: rp -= 1 while ary[lp] <= key and lp < rp: lp += 1 ary[lp], ary[rp] = ary[rp], ary[lp] ary[left], ary[lp] = ary[lp], ary[left] # 這裡不能用key,是交換陣列內數字 _quick_sort(ary, left, lp-1) _quick_sort(ary, lp+1, right) # 這裡lp, rp永遠是相等的。所以都可以。 return ary Java(指標交換): public void quick_sort(int[] ary) { _quick_sort(ary, 0, ary。length-1); } public void _quick_sort(int[] ary, int left, int right) { if (left < right) { int key = ary[left]; int lp = left; int rp = right; while (lp < rp) { while (ary[rp] >= key && lp < rp ) { rp——; } while (ary[lp] <= key && lp < rp ) { lp++; } int temp = ary[lp]; ary[lp] = ary[rp]; ary[rp] = temp; } int temp = ary[lp]; ary[lp] = ary[left]; ary[left] = temp; _quick_sort(ary, left, lp-1); _quick_sort(ary, rp+1, right); } } Java(挖坑法) 非遞迴形式實現(棧) :和剛才的遞迴實現相比,程式碼的變動僅僅在quickSort方法當中。該方法中引入了一個儲存Map型別元素的棧,用於儲存每一次交換時的起始下標和結束下標。 每一次迴圈,都會讓棧頂元素出棧,進行排序,並且按照基準元素的位置分成左右兩部分,左右兩部分再分別入棧。當棧為空時,說明排序已經完畢,退出迴圈。 該方法實現程式碼請參考程式設計師小灰: https:// mp。weixin。qq。com/s? __biz=MzIxMjE5MTE1Nw==&mid=2653195042&idx=1&sn=2b0915cd2298be9f2163cc90a3d464da&chksm=8c99f9f8bbee70eef627d0f5e5b80a604221abb3a1b5617b397fa178582dcb063c9fb6f904b3&mpshare=1&scene=1&srcid=0813k35KHoSO42jGGrMx5oUA#rd 堆排序 參考: http:// blog。csdn。net/minxihou/ article/details/51850001 https://www。 2cto。com/kf/201609/5493 35。html 例題:相當幫助理解 https://www。 nowcoder。com/test/quest ion/done?tid=14276624&qid=56294#summary 思路: 父節點i的左子節點在位置(2*i+1) 父節點i的右子節點在位置(2*i+2) 子節點i的父節點在位置floor((i-1)/2) 堆排序構建堆的時間複雜度是N,而重調堆的時間複雜度是logN 堆可以分為大根堆和小根堆,這裡用最大堆的情況來定義操作: (1)最大堆調整(MAX_Heapify): 將堆的末端子節點作調整,使得子節點永遠小於父節點。這是核心步驟,在建堆和堆排序都會用到。比較i的根節點和與其所對應i的孩子節點的值。當i根節點的值比左孩子節點的值要小的時候,就把i根節點和左孩子節點所對應的值交換,當i根節點的值比右孩子的節點所對應的值要小的時候,就把i根節點和右孩子節點所對應的值交換。然後再呼叫堆調整這個過程,可見這是一個遞迴的過程。 (2)建立最大堆(Build_Max_Heap): 將堆所有資料重新排序。建堆的過程其實就是不斷做最大堆調整的過程,從len/2出開始調整,一直比到第一個節點。 (3)堆排序(HeapSort): 移除位在第一個資料的根節點,並做最大堆調整的遞迴運算。堆排序是利用建堆和堆調整來進行的。首先先建堆,然後將堆的根節點選出與最後一個節點進行交換,然後將前面len-1個節點繼續做堆調整的過程。直到將所有的節點取出,對於n個數我們只需要做n-1次操作。堆是用順序表儲存的的程式碼可以先看: http:// blog。51cto。com/ahalei/1 427156 就能理解程式碼中的操作 注意: 從小到大排序的時候不建立最小堆而建立最大堆。最大堆建立好後,最大的元素在h[ 1]。因為我們的需求是從小到大排序,希望最大的放在最後。 因此我們將h[ 1]和h[ n]交換,此時h[ n]就是陣列中的最大的元素。 請注意,交換後還需將h[1]向下調整以保持堆的特性。OK現在最大的元素已經歸位,需要將堆的大小減1即n——,然後再將h[1]和h[ n]交換,並將h[1]向下調整。 如此反覆,直到堆的大小變成1為止。此時陣列h中的數就已經是排序好的了。 程式碼如下: Python: def MAX_Heapify(heap, HeapSize, root): # 在堆中做結構調整使得父節點的值大於子節點 left = 2 * root + 1 right = left + 1 larger = root if left < HeapSize and heap[larger] < heap[left]: larger = left if right < HeapSize and heap[larger] < heap[right]: # 確定到底和左還是右節點換,先判斷做節點 larger = right if larger != root: # 如果做了堆調整:則larger的值等於左節點或者右節點的,這個時候做對調值操作 heap[larger],heap[root] = heap[root],heap[larger] MAX_Heapify(heap, HeapSize, larger) # 從頂端遞迴往下調整,用larger是因為larger是陣列索引,並且已經在比較時候更新過,而root沒有更新過! def Build_MAX_Heap(heap): # 構造一個堆,將堆中所有資料重新排序 HeapSize = len(heap) for i in range(((HeapSize-1)-1)//2,-1,-1): # 從後往前出數(z最後一個節點的父節點) ‘//’ got integer MAX_Heapify(heap,HeapSize,i) # 這裡堆的大小是固定,root是i逐步減小 def HeapSort(heap): # 將根節點取出與最後一位做對調,對前面len-1個節點繼續進行對調整過程。 Build_MAX_Heap(heap) for i in range(len(heap)-1,-1,-1): heap[0],heap[i] = heap[i],heap[0] MAX_Heapify(heap, i, 0) # 這裡堆的大小是逐步縮小,root永遠是0 return heap Java: 有空補 非基於比較的排序演算法 基於比較的排序演算法是不能突破O(NlogN)的。簡單證明如下: N個數有N!個可能的排列情況,也就是說基於比較的排序演算法的判定樹有N!個葉子結點,比較次數至少為log(N!)=O(NlogN)(斯特林公式)。 計數排序 計數排序在輸入n個0到k之間的整數時( 可以從a到b,不用非要從0開始,程式碼可以實現 ), 時間複雜度最好情況下為O(n+k),最壞情況下為O(n+k),平均情況為O(n+k),空間複雜度為O(n+k) 演算法的步驟如下: 1。找出待排序的陣列中最大和最小的元素 2。統計陣列中每個值為i的元素出現的次數,存入陣列C的第i項 3。對所有的計數累加(從C中的第一個元素開始,每一項和前一項相加) 4。反向填充目標陣列:將每個元素i放在新陣列的第C(i)項,每放一個元素就將C(i)減去1 當k不是很大時,這是一個很有效的線性排序演算法。更重要的是,它是一種 穩定排序演算法 ,即排序後的相同值的元素原有的相對位置不會發生改變(表現在Order上),這是計數排序很重要的一個性質,就是根據這個性質,我們才能把它應用到基數排序。 # -*- coding:utf-8 -*- def count_sort(ary): max=min=0 # min和max應該用sys。maxint for i in ary: if i < min: min = i if i > max: max = i count = [0] * (max - min +1) for index in ary: count[index-min]+=1 index=0 for a in range(max-min+1): for c in range(count[a]): # 重點:有多少個就for迴圈多少次 ary[index]=a+min index+=1 return ary 桶排序 假如待排序列K= {49、 38 、 35、 97 、 76、 73 、 27、 49 }。這些資料全部在1—100之間。因此我們定製10個桶,然後確定對映函式f(k)=k/10。則第一個關鍵字49將定位到第4個桶中(49/10=4)。依次將所有關鍵字全部堆入桶中,並在每個非空的桶中進行快速排序。 因此,我們需要儘量做到下面兩點: (1) 對映函式f(k)能夠將N個數據平均的分配到M個桶中,這樣每個桶就有[N/M]個數據量。 (2) 儘量的增大桶的數量。極限情況下每個桶只能得到一個數據,這樣就完全避開了桶內資料的“比較”排序操作。 當然,做到這一點很不容易,資料量巨大的情況下,f(k)函式會使得桶集合的數量巨大,空間浪費嚴重。這就是一個時間代價和空間代價的權衡問題了。 對於N個待排資料,M個桶,平均每個桶[N/M]個數據的桶排序平均時間複雜度為: O(N)+O(M (N/M) log(N/M))=O(N+N (logN-logM))=O(N+N logN-N*logM) 當N=M時,即極限情況下每個桶只有一個數據時。桶排序的最好效率能夠達到O(N)。 桶排序是穩定的。 基數排序 基數排序的思想就是將待排資料中的每組關鍵字依次進行桶分配。比如下面的待排序列: 278、109、063、930、589、184、505、269、008、083 我們將每個數值的個位,十位,百位分成三個關鍵字: 278 -> k1(個位)=8 ,k2(十位)=7 ,k3=(百位)=2。 然後從最低位個位開始(從最次關鍵字開始),對所有資料的k1關鍵字進行桶分配(因為,每個數字都是 0-9的,因此桶大小為10),再依次輸出桶中的資料得到下面的序列。 930、063、083、184、505、278、008、109、589、269 再對上面的序列接著進行針對k2的桶分配,輸出序列為: 505、008、109、930、063、269、278、083、184、589 最後針對k3的桶分配,輸出序列為: 008、063、083、109、184、269、278、505、589、930 很明顯,基數排序的效能比桶排序要略差。每一次關鍵字的桶分配都需要O(N)的時間複雜度,而且分配之後得到新的關鍵字序列又需要O(N)的時間複雜度。假如待排資料可以分為d個關鍵字,則基數排序的時間複雜度將是O(d*2N) ,當然d要遠遠小於N,因此基本上還是線性級別的。基數排序的空間複雜度為O(N+M),其中M為桶的數量。一般來說N>>M,因此額外空間需要大概N個左右。 但是,對比桶排序,基數排序每次需要的桶的數量並不多。而且基數排序幾乎不需要任何“比較”操作,而桶排序在桶相對較少的情況下,桶內多個數據必須進行基於比較操作的排序。 因此,在實際應用中,基數排序的應用範圍更加廣泛。 參考 穩定性解釋: https:// baike。baidu。com/item/%E 6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E7%A8%B3%E5%AE%9A%E6%80%A7/9763250?fr=aladdin 效能分析與適應場景: http:// blog。csdn。net/p10010/ar ticle/details/49557763 動畫: http:// blog。csdn。net/tobeandno ttobe/article/details/7192953 http://www。 webhek。com/post/compari son-sort。html Python排序總結: http:// wuchong。me/blog/2014/02 /09/algorithm-sort-summary/ Java排序總結: https://www。 cnblogs。com/10158wsj/p/ 6782124。html?utm_source=tuicool&utm_medium=referral -----正文結束-----