python實(shí)現(xiàn)常見(jiàn)排序算法

快速排序

思想：取出第一個(gè)元素把它放到序列的中間某一個(gè)正確位置，以它進(jìn)行分割成左邊和右邊，再分別對(duì)左邊和右邊進(jìn)行取元素分割（遞歸）

遞歸實(shí)現(xiàn)

def quicksort(array):if len(array) < 2: # 遞歸終止條件：數(shù)組少于2則是一個(gè)元素或空元素?zé)o需排序return arrayelse:mid = array[0] # 先確定一個(gè)中間點(diǎn)less = [i for i in array[1:] if i <= mid] # 生成一個(gè)列表的元素全部小于等于中間基準(zhǔn)點(diǎn)more = [i for i in array[1:] if i > mid] # 生成一個(gè)列表的元素全部大于中間基準(zhǔn)點(diǎn)return quicksort(less) + [mid] + quicksort(more) # 列表拼接，左邊繼續(xù)調(diào)用自身排序，右邊同理#驗(yàn)證結(jié)果 print(quicksort([1, 4, 2, 6, 4, 5, 8, 3])) #===>[1, 2, 3, 4, 4, 5, 6, 8]

時(shí)間復(fù)雜度

• 最優(yōu)時(shí)間復(fù)雜度：O(nlogn)
• 最壞時(shí)間復(fù)雜度：O(n*n) ==>深度最壞的n，單層是n，所以n*n
• 穩(wěn)定性：不穩(wěn)定

對(duì)O(nlogn)的類(lèi)比通俗理解：
遞歸調(diào)用函數(shù)可以理解為二叉樹(shù)，調(diào)用樹(shù)的深度是O(log n)，也就是要切分logn次，而調(diào)用的每一層次結(jié)構(gòu)總共全部?jī)H需要O(n)的時(shí)間，所以二者相乘得O(nlogn)，我這里說(shuō)的調(diào)用樹(shù)其實(shí)是調(diào)用棧后面也會(huì)詳細(xì)說(shuō)道快速排序的時(shí)間復(fù)雜度。
在最好的情況，每次我們運(yùn)行一次分區(qū)，我們會(huì)把一個(gè)數(shù)列分為兩個(gè)幾近相等的片段。這個(gè)意思就是每次遞歸調(diào)用處理一半大小的數(shù)列。

選擇排序

思想： 假設(shè)最后一個(gè)元素是最大值，現(xiàn)在要從左到右（除了最后一個(gè)）依次與最大值進(jìn)行比較，如果大于最大值就將兩個(gè)位置進(jìn)行交換。
代碼實(shí)現(xiàn)

def selection_sort(array):for i in range(len(array)-1,0,-1): #產(chǎn)生[n-1,n-2,...2,1]for j in range(i):if array[j] > array[i]:array[j], array[i] = array[i], array[j]return array

時(shí)間復(fù)雜度

• 最優(yōu)時(shí)間復(fù)雜度：O(n*n)
• 最壞時(shí)間復(fù)雜度：O(n*n) ==>深度最壞的n，單層是n，所以n*n
• 穩(wěn)定性：不穩(wěn)定

冒泡排序

思想：所謂冒泡，就是將元素兩兩之間進(jìn)行比較，誰(shuí)大就往后移動(dòng)，直到將最大的元素排到最后面，接著再循環(huán)一趟，從頭開(kāi)始進(jìn)行兩兩比較，而上一趟已經(jīng)排好的那個(gè)元素就不用進(jìn)行比較了。
一級(jí)優(yōu)化實(shí)現(xiàn)
考慮整數(shù)數(shù)組就是有序的特殊情況，設(shè)定一個(gè)變量為False，如果元素之間交換了位置，將變量重新賦值為T(mén)rue,最后再判斷，在一次循環(huán)結(jié)束后，變量如果還是為False，則break退出循環(huán)，結(jié)束排序。

def bubble_sort(array):for i in range(len(array) - 1): # 外層循環(huán)n次保證所有數(shù)都在正確的位置上flag = False # 標(biāo)識(shí)for j in range(len(array) - 1 - i): #內(nèi)層循環(huán)一次代表最后一個(gè)數(shù)就是最大的if array[j] > array[j + 1]:array[j], array[j + 1] = array[j + 1], array[j]flag = True # 只要需要進(jìn)行交換，則進(jìn)入循環(huán)改為T(mén)rueif not flag: #如果沒(méi)進(jìn)入循環(huán)體說(shuō)明原來(lái)的數(shù)據(jù)是有序的break # 直接跳出循環(huán)return array

