前言
快速排序應該是排序中最出名的算法了，也可能是應用最廣泛的排序算法了。他之所以流行，是因為實現簡單，同時適用於各種數據，且一般比其他排序算法要快。
快排原理
快排是對冒泡排序的一種改進，它之所以快是因為一次交換能改變多個逆序對，而冒泡排序只能改變一個逆序對。
而快排的基本思想即是：通過一趟排序將欲排序的數據分割成兩部分，其中一部分數據比另一部分所有數據都要小。接著繼續對這兩部分數據進行快速排序。則是分治思想的體現。
下面我們用圖例來看看一趟排序
此過程如下：
- 選定數組a[lo]作為切分元素，同時令i = lo, j = hi，即對應lo、hi位置
- i指針從左向右掃描，遇見>v的數時暫停；j指針從右向左掃描，遇見= j。
- 當2流程結束時，此時j指向小於切分元素的數字，進行交換。此時切分元素已位於最終位置，切分元素左側元素均小於切分元素，右側元素均大於切分元素
- 對卻分後的子數組重複上述流程：sort(array, lo, j - 1);sort(array, j + 1, hi)。直至遞歸結束
代碼實現
核心代碼sort與partition，sort用於遞歸調用，partition用於切分
<code> sort(array, lo, hi) {
if(hi <= lo ){
return ;
}
const j = this.partition(array, lo, hi);
this.sort(array, lo, j - 1);
this.sort(array, j + 1, hi);
}
partition(array, lo, hi){
let i = lo;
let j = hi + 1;
const ele = array[lo];//切分元素
while(true){
while(this.less(array[++i], ele)){//左向右掃描
if(i === hi){
break;
}
}
while(this.less(ele, array[--j])){//右向左掃描
if(j === lo){
break;
}
}
if(i >= j){
break;
}
this.exch(array, i ,j);//左右元素交換
}
this.exch(array, lo, j);//切分元素交換
return j;
}/<code> 性能特點
主要優點：
- 實現簡單
- 一般情況下比其他排序算法快得多
- 長度為N的數組排序時間為NlgN
- 內循環比大多數排序算法都要短小
主要缺點：
- 脆弱，在切分不平衡時可能導致極低的性能。比如倒序變升序
總結
以上的快排是最基礎的版本。針對不同的場景，其實還有很多的改進空間使得性能提升，比如：
- 對於小數組可在快排中切換至插入排序
- 對於含有大量重複元素的數組，比如生日、性別，可將數組切分為三部分，分別對應小於、等於、大於切分元素的數組元素
分享到:
