algorighm/sort/quick-sort.mjs

import { swap } from '../util/index.mjs';

/**
 *
 * @param {number[]} array - 需要排序的数组
 */
export function quickSort(array) {
  function QuickSort(arr, left, right) {
    if (left < right) {
      const index = partition(arr, left, right);
      QuickSort(arr, left, index - 1); // index是中心轴无需参与排序,若写成index会造成堆栈益处
      QuickSort(arr, index + 1, right);
    }
  }
  QuickSort(array, 0, array.length - 1);
  return array;
}

/**
 * @description 使用左右指针法来分数组
 * @param {number[]} arr - 需要分治的函数
 * @param {number} left - 开始的位置
 * @param {number} right - 结束的位置
 */
function partition(arr, left, right) {
  const pivot = arr[right]; // 以right作为pivot
  const pivotIndex = right;

  while (left < right) {
    // left开始往右边找比pivot大的值
    while (left < right && arr[left] <= pivot) {
      left++;
    }
    // right开始往左边找比pivot小的值
    while (left < right && arr[right] >= pivot) {
      right--;
    }
    swap(arr, left, right);
  }
  swap(arr, left, pivotIndex);
  return left;
}

/**
 *
 * @param {number[]} array - 需要快速排序的数组
 */
export function quickSort2(array) {
  function QuickSort(arr, left, right) {
    if (left < right) {
      const pivot = partition2(arr, left, right);
      QuickSort(arr, left, pivot - 1);
      QuickSort(arr, pivot + 1, right);
    }
  }
  QuickSort(array, 0, array.length - 1);
}

/**
 * @description 使用挖坑法来分数组
 * @param {number[]} arr - 需要分解的数组
 * @param {number} left - 开始的位置
 * @param {number} right - 结束的位置
 */
function partition2(arr, left, right) {
  const pivot = arr[right];
  while (left < right) {
    while (left < right && arr[left] <= pivot) {
      left++;
    }
    arr[right] = arr[left];
    while (left < right && arr[right] >= pivot) {
      right--;
    }
    arr[left] = arr[right];
  }
  arr[left] = pivot;
  return left;
}

/**
 * @description 使用前后指针法分数组
 * @param {number[]} array - 需要排序的数组
 */
export function quickSort3(array) {
  function QuickSort(arr, left, right) {
    if (left < right) {
      const pivot = partition4(arr, left, right);
      QuickSort(arr, left, pivot - 1);
      QuickSort(arr, pivot + 1, right);
    }
  }
  QuickSort(array, 0, array.length - 1);
}

/**
 * @description 使用前后指针法
 * @param {number[]} arr
 * @param {number} left - 开始的位置
 * @param {number} right - 结束的位置
 */
// eslint-disable-next-line no-unused-vars
function partition3(arr, left, right) {
  let cur = left;
  let pre = left - 1;
  const pivot = arr[right]; // 选取最后一个元素作为中枢
  while (cur < right) {
    if (arr[cur] < pivot) {
      swap(arr, cur, ++pre);
    }
    cur++;
  }
  /*
        循环结束之后pre所处的元素之前都是小于pivot（包含pre）,右侧的元素都是大于或等于pivot的，交换cur+1和pviot的值
    */
  swap(arr, pre + 1, right);
  return pre + 1;
}

/**
 * @description 使用前后指针法(优化版)
 * @param {number[]} arr
 * @param {number} left - 开始的位置
 * @param {number} right - 结束的位置
 */
function partition4(arr, left, right) {
  let cur = left;
  let pre = left - 1;
  const pivot = arr[right]; // 选取最后一个元素作为中枢
  while (cur < right) {
    if (arr[cur] < pivot && ++pre !== cur) {
      swap(arr, pre, cur);
    }
    cur++;
  }
  /*
        循环结束之后pre所处的元素之前都是小于pivot（包含pre）,右侧的元素都是大于或等于pivot的，交换cur+1和pviot的值
    */
  swap(arr, pre + 1, right);
  return pre + 1;
}

/**
 * @description 使用非递归方式实现快速排序
 * @param {number[]} arr - 需要排序的数组
 */
export function quickSort4(arr) {
  if (!arr.length || arr.length === 1) return; // 数组为空，或者数组为1，不处理
  const left = 0;
  const right = arr.length - 1;
  const stack = []; // js的数组有push和pop符合栈结构
  stack.push(right);
  stack.push(left);
  while (stack.length) {
    const l = stack.pop(); // 弹出需要处理的左边l
    const r = stack.pop(); // 弹出需要处理的有边界
    const pivot = partition4(arr, l, r);
    // l < pivot - 1 说明还可以分，当l = pivot -1 说明pivot左侧就一个数，说明左侧已经有序了无须再分
    if (l < pivot - 1) {
      stack.push(pivot - 1);
      stack.push(l);
    }
    if (r > pivot + 1) {
      stack.push(r);
      stack.push(pivot + 1);
    }
  }
}

export function quickSort5(arr) {
  const stack = [];
  stack.push(arr.length - 1);
  stack.push(0);
  while (stack.length) {
    const l = stack.pop();
    const r = stack.pop();
    const index = partition4(arr, l, r);
    if (l < index - 1) {
      stack.push(index - 1);
      stack.push(l);
    }
    if (r > index + 1) {
      stack.push(r);
      stack.push(index + 1);
    }
  }
}

/*
    1000000个数据测试下来发现，partition ，partition3和4基本上无区别，而且4只是减少了代码，并没有减少执行
    过程，而且使代码变得难以理解，不推荐使用，推荐使用挖坑法来分数组，
    Function execution time: 464.513192 milliseconds
    Function execution time: 418.692408 milliseconds
    Function execution time: 467.99971000000005 milliseconds
 */