二級(jí)優(yōu)化實(shí)現(xiàn)
上面這種寫(xiě)法還有一個(gè)問(wèn)題，就是每次都是從左邊到右邊進(jìn)行比較，這樣效率不高，你要考慮當(dāng)最大值和最小值分別在兩端的情況。寫(xiě)成雙向排序提高效率，即當(dāng)一次從左向右的排序比較結(jié)束后，立馬從右向左來(lái)一次排序比較。

def bubble_sort(array):for i in range(len(array) - 1):flag = Falsefor j in range(len(array) - 1 - i):if array[j] > array[j + 1]:array[j], array[j + 1] = array[j + 1], array[j]flag = Trueif flag: # 上個(gè)循環(huán)體循環(huán)一次保證最后一個(gè)數(shù)是最大的flag = False for j in range(len(array) - 2 - i, 0, -1): # 從倒數(shù)第二個(gè)數(shù)開(kāi)始，從后往前再浮動(dòng)比較一下if array[j - 1] > array[j]:array[j], array[j - 1] = array[j - 1], array[j]flag = Trueif not flag:breakreturn array

時(shí)間復(fù)雜度

• 最優(yōu)時(shí)間復(fù)雜度：O(n) ==> 已經(jīng)是有序的了
• 最壞時(shí)間復(fù)雜度：O(n*n)
• 穩(wěn)定性：穩(wěn)定==>每次判斷如果相等，那就不交換，位置不變

插入排序

思想：認(rèn)定第一個(gè)元素是有序，取出第二個(gè)元素進(jìn)行判斷插入到左邊的正確位置上,這是一個(gè)內(nèi)循環(huán)，外循環(huán)遍歷不包括第一個(gè)元素的下標(biāo)進(jìn)行重復(fù)操作。

def insert_sort(array):for i in range(1, len(array)): j = i # 從第二個(gè)元素開(kāi)始while j > 0 :if array[j-1] > array[j]:array[j-1], array[j] = array[j], array[j-1]j -= 1else: # 如果操作就是有序序列，每次都執(zhí)行else退出循環(huán)體,提升效率break

時(shí)間復(fù)雜度

• 最優(yōu)時(shí)間復(fù)雜度：O(n)
• 最壞時(shí)間復(fù)雜度：O(n*n)
• 穩(wěn)定性：穩(wěn)定==> 如果數(shù)值相等，在代碼中對(duì)=不進(jìn)行處理，所以也不交換位置保證原來(lái)的位置順序

歸并排序：

思路：將數(shù)組拆分成一個(gè)一個(gè)的小數(shù)組，然后進(jìn)行臨近合并，合并的時(shí)候進(jìn)行判斷排序
遞歸實(shí)現(xiàn)

def merge(left, right):"""合并排序"""L, R = 0, 0slist = []while L < len(left) and R < len(right):if left[L] <= right[R]:slist.append(left[L])L += 1else:slist.append(right[R])R += 1# 循環(huán)體結(jié)束，對(duì)稱(chēng)的數(shù)據(jù)都比較完了，可能出現(xiàn)不對(duì)稱(chēng)的話，將剩余數(shù)據(jù)追加到slist中slist += left[L:]slist += right[R:]return slist def merge_sort(arr):if len(arr) < 2:return arr# 開(kāi)始遞歸拆分?jǐn)?shù)組mid = len(arr) // 2left_list = merge_sort(arr[:mid])right_list = merge_sort(arr[mid:])# 開(kāi)始合并return merge(left_list,right_list)

時(shí)間復(fù)雜度

• 最優(yōu)時(shí)間復(fù)雜度：O(nlogn)
• 最壞時(shí)間復(fù)雜度：O(nlogn)
• 穩(wěn)定性：穩(wěn)定

排序算法時(shí)空復(fù)雜度總結(jié)

這里只說(shuō)一下快速排序和歸并排序
快速排序我們遞歸調(diào)用棧的思想來(lái)理解，結(jié)合我后一篇文章學(xué)習(xí)遞歸來(lái)理解。

最好的情況， 快速排序的每次選的中間值mid都是真正的中間值，調(diào)用棧的高度（函數(shù)調(diào)用層數(shù)）就為O(logn)，而每層需要時(shí)間為O(n)，因此整個(gè)算法需要的時(shí)間為O(n) * O(log n) = O(n log n)。這就是最佳情況。

最糟糕情況， 有O(n)層，因此該算法的運(yùn)行時(shí)間為O(n) * O(n) = O(n2)。

最佳情況也是平均情況。 只要你每次都隨機(jī)地選擇一個(gè)數(shù)組元素作為基準(zhǔn)值，快速排序的平均運(yùn)行時(shí)間就將為O(n log n)。快速排序是最快的排序算法之一，也是D&C（分而治之）典范。

這里需要記住的是，快速排序一般情況下是比歸并排序的速度要快

總結(jié)

以上是生活随笔為你收集整理的python实现常见排序算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。