這篇文章主要介紹了Python中排序算法有哪些，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。
冒泡排序（英語：Bubble Sort）是一種簡單的排序算法。它重復地遍歷要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。遍歷數(shù)列的工作是重復地進行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
冒泡排序算法的運作如下：
比較相鄰的元素。如果第一個比第二個大（升序），就交換他們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會是大的數(shù)。
針對所有的元素重復以上的步驟，除了最后一個。
持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。
交換過程圖示(第一次)：
那么我們需要進行n-1次冒泡過程，每次對應的比較次數(shù)如下圖所示：
def bubble_sort(alist): for j in range(len(alist)-1,0,-1): # j表示每次遍歷需要比較的次數(shù)，是逐漸減小的 for i in range(j): if alist[i] > alist[i+1]: alist[i], alist[i+1] = alist[i+1], alist[i] li = [54,26,93,17,77,31,44,55,20] bubble_sort(li) print(li)時間復雜度
最優(yōu)時間復雜度：O(n) （表示遍歷一次發(fā)現(xiàn)沒有任何可以交換的元素，排序結(jié)束。）
最壞時間復雜度：O(n2)
穩(wěn)定性：穩(wěn)定
效果：
選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
選擇排序的主要優(yōu)點與數(shù)據(jù)移動有關。如果某個元素位于正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當中至少有一個將被移到其最終位置上，因此對n個元素的表進行排序總共進行至多n-1次交換。在所有的完全依靠交換去移動元素的排序方法中，選擇排序?qū)儆诜浅：玫囊环N。
選擇排序分析排序過程：
紅色表示當前最小值，黃色表示已排序序列，藍色表示當前位置。
def selection_sort(alist): n = len(alist) # 需要進行n-1次選擇操作 for i in range(n-1): # 記錄最小位置 min_index = i # 從i+1位置到末尾選擇出最小數(shù)據(jù) for j in range(i+1, n): if alist[j] < alist[min_index]: min_index = j # 如果選擇出的數(shù)據(jù)不在正確位置，進行交換 if min_index != i: alist[i], alist[min_index] = alist[min_index], alist[i] alist = [54,226,93,17,77,31,44,55,20] selection_sort(alist) print(alist)時間復雜度
最優(yōu)時間復雜度：O(n2)
最壞時間復雜度：O(n2)
穩(wěn)定性：不穩(wěn)定（考慮升序每次選擇大的情況）
插入排序插入排序（英語：Insertion Sort）是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應位置并插入。插入排序在實現(xiàn)上，在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。
插入排序分析
def insert_sort(alist): # 從第二個位置，即下標為1的元素開始向前插入 for i in range(1, len(alist)): # 從第i個元素開始向前比較，如果小于前一個元素，交換位置 for j in range(i, 0, -1): if alist[j] < alist[j-1]: alist[j], alist[j-1] = alist[j-1], alist[j] alist = [54,26,93,17,77,31,44,55,20] insert_sort(alist) print(alist)時間復雜度
最優(yōu)時間復雜度：O(n) （升序排列，序列已經(jīng)處于升序狀態(tài)）
最壞時間復雜度：O(n2)
穩(wěn)定性：穩(wěn)定
快速排序（英語：Quicksort），又稱劃分交換排序（partition-exchange sort），通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。
步驟為：
從數(shù)列中挑出一個元素，稱為"基準"（pivot），
重新排序數(shù)列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)結(jié)束之后，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作。
遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序。
遞歸的最底部情形，是數(shù)列的大小是零或一，也就是永遠都已經(jīng)被排序好了。雖然一直遞歸下去，但是這個算法總會結(jié)束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。
def quick_sort(alist, start, end): """快速排序""" # 遞歸的退出條件 if start >= end: return # 設定起始元素為要尋找位置的基準元素 mid = alist[start] # low為序列左邊的由左向右移動的游標 low = start # high為序列右邊的由右向左移動的游標 high = end while low < high: # 如果low與high未重合，high指向的元素不比基準元素小，則high向左移動 while low < high and alist[high] >= mid: high -= 1 # 將high指向的元素放到low的位置上 alist[low] = alist[high] # 如果low與high未重合，low指向的元素比基準元素小，則low向右移動 while low < high and alist[low] < mid: low += 1 # 將low指向的元素放到high的位置上 alist[high] = alist[low] # 退出循環(huán)后，low與high重合，此時所指位置為基準元素的正確位置 # 將基準元素放到該位置 alist[low] = mid # 對基準元素左邊的子序列進行快速排序 quick_sort(alist, start, low-1) # 對基準元素右邊的子序列進行快速排序 quick_sort(alist, low+1, end) alist = [54,26,93,17,77,31,44,55,20] quick_sort(alist,0,len(alist)-1) print(alist)時間復雜度
最優(yōu)時間復雜度：O(nlogn)
最壞時間復雜度：O(n2)
穩(wěn)定性：不穩(wěn)定
從一開始快速排序平均需要花費O(n log n)時間的描述并不明顯。但是不難觀察到的是分區(qū)運算，數(shù)組的元素都會在每次循環(huán)中走訪過一次，使用O(n)的時間。在使用結(jié)合（concatenation）的版本中，這項運算也是O(n)。
在最好的情況，每次我們運行一次分區(qū)，我們會把一個數(shù)列分為兩個幾近相等的片段。這個意思就是每次遞歸調(diào)用處理一半大小的數(shù)列。因此，在到達大小為一的數(shù)列前，我們只要作log n次嵌套的調(diào)用。這個意思就是調(diào)用樹的深度是O(log n)。但是在同一層次結(jié)構的兩個程序調(diào)用中，不會處理到原來數(shù)列的相同部分；因此，程序調(diào)用的每一層次結(jié)構總共全部僅需要O(n)的時間（每個調(diào)用有某些共同的額外耗費，但是因為在每一層次結(jié)構僅僅只有O(n)個調(diào)用，這些被歸納在O(n)系數(shù)中）。結(jié)果是這個算法僅需使用O(n log n)時間。
快速排序演示
希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩(wěn)定排序算法。該方法因DL．Shell于1959年提出而得名。 希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。
希爾排序過程希爾排序的基本思想是：將數(shù)組列在一個表中并對列分別進行插入排序，重復這過程，不過每次用更長的列（步長更長了，列數(shù)更少了）來進行。最后整個表就只有一列了。將數(shù)組轉(zhuǎn)換至表是為了更好地理解這算法，算法本身還是使用數(shù)組進行排序。
例如，假設有這樣一組數(shù)[ 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
將上述四行數(shù)字，依序接在一起時我們得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。這時10已經(jīng)移至正確位置了，然后再以3為步長進行排序：
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后變?yōu)椋?/p>
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步長進行排序（此時就是簡單的插入排序了）
希爾排序的分析
def shell_sort(alist): n = len(alist) # 初始步長 gap = n / 2 while gap > 0: # 按步長進行插入排序 for i in range(gap, n): j = i # 插入排序 while j>=gap and alist[j-gap] > alist[j]: alist[j-gap], alist[j] = alist[j], alist[j-gap] j -= gap # 得到新的步長 gap = gap / 2 alist = [54,26,93,17,77,31,44,55,20] shell_sort(alist) print(alist)
時間復雜度
最優(yōu)時間復雜度：根據(jù)步長序列的不同而不同
最壞時間復雜度：O(n2)
穩(wěn)定想：不穩(wěn)定
歸并排序是采用分治法的一個非常典型的應用。歸并排序的思想就是先遞歸分解數(shù)組，再合并數(shù)組。
將數(shù)組分解最小之后，然后合并兩個有序數(shù)組，基本思路是比較兩個數(shù)組的最前面的數(shù)，誰小就先取誰，取了后相應的指針就往后移一位。然后再比較，直至一個數(shù)組為空，最后把另一個數(shù)組的剩余部分復制過來即可。
歸并排序的分析
重慶分公司
重慶分公司
