來源 | https://www.cnblogs.com/EaVango/archive/2021/05/14/14769230.html

快速排序的基本思想是選擇數(shù)組中的一個元素作為關(guān)鍵字，通過一趟排序，把待排序的數(shù)組分成兩個部分，其中左邊的部分比所有關(guān)鍵字小，右邊的部分比所有關(guān)鍵字大。

然后，再分別對左右兩邊的數(shù)據(jù)作此重復(fù)操作，直到所有元素都有序，就得到了一個完全有序的數(shù)組。

來看一個例子，以數(shù)組[4, 5, 2, 7, 3, 1, 6, 8]為例，我們選中數(shù)組最左邊的元素為關(guān)鍵字pivot

第一步從右側(cè)開始，往左移動右指針，遇到8，6，都比4大，直到遇到1，比4小，故把1移動到最左邊。右指針保持不動，開始移動左指針。

移動左指針，發(fā)現(xiàn)5比關(guān)鍵字pivot 4大，所以把5移動到剛才記錄的右指針的位置，相當(dāng)于把比pivot大的值都移動到右側(cè)。然后開始移動右指針。

移動右指針，發(fā)現(xiàn)3比pivot小，故把3移動到剛才左指針記錄的位置，開始移動左指針。

移動左指針，2比pivot小，再移動，發(fā)現(xiàn)7，7比pivot大，故把7放到右指針記錄的位置，再次開始移動右指針。

移動右指針，發(fā)現(xiàn)兩個指針重疊了，將pivot的值插入指針位置（相當(dāng)于找到了pivot在排序完成后所在的確切位置）。此次排序結(jié)束。

一趟排序結(jié)束后，將重疊的指針位置記錄下來，分別對左右兩側(cè)的子數(shù)組繼續(xù)上面的操作，直到分割成單個元素的數(shù)組。所有操作完成之后，整個數(shù)組也就變成有序數(shù)組了。

動態(tài)圖如下，動態(tài)圖使用20個元素的無序數(shù)組來演示。其中灰色背景為當(dāng)前正在排序的子數(shù)組，橙色為當(dāng)前pivot，為方便演示，使用交換元素的方式體現(xiàn)指針位置。

JavaScript實現(xiàn)

代碼如下：

const quickSort = (array)=>{  quick(array, 0, array.length - 1)}
const quick = (array, left, right)=>{  if(left < right){    let index = getIndex(array, left, right);    quick(array, left, index-1)    quick(array, index+1, right)  }}
const getIndex = (array, leftPoint, rightPoint)=>{  let pivot = array[leftPoint];  while(leftPoint < rightPoint){    while(leftPoint < rightPoint && array[rightPoint] >= pivot) {      rightPoint--;    }    array[leftPoint] = array[rightPoint]    // swap(array, leftPoint, rightPoint)       //使用swap，則與動態(tài)圖演示效果完全一致    while(leftPoint < rightPoint && array[leftPoint] <= pivot) {      leftPoint++;    }    array[rightPoint] = array[leftPoint]    // swap(array, leftPoint, rightPoint)  }  array[leftPoint] = pivot  return leftPoint;}
const swap = (array, index1, index2)=>{  var aux = array[index1];  array.splice(index1, 1, array[index2])  array.splice(index2, 1, aux)}
const createNonSortedArray = (size)=>{  var array = new Array();  for (var i = size; i > 0; i--) {    //array.push(parseInt(Math.random()*100));    array.push(i*(100/size));    array.sort(function() {      return (0.5-Math.random());    });  }  return array;}
var arr = createNonSortedArray(20);quickSort(arr)console.log(arr)  //[5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100]

時間復(fù)雜度

快速排序很明顯用了分治的思想，關(guān)鍵在于選擇的pivot，如果每次都能把數(shù)據(jù)平分成兩半，這樣遞歸樹的深度就是logN，這樣快排的時間復(fù)雜度為O(NlogN)。

而如果每次pivot把數(shù)組分成一部分空，一部分為所有數(shù)據(jù)，那么這時遞歸樹的深度就是n-1，這樣時間復(fù)雜度就變成了O(N^2)。

根據(jù)以上的時間復(fù)雜度分析，我們發(fā)現(xiàn)如果一個數(shù)據(jù)完全有序，那么使用咱們上面的快速排序算法就是最差的情況，所以怎么選擇pivot就成了優(yōu)化快速排序的重點了，如果繼續(xù)使用上面的算法，那么我們可以隨機選擇pivot來代替數(shù)組首元素作為pivot的方式。

學(xué)習(xí)更多技能

請點擊下方公眾號