标准快排排序

快速排序的逻辑示意图 这是示意图并不是完整的代码逻辑示意图只是第一次数组循环的示意图


参考代码

const arr = [4, 1, 6, 9, 3, 2, 8, 7]
/**
 * 数组两位互相交换位置
 * @param {Array} arr 
 * @param {Number} a 
 * @param {Number} b 
 */
function exchange(arr, a, b) {
    let temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
/**
 * 标椎排序
 * @param {Array} arr 数组 
 * @param {*} begin
 * @param {*} end 
 */
function quickSor(arr, begin, end) {
    if (begin >= end - 1) return;
    let left = begin;
    let right = end;
        // 只进行第一次循环
      // do while  的运行顺序， 先运行do 里语句 之后在while 进行判断为true再次执行do里语句，当为false时停止循环
    do {
        do left++; while (left < right && arr[left] < arr[begin])
        do right--; while (right > left && arr[right] > arr[begin])
        if (left < right) exchange(arr, left, right)
    } while (left < right); //判断第一次循环是否结束
    let temp = left == right ? right - 1 : right;
    exchange(arr, begin, temp)
}
quickSor(arr, 0, arr.length)
console.log(arr)

控制台打印效果

案例

const arr = [4, 1, 5, 6, 2, 3, 9, 7]
/**
 * 数组两位互相交换位置
 * @param {Array} arr 
 * @param {Number} a 
 * @param {Number} b 
 */
function exchange(arr, a, b) {
    let temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
/**
 * 标椎排序
 * @param {Array} arr 数组 
 * @param {*} begin
 * @param {*} end 
 */
function quickSor(arr, begin, end) {
    if (begin >= end - 1) return;
    let left = begin;
    let right = end;
    do {
        do left++; while (left < right && arr[left] < arr[begin])
        do right--; while (right > left && arr[right] > arr[begin])
        if (left < right) exchange(arr, left, right)
    } while (left < right);
    let temp = left == right ? right - 1 : right;
    exchange(arr, begin, temp)
    quickSor(arr, begin, temp);
    quickSor(arr, temp + 1, end)
}
quickSor(arr, 0, arr.length)
console.log(arr)

控制台打印效果