排序算法基本原理以及復雜度等知識點可跳轉至該博客了解https://www.cnblogs.com/onepixel/p/7674659.html?，本博客主要對排序算法性能進行對比以及記錄對比過程發(fā)現(xiàn)的問題

1. 插入排序和選擇排序的對比

1.1 插入排序：從列表第一個元素 List[0] 開始每次取出列表一個元素，與該元素的前面元素進行比較，如果前面元素比該元素大，則把前面元素后移，直到前面元素不比該元素大，則插入。

插入排序示例lst = [1,4,2,7,5] ----------------------第1次--------------------- 取出lst[0] = 1; temp = lst[0] 前面沒有元素，結束比較。 lst = [1,4,2,7,5]----------------------第2次--------------------- 取出lst[1] = 4; temp = lst[1] lst[0] 不大于 temp, 不移動。 lst = [1,4,2,7,5]----------------------第3次--------------------- 取出lst[2] = 2; temp = lst[2] lst[1] 大于 temp, lst[1]后移； 此時lst[2] = lst[1], 即lst[2] = 4。 lst[0] 不大于 temp, 不移動。 比較結束，將temp插入到列表中，lst[1] = temp。 lst = [1,2,4,7,5]----------------------第4次--------------------- …… #插入排序示例代碼def insertsort(lst):if lst:if len(lst)<2:return lstL = lst[:]for i in range(1, len(L)): #range()右邊不閉合temp = L[i]j = i-1while j>=0 and L[j] > temp:L[j+1] = L[j]j -= 1if j<i-1:L[j+1] = tempreturn Lelse:return "List can't be none"

?

1.2 選擇排序：從列表第一個元素開始，每一次取一個出來和該列表的后續(xù)元素比較，找到最小值，然后將最小值和列表的取出值對換即可。

選擇排序示例lst = [1,4,2,7,5] ----------------------第1次--------------------- 取出lst[0] = 1; minindex = 0 和lst[1], lst[2], lst[3], lst[4]比較； 沒有比lst[0]更小的值，則minindex=0，不交換，結束 lst = [1,4,2,7,5]----------------------第2次--------------------- 取出lst[1] = 4; minindex=1 和lst[2],lst[3],lst[4]比較； 得到最小值lst[2]的索引為minindex=2; 將lst[1]和lst[minindex]交換，結束。 lst = [1,2,4,7,5]----------------------第3次--------------------- 取出lst[2] = 4; minindex=2 和lst[3],lst[4]比較； 沒有比lst[2]更小的值，則minindex還是等于2，不交換，結束 lst = [1,2,4,7,5]----------------------第4次--------------------- …… def selectsort(lst):if lst:if len(lst)<2:return lstL = lst[:]for i in range(len(L)-1):min = ifor j in range(len(L)-1, i, -1):if L[j] < L[min]:min = jif min != i:temp = L[i]L[i] = L[min]L[min] = tempreturn Lelse:return "List can't be none"

?1.3 插入排序和選擇排序性能對比：我們都知道插入排序和選擇排序的平均時間復雜度都是，而且選擇排序每一輪循環(huán)都要遍歷整個列表找出最小值，所以平均時間復雜度還是。但是插入排序是和前面的數(shù)據(jù)排序，把比它小的數(shù)據(jù)往后移，這就值得我們注意了。如果列表本身有序程度較高，那么根本就不需要怎么移動，如[1,2,3,4]，所以，時間復雜度最好為。具體排序性能如下圖。列表元素無序時，且長度為10,000，則選擇排序比插入排序快一些，但處于同一數(shù)量級，區(qū)別不大。而列表元素有序時，插入排序只需0.002秒，而選擇排序所用時間和處理無序列表時間差不多，都需要2.7秒左右。當我把列表長度拓展至40,000時，運行時間如下圖。

? ? ??

1.4 插入排序和選擇排序總結：根據(jù)以上分析以及性能對比，對于隨機序列，選擇排序性能稍好，不管什么情況下，時間復雜度均為，此時插入排序與之處于同一數(shù)量級；對于有序程度較高的序列，插入排序有驚人的排序性能，復雜度可以為，而且插入排序是依次比較，所以是穩(wěn)定性排序算法（列表中相同兩個元素不會因為排序算法而更換位置）。所以可以根據(jù)相應場景選擇相應排序算法。

?

