Quick sort with JavaScript

quickSort.js

/* 快速排序 */

/** 待排序原始数据 */
let data = [4, 10, 14, 11, 17, 8, 13, 15, 12, 2, 6, 9];
let n = data.length;

/** 快速排序 */
function quickSort(data, low, hight) {
  /** 枢轴 */
  let pivot = 0;

  // 递归停止条件为高位索引小于低位索引
  if (hight > low) {
    console.log(data.join(', '));

    // 得到枢轴
    pivot = partition(data, low, hight);
    // 枢轴左边更小规模的问题。都小于枢轴所指的值
    quickSort(data, low, pivot - 1);
    // 枢轴右边更小规模的问题。都大于枢轴所指的值
    quickSort(data, pivot + 1, hight);
  }
}

/**
 * 计算枢轴
 * param data 待排序数据
 * param low 问题左边界
 * param hight 问题右边界
 * return 枢轴
 */
function partition(data, low, hight) {
  /** 将第一个数据选为枢轴所指的值 */
  let pivotElement = data[low];
  /** 从左往右移动的指针，从枢轴下一个元素开始 */
  let left = low + 1;
  /** 从右往左移动的指针，从末尾元素开始 */
  let right = hight;

  // 左右指针不交叉循环
  while (left < right) {

    // 左指针向右，略过小于枢轴所指元素，遇到大于枢轴所指元素则停止移动。
    // 因为需要将所有小于枢轴所指值的元素移动到枢轴左边
    while (data[left] <= pivotElement) {
      left++;
    }

    // 右指针向左，略过大于枢轴所指元素，遇到小于枢轴所指元素则停止移动。
    // 因为需要将所有大于枢轴所指值的元素移动到枢轴右边
    while (data[right] > pivotElement) {
      right--;
    }

    // 如果左右指针未交叉，则交换所指向的值
    // 交叉即左指针大于右指针
    if (left < right) {
      swap(data, left, right);
    }
    
  }

  // 当左右指针交叉时停止迭代
  // 同时将枢轴所指值交换到合适的位置，即右指针所指的位置
  data[low] = data[right];
  data[right] = pivotElement;

  // 至此，枢轴将元素分隔成两部分，
  // 左边小于枢轴所指值的元素，
  // 右边大于枢轴所指值的元素。
  // 返回枢轴位置
  return right;
}

/**
 * 交换数组中两个索引上变量的值
 */
function swap(data, i, j) {
  let tmp = 0;

  tmp = data[i];
  data[i] = data[j];
  data[j] = tmp;
}

quickSort(data, 0, n - 1);

快速排序思想：

• 选择一个元素作为枢轴（选择第一个元素即可）。
• 设置一个指针叫左指针，从枢轴后一个元素开始，从左往右移动。将所指向的值与枢轴相比较，小则略过，大则停止移动。
• 设置一个指针叫右指针，从最末尾一个元素开始，从右往左移动。将所指向的值与枢轴相比较，大则略过，小则停止移动。
• 若左右指针未交叉（即左指针小于右指针），则交换左右指针所指向的元素。
• 若左右指针已交叉（即左指针大于右指针），则交换枢轴和右指针所指元素。且停止迭代。
• 至此，数组已被分割为三部分：[左边小于枢轴元素集合]，枢轴，[右边大于枢轴元素集合]。
• 将枢轴左右两边更小规模的问题继续使用上述方法，直至集合中只有一个元素则完成排序。