排序算法是《數據結構與算法》中最基本的算法之一。排序算法可以分爲內部排序和外部排序,內部排序是數據記錄在內存中進行排序,而外部排序是因排序的數據很大,一次不能容納全部的排序記錄,在排序過程中需要訪問外存。常見的內部排序算法有:插入排序、希爾排序、選擇排序、冒泡排序、歸併排序、快速排序、堆排序、基數排序等。以下是快速排序算法:
快速排序是由東尼·霍爾所發展的一種排序算法。在平均狀況下,排序 n 個項目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較,但這種狀況並不常見。事實上,快速排序通常明顯比其他 Ο(nlogn) 算法更快,因爲它的內部循環(inner loop)可以在大部分的架構上很有效率地被實現出來。
快速排序使用分治法(Divide and conquer)策略來把一個串行(list)分爲兩個子串行(sub-lists)。
快速排序又是一種分而治之思想在排序算法上的典型應用。本質上來看,快速排序應該算是在冒泡排序基礎上的遞歸分治法。
快速排序的名字起的是簡單粗暴,因爲一聽到這個名字你就知道它存在的意義,就是快,而且效率高!它是處理大數據最快的排序算法之一了。雖然 Worst Case 的時間複雜度達到了 O(n?),但是人家就是優秀,在大多數情況下都比平均時間複雜度爲 O(n logn) 的排序算法表現要更好,可是這是爲什麼呢,我也不知道。好在我的強迫症又犯了,查了 N 多資料終於在《算法藝術與資訊學競賽》上找到了滿意的答案:
快速排序的最壞執行情況是 O(n?),比如說順序數列的快排。但它的平攤期望時間是 O(nlogn),且 O(nlogn) 記號中隱含的常數因子很小,比複雜度穩定等於 O(nlogn) 的歸併排序要小很多。所以,對絕大多數順序性較弱的隨機數列而言,快速排序總是優於歸併排序。
1. 算法步驟 從數列中挑出一個元素,稱爲 "基準"(pivot);
重新排序數列,所有元素比基準值小的擺放在基準前面,所有元素比基準值大的擺在基準的後面(相同的數可以到任一邊)。在這個分區退出之後,該基準就處於數列的中間位置。這個稱爲分區(partition)操作;
遞歸地(recursive)把小於基準值元素的子數列和大於基準值元素的子數列排序;
2. 動圖演示 代碼實現 JavaScript 實例 function q
ui ckSort
( arr
, left
, right
) { var len
= arr.
length , partitionIndex
, left
= typeof left
!= 'number' ? 0 : left
, right
= typeof right
!= 'number' ? len
- 1 : right
; if ( left
< right
) { partitionIndex
= partition
( arr
, left
, right
) ; quickSort
( arr
, left
, partitionIndex
- 1 ) ; quickSort
( arr
, partitionIndex
+ 1 , right
) ; } return arr
; } function partition
( arr
, left
, right
) { // 分區操作 var pivot
= left
, // 設定基準值(pivot) index
= pivot
+ 1 ; for ( var i
= index
; i
<= right
; i
++ ) { if ( arr
[ i
] < arr
[ pivot
] ) { swap
( arr
, i
, index
) ; index
++; } } swap
( arr
, pivot
, index
- 1 ) ; return index
- 1 ; } function swap
( arr
, i
, j
) { var temp
= arr
[ i
] ; arr
[ i
] = arr
[ j
] ; arr
[ j
] = temp
; } function partition2
( arr
, low
, high
) { let pivot
= arr
[ low
] ; while
( low
< high
) { while
( low
< high
&& arr
[ high
] > pivot
) { -- high
; } arr
[ low
] = arr
[ high
] ; while
( low
< high
&& arr
[ low
] <= pivot
) { ++ low
; } arr
[ high
] = arr
[ low
] ; } arr
[ low
] = pivot
; return low
; } function quickSor
t2 ( arr
, low
, high
) { if ( low
< high
) { let pivot
= partition2
( arr
, low
, high
) ; quickSort2
( arr
, low
, pivot
- 1 ) ; quickSort2
( arr
, pivot
+ 1 , high
) ; } return arr
; } Python 實例 def quickSort
( arr
, left
= None , right
= None ) :
left
= 0 if not isinstance ( left
, ( int , float ) ) else left
right
= len ( arr
) -
1 if not isinstance ( right
, ( int , float ) ) else right
if left
< right:
partitionIndex
= partition
( arr
, left
, right
) quickSort
( arr
, left
, partitionIndex-
1 ) quickSort
( arr
, partitionIndex+
1 , right
) return arr
def partition
( arr
, left
, right
) :
pivot
= left
index
= pivot+
1 i
= index
while i
<= right:
if arr
[ i
] < arr
[ pivot
] :
swap
( arr
, i
, index
) index+
= 1 i+
= 1 swap
( arr
, pivot
, index-
1 ) return index-
1 def swap
( arr
, i
, j
) :
arr
[ i
] , arr
[ j
] = arr
[ j
] , arr
[ i
] Go 實例 func quickSort
( arr
[] int ) [] int { return _quickSort
( arr
, 0 , len ( arr
) - 1 ) } func _quickSort
( arr
[] int , left
, right
int ) [] int { if left < right
{ partitionIndex
:= partition
( arr
, left
, right
) _quickSort
( arr
, left
, partitionIndex
- 1 ) _quickSort
( arr
, partitionIndex
+ 1 , right
) } return arr
} func partition
( arr
[] int , left
, right
int ) int { pivot
:= left
index
:= pivot
+ 1 for i := index
; i <
= right
; i ++ { if arr
[ i ] < arr
[ pivot
] { swap
( arr
, i , index
) index
+= 1 } } swap
( arr
, pivot
, index
- 1 ) return index
- 1 } func swap
( arr
[] int , i , j
int ) { arr
[ i ], arr
[ j
] = arr
[ j
], arr
[ i ] } C++ 實例 //嚴蔚敏《數據結構》標準分割函數 Paritition1
( int A
[ ] ,
int low,
int high
) { int pivot
= A
[ low
] ; while ( low
< high
) { while ( low
< high
&& A
[ high
] >= pivot
) { -- high
; } A
[ low
] = A
[ high
] ; while ( low
< high
&& A
[ low
] <= pivot
) { ++ low
; } A
[ high
] = A
[ low
] ; } A
[ low
] = pivot
; return low
; } void QuickSort
( int A
[ ] ,
int low,
int high
) //快排母函數 { if ( low
< high
) { int pivot
= Paritition1
( A, low, high
) ; QuickSort
( A, low, pivot
- 1 ) ; QuickSort
( A, pivot
+ 1 , high
) ; } } Java 實例 public class QuickSort
implements IArraySort
{ @Override
public int [ ] sort
( int [ ] sourceArray
) throws Exception { // 對 arr 進行拷貝,不改變參數內容 int [ ] arr
= Arrays .
copyOf ( sourceArray, sourceArray.
length ) ; return quickSort
( arr,
0 , arr.
length - 1 ) ; } private int [ ] quickSort
( int [ ] arr,
int left,
int right
) { if ( left
< right
) { int partitionIndex
= partition
( arr, left, right
) ; quickSort
( arr, left, partitionIndex
- 1 ) ; quickSort
( arr, partitionIndex
+ 1 , right
) ; } return arr
; } private int partition
( int [ ] arr,
int left,
int right
) { // 設定基準值(pivot) int pivot
= left
; int index
= pivot
+ 1 ; for ( int i
= index
; i
<= right
; i
++ ) { if ( arr
[ i
] < arr
[ pivot
] ) { swap
( arr, i, index
) ; index
++; } } swap
( arr, pivot, index
- 1 ) ; return index
- 1 ; } private void swap
( int [ ] arr,
int i,
int j
) { int temp
= arr
[ i
] ; arr
[ i
] = arr
[ j
] ; arr
[ j
] = temp
; } } PHP 實例 function quickSort
( $arr ) { if ( count ( $arr ) <= 1 ) return $arr ; $middle = $arr [ 0 ] ; $leftArray = array ( ) ; $rightArray = array ( ) ; for ( $i = 1 ; $i < count ( $arr ) ; $i ++ ) { if ( $arr [ $i ] > $middle ) $rightArray [ ] = $arr [ $i ] ; else $leftArray [ ] = $arr [ $i ] ; } $leftArray = quickSort
( $leftArray ) ; $leftArray [ ] = $middle ; $rightArray = quickSort
( $rightArray ) ; return array_merge ( $leftArray , $rightArray ) ; } C 實例 typedef struct _Range
{ int start
, end
; } Range
; Range new_Range
( int s
, int e
) { Range r
; r.
start = s
; r.
end = e
; return r
; } void swap
( int * x
, int * y
) { int t
= * x
; * x
= * y
; * y
= t
; } void quick_sort
( int arr
[ ] , const int len
) { if ( len
<= 0 ) return ; // 避免len等於負值時引發段錯誤(Segment Fault) // r[]模擬列表,p為數量,r[p++]為push,r[--p]為pop且取得元素 Range r
[ len
] ; int p
= 0 ; r
[ p
++ ] = new_Range
( 0 , len
- 1 ) ; while ( p
) { Range range
= r
[ -- p
] ; if ( range.
start >= range.
end ) continue ; int mid
= arr
[ ( range.
start + range.
end ) / 2 ] ; // 選取中間點為基準點 int left
= range.
start , right
= range.
end ; do { while ( arr
[ left
] < mid
) ++ left
; // 檢測基準點左側是否符合要求 while ( arr
[ right
] > mid
) -- right
; //檢測基準點右側是否符合要求 if ( left
<= right
) { swap
( & arr
[ left
] , & arr
[ right
] ) ; left
++; right
--; // 移動指針以繼續 } } while ( left
<= right
) ; if ( range.
start < right
) r
[ p
++ ] = new_Range
( range.
start , right
) ; if ( range.
end > left
) r
[ p
++ ] = new_Range
( left
, range.
end ) ; } } 遞歸法
實例 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++ 函數法
sort(a,a + n);// 排序a[0]-a[n-1]的所有數. 迭代法
實例 // 參考: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 < typename T
> // 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)、"大於"(>)、"不小於"(>=)的運算子功能 void quick_sort
( T arr
[ ] ,
const int len
) { if ( len
<= 0 ) return ; // 避免len等於負值時宣告堆疊陣列當機 // r[]模擬堆疊,p為數量,r[p++]為push,r[--p]為pop且取得元素 Range r
[ len
] ; int p
= 0 ; r
[ p
++ ] = Range
( 0 , len
- 1 ) ; while ( p
) { Range range
= r
[ -- p
] ; if ( range.
start >= range.
end ) continue ; T mid
= arr
[ range.
end ] ; int left
= range.
start , right
= range.
end - 1 ; while ( left
< right
) { while ( arr
[ left
] < mid
&& left
< right
) left
++ ; while ( arr
[ right
] >= mid
&& left
< right
) right
-- ; std
:: swap ( arr
[ left
] , arr
[ right
] ) ; } if ( arr
[ left
] >= arr
[ range.
end ] ) std
:: swap ( arr
[ left
] , arr
[ range.
end ] ) ; else left
++ ; r
[ p
++ ] = Range
( range.
start , left
- 1 ) ; r
[ p
++ ] = Range
( left
+ 1 , range.
end ) ; } } 遞歸法
實例 template < typename T
> void quick_sort_recursive
( T arr
[ ] ,
int start,
int end
) { if ( start
>= end
) return ; T 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
-- ; std
:: swap ( arr
[ left
] , arr
[ right
] ) ; //交換元素 } if ( arr
[ left
] >= arr
[ end
] ) std
:: swap ( arr
[ left
] , arr
[ end
] ) ; else left
++ ; quick_sort_recursive
( arr, start, left
- 1 ) ; quick_sort_recursive
( arr, left
+ 1 , end
) ; } template < typename T
> //整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)、"大於"(>)、"不小於"(>=)的運算子功能 void quick_sort
( T arr
[ ] ,
int len
) { quick_sort_recursive
( arr,
0 , len
- 1 ) ; } 參考地址:
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
以下是熱心網友對快速排序算法的補充,僅供參考:
熱心網友提供的補充1:
上方沒有C#實現,我補充一下,如下所示:
//快速排序(目標數組,數組的起始位置,數組的終止位置)static void QuickSort(int[] array, int left = 0, int right = -1){ if (right.Equals(-1)) right = array.Length - 1; try { int keyValuePosition; //記錄關鍵值的下標 //當傳遞的目標數組含有兩個以上的元素時,進行遞歸調用。(即:當傳遞的目標數組只含有一個元素時,此趟排序結束) if (left < right) { keyValuePosition = Partion(array, left, right); //獲取 關鍵值的下標(快排的核心) QuickSort(array, left, keyValuePosition - 1); //遞歸調用,快排劃分出來的左區間 QuickSort(array, keyValuePosition + 1, right); //遞歸調用,快排劃分出來的右區間 } } catch (Exception ex) { Console.WriteLine("Exception: {0}", ex); }}///快速排序的核心部分:確定關鍵值在數組中的位置,以此將數組劃分成左右兩區間,關鍵值遊離在外。(返回關鍵值應在數組中的下標)static int Partion(int[] array, int left, int right){ int leftIndex = left; //記錄目標數組的起始位置(後續動態的左側下標) int rightIndex = right; //記錄目標數組的結束位置(後續動態的右側下標) int keyValue = array[left]; //數組的第一個元素作爲關鍵值 int temp; //當 (左側動態下標 == 右側動態下標) 時跳出循環 while (leftIndex < rightIndex) { while (leftIndex < rightIndex && array[leftIndex] <= keyValue) //左側動態下標逐漸增加,直至找到大於keyValue的下標 { leftIndex++; } while (leftIndex < rightIndex && array[rightIndex] > keyValue) //右側動態下標逐漸減小,直至找到小於或等於keyValue的下標 { rightIndex--; } if (leftIndex < rightIndex) //如果leftIndex < rightIndex,則交換左右動態下標所指定的值;當leftIndex==rightIndex時,跳出整個循環 { temp = array[leftIndex]; array[leftIndex] = array[rightIndex]; array[rightIndex] = temp; } } //當左右兩個動態下標相等時(即:左右下標指向同一個位置),此時便可以確定keyValue的準確位置 temp = keyValue; if (temp < array[rightIndex]) //當keyValue < 左右下標同時指向的值,將keyValue與rightIndex - 1指向的值交換,並返回rightIndex - 1 { array[left] = array[rightIndex - 1]; array[rightIndex - 1] = temp; return rightIndex - 1; } else //當keyValue >= 左右下標同時指向的值,將keyValue與rightIndex指向的值交換,並返回rightIndex { array[left] = array[rightIndex]; array[rightIndex] = temp; return rightIndex; }} 熱心網友提供的補充2:
補充 scala 實現版本:
/** * @Auther: huowang * @Date: 19:34:47 2020/12/10 * @DES: 分區交換算法(快速排序發) * @Modified By: */object PartitionExchange { /** * 分區內切割 * @param arr * @param left * @param right * @return */ def partition(arr:Array[Int],left:Int,right: Int):Int={ // 獲取基準元素 直接選取最右側一個元素爲基準元素 val pv=arr(right) // 把最左邊一個索引作爲堆疊索引 var storeIndex=left //操作數組 -1是因爲 最右邊一個元素是基準元素 for (i <- left to right-1 ){ if(arr(i)<=pv){ //把小於基準元素的元素 都堆到集合左端 swap(arr,storeIndex,i) // 把用於堆疊索引往前移動一個 storeIndex=storeIndex+1 } //如果出現了比基準元素大的元素,那麼則不會移動堆疊索引 // 但是如果之後又出現了比基準元素小的元素,那邊會與這個大的元素交換位置 // 進而使大的元素永遠出現在堆疊索引右側 } // 這裏最有右的元素,其實是基準元素,我們把基準元素和最後堆疊索引對應的元素調換位置 // 這樣基準元素左邊就都是大於它的元素了 swap(arr,right,storeIndex) // 返回堆疊索引位置,目前堆疊索引指向的就是基準元素 storeIndex }def quicksort(arr:Array[Int],left: Int,right: Int):Array[Int]={ if(right>left){ // 左右索引不重合 // 隨便選擇一個元素作爲基準 就選擇最左邊的吧 var pivotIndex=0 // 切割返回基準元素 pivotIndex= partition(arr,left,right) // 遞歸對切割形成的兩個子集進行排序 quicksort(arr,left,pivotIndex-1) quicksort(arr,pivotIndex,right) } arr } /** * 調換 a b 元素在數組中的位置 * @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 = { // 測試 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(",")) }} 熱心網友提供的補充3:
補充一下迭代法的 python 實現:
def _partition(array:list, start:int, end:int) -> int: """ 將數組指定片段進行左右劃分,首先選擇中位元素爲中值。 比中位元素小的置於其左,與中位元素相等或比中位元素大的置於其右, 最後返回中位元素的下標位置。 """ # 以中位元素爲中值劃分,儘量避免極端情況 mid = (start + end) >> 1 array[start], array[mid] = array[mid], array[start] # 劃分的實現 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 idef quickSort(array:list) -> list: """ 迭代法快速排序,隊列結構輔助實現。 """ sorted_array = array.copy() length = len(sorted_array) # 使用隊列儲存每次劃分的二元組:(起始下標,終止下標) queue = [] queue.append((0, length - 1)) # 隊列爲空,則所有劃分操作執行完畢 while len(queue): left, right = queue.pop(0) pos = _partition(sorted_array, left, right) # 默認長度爲 1 的序列有序,那麼區間長度 > 1 才需要劃分,才需要儲存到隊列中 if (left < pos - 1): queue.append((left, pos - 1)) if (pos + 1 < right): queue.append((pos + 1, right)) return sorted_arrayif __name__ == "__main__": array = [21, -17, 1, -27, 41, 17, -5, -49] sorted_array = quickSort(array) print("排序前:{array1}排序後:{array2}".format(array1=array, array2=sorted_array)) 以上爲快速排序算法詳細介紹,插入排序、希爾排序、選擇排序、冒泡排序、歸併排序、快速排序、堆排序、基數排序等排序算法各有優缺點,用一張圖概括:
關於時間複雜度
平方階 (O(n2)) 排序 各類簡單排序:直接插入、直接選擇和冒泡排序。
線性對數階 (O(nlog2n)) 排序 快速排序、堆排序和歸併排序;
O(n1+§)) 排序,§ 是介於 0 和 1 之間的常數。 希爾排序
線性階 (O(n)) 排序 基數排序,此外還有桶、箱排序。
關於穩定性
穩定的排序算法:冒泡排序、插入排序、歸併排序和基數排序。
不是穩定的排序算法:選擇排序、快速排序、希爾排序、堆排序。
名詞解釋:
n:數據規模
k:"桶"的個數
In-place:佔用常數內存,不佔用額外內存
Out-place:佔用額外內存
穩定性:排序後 2 個相等鍵值的順序和排序之前它們的順序相同