2. 歸并排序和快速排序的對比

2.1 歸并排序：將列表一分為二，再將兩個子列表一分為二得到四個子列表，遞歸劃分，最終得到單個元素的列表不再劃分。此時再將子列表逐層合并，得到排序完成的列表，流程及代碼如下。由二叉樹知識可知，一n個元素的列表，最終劃分為單個元素，那么總的層數(shù)有層，而每一層合并都需對n個元素進行n/2次比較，加上賦值操作，所以每一層的時間復雜度是，總共有，那么總的時間復雜度，而且不管什么情況下，復雜度均為。

def merge(left, right):result = []while len(left) and len(right):if left[0] <= right[0]:result.append(left.pop(0))else:result.append(right.pop(0))if len(left):result += leftelif len(right):result += right return resultdef mergesort(lst): if len(lst)<2:return lstmiddle = len(lst)//2left = lst[:middle]right = lst[middle:]return merge(mergesort(left), mergesort(right))

?2.2 快速排序：選取關鍵字key（推薦取列表中間值，原因見附錄），每一輪從列表末端判斷是否有元素小于索引key的值，若有，更換值，并更新key。然后從列表前端判斷是否有元素大于索引key的值，若有，更換值，并更新索引key，直至列表前端掃描索引和末端掃描索引重合，此時，索引key的左端都是比索引key的列表值小，索引key的右端都是比索引key的列表值大，分別對索引key的左右兩端采取遞歸操作即可排序，排序示例如下，方便理解。平均情況下，key靠近整個列表的中值，那么每次掃描整個列表，然后將小于key放置左端，大于key放置右端，則依次劃分，相當于歸并排序的劃分，層數(shù)接近層，每一層都要對n個元素進行比較，所以平均復雜度為，但是當選取的key遠離列表中值，那么以key為界，不能均分列表為兩個子列表，比如比key小的列表為一個數(shù)，那么比key大的列表仍有n-2個數(shù)，相當于沒有二分，復雜度和冒泡算法接近，退化為。

快速排序假設序列{xi}：5，3，7，6，4，1。--------------------------------------------第1次------------------------------------------ 此時，關鍵字索引為列表長度除以2，則key=3，則參考值ref=6，前端head的索引下標i=0，后端tail的索引下標j=5，從后往前找，第一個比6小的數(shù)是x5=1，因此序列為：5，3，7，1，4，6。--------------------------------------------第2次------------------------------------------ 更新i=0，j=4，key=5從前往后找，第一個比ref大的數(shù)是x2=7，因此序列為：5，3，6，1，4，7。--------------------------------------------第3次------------------------------------------ 更新i=3，j=4，key=2從j往前找，第一個比ref小的數(shù)是x4=4，因此：5，3，4，1，6，7。--------------------------------------------第4次------------------------------------------ 更新i=3，j=3，key=4, ref成為一條分界線，它之前的數(shù)都比它小，之后的數(shù)都比它大，對于前后兩部分數(shù)，采用同樣的方法來排序（遞歸）。 def quicksort1(Lp):if len(Lp)<2:return LpL = Lp[:]key = len(L)//2left = -1right = len(L)while left<right:right -= 1 #下一輪開始都需要在上輪的值移動一步，不然又重復計算while right>key and L[right]>=L[key]:right -= 1if right>key: #滿足條件說明while循環(huán)是因為L[right]<L[key]而跳出，此時需要更新keyL[right], L[key] = L[key], L[right]key = rightleft += 1 #下一輪開始都需要在上輪的值移動一步，不然又重復計算while left<key and L[left]<=L[key]:left += 1if key>left: #滿足條件說明while循環(huán)是因為L[left]>L[key]而跳出，此時需要更新keyL[left], L[key] = L[key], L[left]key = leftreturn quicksort1(L[:key]) + [L[key]] + quicksort1(L[key+1:])

2.3 歸并排序、快速排序和插入排序、選擇排序的對比： 由下圖運行過程可知，歸并排序和快速排序的性能比插入排序和選擇排序好的多。

? ?? ? ?

2.4?歸并排序和快速排序的對比： 由上述分析可知，快速排序會因為極端情況而復雜度上升，如果key值不夠合適的話，會導致快速排序退化成冒泡排序，從而時間復雜度上升為。而歸并排序的性能較為穩(wěn)定，沒有大的區(qū)別。如下圖，可知快速排序對于有序列表處理效果良好。

