1.每一轮排序选择一个基准点进行分区
1.1 让小于基准点的元素进入一个分区，大于基准点的元素进入另一个分区
1.2 当分区完成时，基准点元素的位置就是最终位置
2.在子分区内重置以上过程，直至子分区元素个数小于等于1。该算法提现的是分而治之的思想
一、单边循环快排（lomuto洛穆托分区方案）
1.选择最右边元素作为基准点元素
2.j指针负责找到比基准点小的元素，一旦找到则与i进行交换
3.i指针维护小于基准点元素的边界，也是每次交换的目标索引
4.最后基准点与i交换，i即为分区位置
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
}
// 递归循环
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)
// 进行左侧分区范围确定
quickSort1(arr, start, index - 1)
// 进行右侧分区范围确定
quickSort1(arr, index + 1, end)
}
}
// 交换两个值
function swap(arr, i, j) {
var tmp = arr[i]
arr[i] = arr[j]
arr[j] = tmp
}
二、双边循环快排
1.选择最左边作为基准点元素
2.j指针负责从右向左找到比基准点小的元素，i指针负责从左向右找到比基准点大的元素，一旦找到二者交换，直到i、j相交
3.最后基准点与i（此时i与j相等）交换，i即为分区位置
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)
// 进行左侧分区范围确定
quickSort(arr, start, index - 1)
// 进行右侧分区范围确定
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
}
双边循环的要点：
1.基准点取左边的值，并且要先右后左
2.while (i < j && arr[j] > tmp) j--
3.while (i < j && arr[i] <= tmp) i++
