科技
排序算法是《數(shù)據(jù)結(jié)構(gòu)與算法》中最基本的算法之一。排序算法可以分為內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過(guò)程中需要訪(fǎng)問(wèn)外存。常見(jiàn)的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。以下是快速排序算法：
快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個(gè)項(xiàng)目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況并不常見(jiàn)。事實(shí)上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來(lái)。
快速排序使用分治法（Divide and conquer）策略來(lái)把一個(gè)串行（list）分為兩個(gè)子串行（sub-lists）。
快速排序又是一種分而治之思想在排序算法上的典型應(yīng)用。本質(zhì)上來(lái)看，快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法。
快速排序的名字起的是簡(jiǎn)單粗暴，因?yàn)橐宦?tīng)到這個(gè)名字你就知道它存在的意義，就是快，而且效率高！它是處理大數(shù)據(jù)最快的排序算法之一了。雖然 Worst Case 的時(shí)間復(fù)雜度達(dá)到了 O(n?)，但是人家就是優(yōu)秀，在大多數(shù)情況下都比平均時(shí)間復(fù)雜度為 O(n logn) 的排序算法表現(xiàn)要更好，可是這是為什么呢，我也不知道。好在我的強(qiáng)迫癥又犯了，查了 N 多資料終于在《算法藝術(shù)與信息學(xué)競(jìng)賽》上找到了滿(mǎn)意的答案：
快速排序的最壞運(yùn)行情況是 O(n?)，比如說(shuō)順序數(shù)列的快排。但它的平攤期望時(shí)間是 O(nlogn)，且 O(nlogn) 記號(hào)中隱含的常數(shù)因子很小，比復(fù)雜度穩(wěn)定等于 O(nlogn) 的歸并排序要小很多。所以，對(duì)絕大多數(shù)順序性較弱的隨機(jī)數(shù)列而言，快速排序總是優(yōu)于歸并排序。
1. 算法步驟從數(shù)列中挑出一個(gè)元素，稱(chēng)為 "基準(zhǔn)"（pivot）;
重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱(chēng)為分區(qū)（partition）操作；
遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序；
2. 動(dòng)圖演示
遞歸法
實(shí)例 void swap(int *x, int *y) {? ? int t = *x;? ? *x = *y;? ? *y = t;}void quick_sort_recursive(int arr[], int start, int end) {? ? if (start >= end)? ? ? ? return;? ? int mid = arr[end];? ? int left = start, right = end - 1;? ? while (left < right) {? ? ? ? while (arr[left] < mid && left < right)? ? ? ? ? ? left++;? ? ? ? while (arr[right] >= mid && left < right)? ? ? ? ? ? right--;? ? ? ? swap(&arr[left], &arr[right]);? ? }? ? if (arr[left] >= arr[end])? ? ? ? swap(&arr[left], &arr[end]);? ? else? ? ? ? left++;? ? if (left)? ? ? ? quick_sort_recursive(arr, start, left - 1);? ? quick_sort_recursive(arr, left + 1, end);}void quick_sort(int arr[], int len) {? ? quick_sort_recursive(arr, 0, len - 1);}C++函數(shù)法
sort(a,a + n);// 排序a[0]-a[n-1]的所有數(shù).
迭代法
實(shí)例 // 參考：http://www.dutor.net/index.php/2011/04/recursive-iterative-quick-sort/struct Range {? ? int start, end;? ? Range(int s = 0, int e = 0) {? ? ? ? start = s, end = e;? ? }};template遞歸法
實(shí)例 template參考地址:
https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/6.quickSort.md
https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F
以下是熱心網(wǎng)友對(duì)快速排序算法的補(bǔ)充，僅供參考：
熱心網(wǎng)友提供的補(bǔ)充1：
上方?jīng)]有C#實(shí)現(xiàn)，我補(bǔ)充一下，如下所示：
//快速排序（目標(biāo)數(shù)組，數(shù)組的起始位置，數(shù)組的終止位置）
static void QuickSort(int[] array, int left = 0, int right = -1)
{
if (right.Equals(-1)) right = array.Length - 1;
try
{
int keyValuePosition; //記錄關(guān)鍵值的下標(biāo)
//當(dāng)傳遞的目標(biāo)數(shù)組含有兩個(gè)以上的元素時(shí)，進(jìn)行遞歸調(diào)用。（即：當(dāng)傳遞的目標(biāo)數(shù)組只含有一個(gè)元素時(shí)，此趟排序結(jié)束）
if (left < right)
{
keyValuePosition = Partion(array, left, right); //獲取關(guān)鍵值的下標(biāo)（快排的核心）
QuickSort(array, left, keyValuePosition - 1); //遞歸調(diào)用，快排劃分出來(lái)的左區(qū)間
QuickSort(array, keyValuePosition + 1, right); //遞歸調(diào)用，快排劃分出來(lái)的右區(qū)間
}
}
catch (Exception ex)
{
Console.WriteLine("Exception: {0}", ex);
}
}
///快速排序的核心部分：確定關(guān)鍵值在數(shù)組中的位置，以此將數(shù)組劃分成左右兩區(qū)間，關(guān)鍵值游離在外。（返回關(guān)鍵值應(yīng)在數(shù)組中的下標(biāo)）
static int Partion(int[] array, int left, int right)
{
int leftIndex = left; //記錄目標(biāo)數(shù)組的起始位置（后續(xù)動(dòng)態(tài)的左側(cè)下標(biāo)）
int rightIndex = right; //記錄目標(biāo)數(shù)組的結(jié)束位置（后續(xù)動(dòng)態(tài)的右側(cè)下標(biāo)）
int keyValue = array[left]; //數(shù)組的第一個(gè)元素作為關(guān)鍵值
int temp;
//當(dāng) （左側(cè)動(dòng)態(tài)下標(biāo) == 右側(cè)動(dòng)態(tài)下標(biāo)） 時(shí)跳出循環(huán)
while (leftIndex < rightIndex)
{
while (leftIndex < rightIndex && array[leftIndex] <= keyValue) //左側(cè)動(dòng)態(tài)下標(biāo)逐漸增加，直至找到大于keyValue的下標(biāo)
{
leftIndex++;
}
while (leftIndex < rightIndex && array[rightIndex] > keyValue) //右側(cè)動(dòng)態(tài)下標(biāo)逐漸減小，直至找到小于或等于keyValue的下標(biāo)
{
rightIndex--;
}
if (leftIndex < rightIndex) //如果leftIndex < rightIndex，則交換左右動(dòng)態(tài)下標(biāo)所指定的值；當(dāng)leftIndex==rightIndex時(shí)，跳出整個(gè)循環(huán)
{
temp = array[leftIndex];
array[leftIndex] = array[rightIndex];
array[rightIndex] = temp;
}
}
//當(dāng)左右兩個(gè)動(dòng)態(tài)下標(biāo)相等時(shí)（即：左右下標(biāo)指向同一個(gè)位置），此時(shí)便可以確定keyValue的準(zhǔn)確位置
temp = keyValue;
if (temp < array[rightIndex]) //當(dāng)keyValue < 左右下標(biāo)同時(shí)指向的值，將keyValue與rightIndex - 1指向的值交換，并返回rightIndex - 1
{
array[left] = array[rightIndex - 1];
array[rightIndex - 1] = temp;
return rightIndex - 1;
}
else //當(dāng)keyValue >= 左右下標(biāo)同時(shí)指向的值，將keyValue與rightIndex指向的值交換，并返回rightIndex
{
array[left] = array[rightIndex];
array[rightIndex] = temp;
return rightIndex;
}
}熱心網(wǎng)友提供的補(bǔ)充2：
補(bǔ)充 scala 實(shí)現(xiàn)版本：
/**
* @Auther: huowang
* @Date: 19:34:47 2020/12/10
* @DES: 分區(qū)交換算法（快速排序發(fā)）
* @Modified By:
*/
object PartitionExchange {
/**
* 分區(qū)內(nèi)切割
* @param arr
* @param left
* @param right
* @return
*/
def partition(arr:Array[Int],left:Int,right: Int):Int={
// 獲取基準(zhǔn)元素 直接選取最右側(cè)一個(gè)元素為基準(zhǔn)元素
val pv=arr(right)
// 把最左邊一個(gè)索引作為堆疊索引
var storeIndex=left
//操作數(shù)組 -1是因?yàn)?最右邊一個(gè)元素是基準(zhǔn)元素
for (i <- left to right-1 ){
if(arr(i)<=pv){
//把小于基準(zhǔn)元素的元素 都堆到集合左端
swap(arr,storeIndex,i)
// 把用于堆疊索引往前移動(dòng)一個(gè)
storeIndex=storeIndex+1
}
//如果出現(xiàn)了比基準(zhǔn)元素大的元素,那么則不會(huì)移動(dòng)堆疊索引
// 但是如果之后又出現(xiàn)了比基準(zhǔn)元素小的元素,那邊會(huì)與這個(gè)大的元素交換位置
// 進(jìn)而使大的元素永遠(yuǎn)出現(xiàn)在堆疊索引右側(cè)
}
// 這里最有右的元素,其實(shí)是基準(zhǔn)元素,我們把基準(zhǔn)元素和最后堆疊索引對(duì)應(yīng)的元素調(diào)換位置
// 這樣基準(zhǔn)元素左邊就都是大于它的元素了
swap(arr,right,storeIndex)
// 返回堆疊索引位置,目前堆疊索引指向的就是基準(zhǔn)元素
storeIndex
}
def quicksort(arr:Array[Int],left: Int,right: Int):Array[Int]={
if(right>left){
// 左右索引不重合
// 隨便選擇一個(gè)元素作為基準(zhǔn) 就選擇最左邊的吧
var pivotIndex=0
// 切割返回基準(zhǔn)元素
pivotIndex= partition(arr,left,right)
// 遞歸對(duì)切割形成的兩個(gè)子集進(jìn)行排序
quicksort(arr,left,pivotIndex-1)
quicksort(arr,pivotIndex,right)
}
arr
}
/**
* 調(diào)換 a b 元素在數(shù)組中的位置
* @param arr
* @param a
* @param b
*/
def swap(arr:Array[Int],a:Int,b:Int)={
val tmp=arr(a)
arr(a)=arr(b)
arr(b)=tmp
}
def main(args: Array[String]): Unit = {
// 測(cè)試
val arr=Array(5, 2, 9,11,3,6,8,4,0,0)
val arrNew=quicksort(arr,0,arr.size-1)
println(arrNew.toList.mkString(","))
}
}熱心網(wǎng)友提供的補(bǔ)充3：
補(bǔ)充一下迭代法的 python 實(shí)現(xiàn)：
def _partition(array:list, start:int, end:int) -> int:
"""
將數(shù)組指定片段進(jìn)行左右劃分，首先選擇中位元素為中值。
比中位元素小的置于其左，與中位元素相等或比中位元素大的置于其右，
最后返回中位元素的下標(biāo)位置。
"""
# 以中位元素為中值劃分，盡量避免極端情況
mid = (start + end) >> 1
array[start], array[mid] = array[mid], array[start]
# 劃分的實(shí)現(xiàn)
i, j = start, end
x = array[start]
while (i < j):
if (i < j and array[j] >= x): j -= 1
array[i] = array[j]
if (i < j and array[i] < x): i += 1
array[j] = array[i]
array[i] = x
return i
def quickSort(array:list) -> list:
"""
迭代法快速排序，隊(duì)列結(jié)構(gòu)輔助實(shí)現(xiàn)。
"""
sorted_array = array.copy()
length = len(sorted_array)
# 使用隊(duì)列保存每次劃分的二元組：(起始下標(biāo)，終止下標(biāo))
queue = []
queue.append((0, length - 1))
# 隊(duì)列為空，則所有劃分操作執(zhí)行完畢
while len(queue):
left, right = queue.pop(0)
pos = _partition(sorted_array, left, right)
# 默認(rèn)長(zhǎng)度為 1 的序列有序，那么區(qū)間長(zhǎng)度 > 1 才需要?jiǎng)澐郑判枰４娴疥?duì)列中
if (left < pos - 1): queue.append((left, pos - 1))
if (pos + 1 < right): queue.append((pos + 1, right))
return sorted_array
if __name__ == "__main__":
array = [21, -17, 1, -27, 41, 17, -5, -49]
sorted_array = quickSort(array)
print("排序前：{array1}
排序后：{array2}".format(array1=array, array2=sorted_array))以上為快速排序算法詳細(xì)介紹，插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等排序算法各有優(yōu)缺點(diǎn)，用一張圖概括： 
關(guān)于時(shí)間復(fù)雜度
平方階 (O(n2)) 排序 各類(lèi)簡(jiǎn)單排序：直接插入、直接選擇和冒泡排序。
線(xiàn)性對(duì)數(shù)階 (O(nlog2n)) 排序 快速排序、堆排序和歸并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之間的常數(shù)。 希爾排序
線(xiàn)性階 (O(n)) 排序 基數(shù)排序，此外還有桶、箱排序。
關(guān)于穩(wěn)定性
穩(wěn)定的排序算法：冒泡排序、插入排序、歸并排序和基數(shù)排序。
不是穩(wěn)定的排序算法：選擇排序、快速排序、希爾排序、堆排序。
名詞解釋?zhuān)?/p>
n：數(shù)據(jù)規(guī)模
k："桶"的個(gè)數(shù)
In-place：占用常數(shù)內(nèi)存，不占用額外內(nèi)存
Out-place：占用額外內(nèi)存
穩(wěn)定性：排序后 2 個(gè)相等鍵值的順序和排序之前它們的順序相同
<sup id="m40ya"></sup>
