快速排序(Quick Sort)是公認效能優秀的排序演算法之一,它的思想其實很簡單,整個排序過程可以拆成三個步驟:
下面是一個可以直接運行的示範:
<script type="text/javascript"> function quickSort(arr){ if(arr.length<=1){ return arr;//如果數組只有一個數,就直接返回; } var num = Math.floor(arr.length/2);//找到中間數的索引值,如果是浮點數,則向下取整 var numValue = arr.splice(num,1);//找到中間數的值 var left = []; var right = []; for(var i=0;i<arr.length;i++){ if(arr[i]<numValue){ left.push(arr[i]);//基准點的左邊的數傳到左邊數組 } else{ right.push(arr[i]);//基准點的右邊的數傳到右邊數組 } } return quickSort(left).concat([numValue],quickSort(right));//遞歸不斷重復比較 } alert(quickSort([32,45,37,16,2,87]));//彈出“2,16,32,37,45,87” </script> 來逐段理解這段程式:
Math.floor 向下取整取得索引,再用 splice 把它從原陣列取出。concat 把「排好序的左半 + 基準 + 排好序的右半」拼接起來,而左右兩半又各自遞迴呼叫 quickSort。就這樣透過不斷地「分而治之」,最終得到完整且有序的結果。快速排序的平均時間複雜度為 O(n log n),是實作簡潔又高效的經典範例。