快速排序是一種分治法排序演算法。它的核心概念是選出一個基準值,再把資料分成小於基準與大於等於基準的兩群,最後遞迴排序。
1. 選出一個基準 pivot。
2. 把小於 pivot 的元素放到左邊,大於等於 pivot 的元素放到右邊。
3. 對左右兩邊的子集合重複上述步驟。






var quickSort = function(arr) {
if (arr.length <= 1) {
return arr;
}
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};

快速排序在平均情況下效率很好,但若資料已接近排序完成,或基準值選擇不當,可能會導致效能下降。實務上可加入隨機基準值或三數取中等方式改善。