快速排序算法

快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序?n?個項目要Ο(n?log?n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他Ο(n?log?n)?算法更快，因為它的內(nèi)部循環(huán)（inner?loop）可以在大部分的架構(gòu)上很有效率地被實現(xiàn)出來。

快速排序使用分治法（Divide?and?conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。

算法步驟：

1 、從數(shù)列中挑出一個元素，稱為?"基準"（pivot）

2 、重新排序數(shù)列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作

3 、遞歸（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序

遞歸的最底部情形，是數(shù)列的大小是零或一，也就是永遠都已經(jīng)被排序好了。雖然一直遞歸下去，但是這個算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。

這里簡單的介紹一下遞歸的三個原則，

1、有基本的結(jié)束條件，比如這里結(jié)束條件是只剩兩個數(shù)對比

2、問題規(guī)模不斷減少，比如這里不斷地對比兩個數(shù)字，剩下的可以比的數(shù)不斷減少

3、調(diào)用函數(shù)自身，例如累加返回return?x+add(x-1)

本處代碼"[x for x in arr if x<i]"為“list comprehension”（列表推導(dǎo)式）是一個python書寫技巧，用法如下：

列表推導(dǎo)式提供了從序列創(chuàng)建列表的簡單途徑。通常應(yīng)用程序?qū)⒁恍┎僮鲬?yīng)用于某個序列的每個元素，用其獲得的結(jié)果作為生成新列表的元素，或者根據(jù)確定的判定條件創(chuàng)建子序列。

每個列表推導(dǎo)式都在 for 之后跟一個表達式，然后有零到多個 for 或 if 子句。返回結(jié)果是一個根據(jù)表達從其后的 for 和 if 上下文環(huán)境中生成出來的列表。如果希望表達式推導(dǎo)出一個元組，就必須使用括號。

這里我們將列表中每個數(shù)值乘三，獲得一個新的列表：

>>>?vec?=?[2,?4,?6]
>>>?[3*x?for?x?in?vec]
[6,?12,?18]

教程講解視頻：【排序算法精華3】快速排序 (上）_嗶哩嗶哩_bilibili

#簡單的快排代碼如下：

def qsort(arr):

? ? if len(arr)<=1:

? ? ? ? return arr

? ? #元素數(shù)量為0或1，直接返回

? ? elif len(arr)==2:

? ? ? ? #有2個元素的情況

? ? ? ? if arr[0]>arr[1]:

? ? ? ? ? ? return arr[1],arr[0]

? ? ? ? else:

? ? ? ? ? ? return arr

? ? else:

? ? ? ? #選取標桿

? ? ? ? i=arr[0]

? ? ? ? #比標桿小的元素集合

? ? ? ? L=[x for x in arr if x<i]

? ? ? ? #比標桿大的元素集合

? ? ? ? R=[x for x in arr if x>i]

? ? ? ? #重復(fù)以上兩個步驟并合并

? ? ? ? res=qsort(L)+qsort(R)+[i]

? ? ? ? return res

Myarr=[5,2.343,35,6,8,24,67]

qsort(Myarr)