1.每一輪排序選擇一個基準點進行分區(qū)
1.1 讓小于基準點的元素進入一個分區(qū)饱亿，大于基準點的元素進入另一個分區(qū)
1.2 當分區(qū)完成時闰靴，基準點元素的位置就是最終位置
2.在子分區(qū)內重置以上過程，直至子分區(qū)元素個數(shù)小于等于1配猫。該算法提現(xiàn)的是分而治之的思想
一膘掰、單邊循環(huán)快排（lomuto洛穆托分區(qū)方案）
1.選擇最右邊元素作為基準點元素
2.j指針負責找到比基準點小的元素，一旦找到則與i進行交換
3.i指針維護小于基準點元素的邊界识埋，也是每次交換的目標索引
4.最后基準點與i交換，i即為分區(qū)位置
window.onload = function() {
var arr = [2,4,9,1,7,3,6,8,5]
// 快速排序
quickSort(arr)
}
// 單邊快排
function partition1(arr, left, right) {
var tmp = arr[right] // 取最右側的為基準值
var i = left
for (let j = i; j < right; j++) {
if (arr[j] < tmp) {
if (i != j) {
swap(arr, i, j)
}
i++
}
}
if (i != right) {
swap(arr, right, i)
}
return i
}
// 遞歸循環(huán)
function quickSort1(arr, left, right){
var start = left || 0
var end = right != undefined ? right : arr.length - 1
if (start < end) {
// 進行一輪后基準值所在位置的索引
var index = partition1(arr, start, end)
// 進行左側分區(qū)范圍確定
quickSort1(arr, start, index - 1)
// 進行右側分區(qū)范圍確定
quickSort1(arr, index + 1, end)
}
}
// 交換兩個值
function swap(arr, i, j) {
var tmp = arr[i]
arr[i] = arr[j]
arr[j] = tmp
}
二、雙邊循環(huán)快排
1.選擇最左邊作為基準點元素
2.j指針負責從右向左找到比基準點小的元素惠豺，i指針負責從左向右找到比基準點大的元素，一旦找到二者交換蛹疯，直到i热监、j相交
3.最后基準點與i（此時i與j相等）交換，i即為分區(qū)位置
window.onload = function() {
var arr = [2,4,9,1,7,3,6,8,5]
// 快速排序
quickSort(arr)
}
// 雙邊快速排序
function partition(arr, left, right) {
var tmp = arr[left] // 取左側為基準值
var i = left
var j = right
while (i < j) {
// 先從右向左找小的
while (i < j && arr[j] > tmp) {
j--
}
// 從右向左找大的
while (i < j && arr[i] <= tmp) {
i++
}
// 交換大小值的位置,將小的放在左邊,大的放在右邊
swap(arr, i, j)
}
// 將基準值填入坑里
swap(arr, left, i)
return i
}
function quickSort(arr, left, right) {
var start = left || 0
var end = right !== undefined ? right : arr.length - 1
if (start < end) {
// 進行一輪后基準值所在位置的索引
var index = partition(arr, start, end)
// 進行左側分區(qū)范圍確定
quickSort(arr, start, index - 1)
// 進行右側分區(qū)范圍確定
quickSort(arr, index + 1, end)
}
console.log(arr)
return arr
}
// 交換兩個值
function swap(arr, i, j) {
var tmp = arr[i]
arr[i] = arr[j]
arr[j] = tmp
}
雙邊循環(huán)的要點：
1.基準點取左邊的值列吼，并且要先右后左
2.while (i < j && arr[j] > tmp) j--
3.while (i < j && arr[i] <= tmp) i++
