相關知識來自《python算法設計與分析》。初級排序算法是指幾種較為基礎且容易理解的排序算法。初級排序算法包括插入排序、選擇排序和冒泡排序3種。相比起初級排序算法，高級排序算法往往有更加復雜的邏輯，但也會有更高的時間或空間效率。其中有些高級排序算法是由初級排序算法優(yōu)化而來的。本文介紹快速排序。
二、算法描述快速排序的思想是：取數(shù)組中的一個數(shù)作為基準值，把所有小于基準值的數(shù)都放在它的一側，再把所有大于基準值的數(shù)都放在它的另一側。隨后，對基準值左右兩側的數(shù)組分別進行快速排序。由此可以看出，快速排序的整個排序過程也是遞歸進行的。
快速排序的平均時間復雜度是O(nlgn)，最好情況下的時間復雜度是O(nlgn)。最壞情況下，快速排序的時間復雜度可能退化成O( n2 )，但這種情況很少見。它的空間復雜度是O(nlgn)。它是一個不穩(wěn)定的排序算法。如果使用得當，快速排序的速度可以達到歸并排序和堆排序的數(shù)倍，所以快速排序是一種極其常用的算法。
快速排序的流程如圖2-22所示（以升序排序為例）。
一般情況下，我們?nèi)?shù)組的第一個數(shù)作為基準進行快速排序。在第一步中，基準數(shù)為5?？梢钥闯觯诘诙械臄?shù)組中，比5小的元素：3、4、1、2，都被置于5的左側，而比5大的元素則被置于5的右側。這時，元素5在有序數(shù)組中的位置就確定了。第三行中，我們再取左右兩個無序數(shù)組的第一個數(shù)3和6，分別作為它們的基準數(shù)，然后再次對數(shù)組進行分拆。分拆結束之后，3和6在有序數(shù)組中的位置也確定了。接下來，繼續(xù)處理分拆出來的4個子數(shù)組：[1,2]、[4]、[]、[8,7]。其中，一個子數(shù)組只剩一個數(shù)，一個為空。這意味著[4]與[]已經(jīng)完成了對自己的快速排序。而其他的兩個子數(shù)組則需繼續(xù)處理。全部處理完畢后，我們將得到一個完整的有序數(shù)組。
可以看出，快速排序也是通過這樣的分治思想來排序的。
三、代碼實現(xiàn)在QuickSort()函數(shù)中，首先是邊界條件：如果傳入函數(shù)的列表長度小于等于1，那么這一段列表必定是有序的，可以直接返回。如果不滿足邊界條件，則繼續(xù)執(zhí)行函數(shù)。先用key存儲基準值，再定義3個列表存儲小于基準數(shù)的元素llist，大于基準數(shù)的元素rlist和等于基準數(shù)的元素mlist。由于接下來for循環(huán)的范圍不包括列表中的第一個數(shù)，所以對mlist初始化時，多加一個初始元素key。
接下來的for循環(huán)把數(shù)組內(nèi)的元素分別歸入3個列表中。隨后，再次調(diào)用QuickSort()函數(shù)，對llist和rlist進行排序。這樣，llist和rlist就是有序的了，而mlist內(nèi)的元素剛好處于它們中間的連接部分。所以，排序完成后，把llist、mlist、rlist按順序拼接到一起并輸出。
快速排序代碼（基礎版）：
重慶分公司
重慶分公司
nums = [5,3,6,4,1,2,8,7]
def QuickSort(num):
if len(num)<= 1: #邊界條件
return num
key = num[0] #取數(shù)組的第一個數(shù)為基準數(shù)
llist,rlist,mlist = [],[],[key] #定義空列表，分別存儲小于/大于/等于基準數(shù)的元素
for i in range(1,len(num)): #遍歷數(shù)組，把元素歸類到3個列表中
if num[i] >key:
rlist.append(num[i])
elif num[i]< key:
llist.append(num[i])
else:
mlist.append(num[i])
return QuickSort(llist)+mlist+QuickSort(rlist) #對左右子列表快排，拼接3個列表并返回
print(QuickSort(nums))
運行程序，輸出結果為：
[1,2,3,4,5,6,7,8]以上就是本文要講的內(nèi)容，本文介紹了快速排序理論知識和代碼實現(xiàn)，快速排序的平均時間復雜度是O(nlgn)，最好情況下的時間復雜度是O(nlgn)。最壞情況下，快速排序的時間復雜度可能退化成O( n2 )，但這種情況很少見。它的空間復雜度是O(nlgn)。它是一個不穩(wěn)定的排序算法。
你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
