8行程式碼實現快速排序,簡單易懂圖解!

快速排序是一種常用的排序演算法,比選擇排序快的多。在之前的我隨筆中也寫過關於快速排序的演算法,也可以看一下和現在的區別python實現快速排序 – Mr-Yang` – 部落格園 (cnblogs.com)

在看快速排序之前,要先了解一下遞歸,對於遞歸我之前的文章中也有提到python遞歸函數 – Mr-Yang` – 部落格園 (cnblogs.com),在這裡我補充一個關於遞歸的一個點:基準線條件和遞歸條件

一、基準線條件和遞歸條件

由於遞歸函數是自己調用自己,因此編寫這樣的函數時容易出錯,從而導致無限循環。示例如下:

def countdown(i):
    print(i)
    countdown(i-1)

如果運行上述程式碼,就會發現一個問題:這個函數運行起來是不會停止,直到到達遞歸的最大深度。

正是因為這樣,編寫遞歸函數的時候,必須告訴它何時停止遞歸,所以每個遞歸函數都有兩個部分:基準線條件(base case)和遞歸條件(recursive case)。遞歸條件指定的是函數調用自己,而基準線條件則指的是不再調用自己,從而避免循環。例如給 countdown 添加基準線條件。

def countdown(i):
    print(i)
   	if i <= 1:	#<----------基準線條件
        return
    else:	#<--------------遞歸條件
        countdown(i-1)

這樣就按照預期那樣執行,不會無限循環下去如圖所示

遞歸函數

二、快速排序

因為對於排序來說,最簡單的就是一個空列表,或者只包含一個元素的列表,所以可以將基準線條件設置為空或只包含一個元素,在這種情況下,只需要返回原列表。

def quicksort(alist):
    if len(alist) < 2:
        return alist

思路如下圖所示:

快速排序思路

程式碼如下:

def quicksort(alist):
    if len(alist) < 2:
        return alist	# 基準線條件為空或只包含一個元素的列表是有序的。
    else:
        pivot = alist[0]	# 選擇基準值
        less = [i for i in alist[1:] if i <= pivot]	# 由小於基準值的元素組成
        biggish = [i for i in alist[1:] if i > pivot]	# 由大於基準值的元素組成
        return quicksort(less) + [pivot] + quicksort(biggish)