? ? ??

由上圖可知，歸并排序速度沒有快速排序快，博主了解到的原因是由于歸并排序對內存的操作多于快速排序，那么為了探究是否該原因，博主將歸并排序中比較合并列表的部分代碼進行更改，然后修改代碼如下。

原先合并比較函數(shù) def merge(left, right):result = []while len(left) and len(right):if left[0] <= right[0]:result.append(left.pop(0))else:result.append(right.pop(0))if len(left):result += leftelif len(right):result += right return result修改后合并比較函數(shù)，減少內存操作，仍然進行l(wèi)eft列表和right列表比較，但不將比較結果保存至result列表中，result直接返回left和right中元素。 def mergeupdate(left, right):ll = left[:]rr = right[:]result = []while len(left) and len(right):if left[0] <= right[0]:left.pop(0)else:right.pop(0)if len(ll):result += llelif len(rr):result += rrreturn result

代碼運行效果如下?

? ? ?

由圖可以得到兩點，①：對于有序程序較高的列表，快速排序運行效果比歸并排序快得多，相差一個數(shù)量級，這也可從代碼分析得到快速排序對有序列表的優(yōu)勢。②：對于無序列表快速排序比歸并排序運行快2-3倍左右，而且通過修改歸并排序的內存操作代碼以及實驗數(shù)據(jù)，可以驗證：歸并排序比快速排序慢的原因和內存操作有關。說明內存操作比較耗時間。

?

?

附錄：

1. 快排的關鍵字key選擇（盡量選取中間值）

key如果選兩端的話，比如，設key=0此時若處理的列表為完全有序，如[1,2,3,4……999,1000……999999,1000000],那么程序就會占用超高內存，而且根本運算不了，而且按?計算的話，運算時間得以小時計算，直接退出，如下圖。

??

?原因是什么呢，對于有序列表，當選取的key為兩端時，那么這個key的另一邊全是大于或小于key的值，如此進行快排并沒有實現(xiàn)key分區(qū)的作用，只是將key逐個拿走，如此就變?yōu)?strong>的時間復雜度，并且每次處理完列表長度幾乎沒有變化，那么內存逐漸消耗，極占據(jù)內存。

2. 如果提示超出遞歸深度，添加如下代碼，拓展遞歸深度

import sys sys.setrecursionlimit(10000000)

?3. python計算代碼運行時間

import timetime.process_time() #不計算代碼中的延時，單位是秒，通過兩次差值得到中間代碼塊運行時長 time.perf_counter() #包括代碼中的延時，單位是秒，通過兩次差值得到中間代碼塊運行時長

4. 列表作為參數(shù)，函數(shù)會修改該列表的值導致主程序的列表值也隨之改變，測試代碼如下。

real_a = [5] print('主程序中執(zhí)行函數(shù)前實參值：', real_a) def val(vir_a):vir_a.append(3)print('函數(shù)內形參修改后的值：', vir_a) val(real_a) print('主程序中執(zhí)行函數(shù)后實參值：', real_a)

運行結果如下

導致該結果的是因為python中，列表和字典是mutuable類型，數(shù)字、字符串以及元組是immutuable類型，處理數(shù)字時，實參則不會被函數(shù)修改，代碼及結果如下。

real_a = 5 print('主程序中執(zhí)行函數(shù)前實參值：', real_a) def val(vir_a):vir_a += 5print('函數(shù)內形參修改后的值：', vir_a) val(real_a) print('主程序中執(zhí)行函數(shù)后實參值：', real_a)

所以當傳遞列表或字典對象時，實際傳的是對象地址，所以函數(shù)可以修改參數(shù)中列表或字典的值，即函數(shù)修改形參時會更改實參，因此我們處理列表或字典時，可以先拷貝一份，在拷貝的那一份進行處理，代碼及結果如下。

real_a = [5] print('主程序中執(zhí)行函數(shù)前實參值：', real_a) def val(vir_a):vir_b = vir_a[:]vir_b.append(3)print('函數(shù)內形參修改后的值：', vir_b) val(real_a) print('主程序中執(zhí)行函數(shù)后實參值：', real_a)

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的插入排序、选择排序、快速排序以及归并排序（附Python代码）的全部內容，希望文章能夠幫你解決所遇到的問題。

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