快速排序

TIP

快速排序(Quick Sort)是冒泡排序的升级版，可以说是目前所有排序算法中，最快的一种排序算法。当然，没有任何一种算法是在任意情况下都是最优的。但是，大多数情况下快速排序是比较好的选择

算法描述

快速排序的核心思想是分而治之

• 步骤 1：从数列中挑出一个元素，称为 “基准”、“枢纽” （pivot）
• 步骤 2：重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作
• 步骤 3：递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序

静图演示

动图演示

选取枢纽

选取方案

• 第一种方案：直接选择第一个元素作为枢纽。但是，当第一个元素就是最小值的情况下，效率不高
• 第二种方案：使用随机数。随机数本身十分消耗性能，不推荐
• 优秀的解决方法：
  1. 取 index 为头、中、位的三个数据排序后的中位数
  2. 当（length-1）/2 不整除时可向下或向上取整

如下图所示，按下标值取出的三个数据为：92，43，0，经排序后变为：0，43，92，取其中的中位数 43 作为枢纽

代码编写

// 交换两个位置的数据：用个临时变量中转一次
function swap(arr, m, n) {
  var tmp = arr[m];
  arr[m] = arr[n];
  arr[n] = tmp;
}

// 选择枢纽
function median(arr, left, right) {
  // 1.求出中间的位置
  var center = Math.floor((left + right) / 2);

  // 2.判断大小并且进行交换
  if (arr[left] > arr[center]) {
    swap(arr, left, center);
  }
  if (arr[center] > arr[right]) {
    swap(arr, center, right);
  }
  if (arr[left] > arr[center]) {
    swap(arr, left, center);
  }

  // 3.巧妙的操作: 将center移动到right - 1的位置.
  swap(arr, center, right - 1);

  // 4.返回pivot
  return arr[right - 1];
}

代码测试

var arr = [3, 6, 4, 2, 11, 10, 5];
var pivot = median(arr, 0, 6);
console.log(pivot); // 3
console.log(arr); // [2, 6, 4, 10, 11, 3, 5]

快速排序

递归代码 1

// 快速排序
function quickSort(arr) {
  quick(arr, 0, arr.length - 1);
  return arr;
}
// 递归函数
function quick(arr, left, right) {
  // 1. 递归结束条件
  if (left >= right) return;

  // 2. 获取枢纽
  var pivot = median(arr, left, right);

  // 3. 定义变量，用于记录当前找到的位置
  var i = left;
  var j = right - 1;

  // 4. 开始进行交换
  while (true) {
    while (arr[++i] < pivot) {}
    while (arr[--j] > pivot) {}

    if (i < j) {
      swap(arr, i, j);
    } else {
      break;
    }
  }

  // 5. 将枢纽放到正确的位置，i的位置
  swap(arr, i, right - 1);

  // 6. 分而治之
  quick(arr, left, i - 1);
  quick(arr, i + 1, right);
}

代码说明

• 第一步：获取枢纽
• 第二步：定义两个指针，从前和后两端分别开始往中间移动，不停地交换位置，将数组分成两组
• 第三步：分别针对 左右两组进行递归 1~2 步

代码测试

// 测试快速排序
var arr = [3, 6, 4, 2, 11, 10, 5];
console.log(quickSort(arr).join("-"));
// 2-3-4-5-6-10-11

排序效率

• 快速排序最坏情况下的效率：
  1. 每次选择的枢纽都是最左边或最右边的数据，此时效率等同于冒泡排序，时间复杂度为 O(N²)
  2. 一般会采取取中位数的方式来避免
• 快速排序的平均效率：为 O(N*logN)
• 虽然其他算法效率也可达到 O(N*logN)，但是其中快速排序是最好的

完整代码

/* 快速排序 */

// 交换两个位置的数据：用个临时变量中转一次
function swap(arr, m, n) {
  var tmp = arr[m];
  arr[m] = arr[n];
  arr[n] = tmp;
}

// 选择枢纽
function median(arr, left, right) {
  // 1.求出中间的位置
  var center = Math.floor((left + right) / 2);

  // 2.判断大小并且进行交换
  if (arr[left] > arr[center]) {
    swap(arr, left, center);
  }
  if (arr[center] > arr[right]) {
    swap(arr, center, right);
  }
  if (arr[left] > arr[center]) {
    swap(arr, left, center);
  }

  // 3.巧妙的操作: 将center移动到right - 1的位置.
  swap(arr, center, right - 1);

  // 4.返回pivot
  return arr[right - 1];
}

// 快速排序
function quickSort(arr) {
  quick(arr, 0, arr.length - 1);
  return arr;
}
// 递归函数
function quick(arr, left, right) {
  // 1. 递归结束条件
  if (left >= right) return;

  // 2. 获取枢纽
  var pivot = median(arr, left, right);

  // 3. 定义变量，用于记录当前找到的位置
  var i = left;
  var j = right - 1;

  // 4. 开始进行交换
  while (true) {
    while (arr[++i] < pivot) {}
    while (arr[--j] > pivot) {}

    if (i < j) {
      swap(arr, i, j);
    } else {
      break;
    }
  }

  // 5. 将枢纽放到正确的位置，i的位置
  swap(arr, i, right - 1);

  // 6. 分而治之
  quick(arr, left, i - 1);
  quick(arr, i + 1, right);
}

// 测试中位数选取
var arr = [3, 6, 4, 2, 11, 10, 5];
var pivot = median(arr, 0, 6);
console.log(pivot); // 3
console.log(arr); // [2, 6, 4, 10, 11, 3, 5]

// 测试快速排序
var arr = [3, 6, 4, 2, 11, 10, 5];
console.log(quickSort(arr).join("-"));
// 2-3-4-5-6-10-11