快速排序

快速排序的复杂度是O(nlogn)级别

一般快速排序

// 快速排序
function quickSort(arr) {
  // 从头到尾进行快排
  __quickSort(arr, 0, arr.length - 1);
  // 对 [l, r]区间的元素进行排序
  function __quickSort(arr, l, r) {
    // 递归到底的情况
    if (l >= r) {
      return;
    }
    // 在需要排序的元素数量较少时，可以转为使用插入排序，因为元素数量较少时，插入排序会更快
    // if (r - l <= 15) {
    //   insertSortRange(arr, l, r)
    //   return
    // }
    // 对[l, r]区间的元素进行分隔操作，返回分隔位的索引
    let p = __partition(arr, l, r);
    // 对分隔后的两个区间的元素进行递归排序
    __quickSort(arr, l, p - 1);
    __quickSort(arr, p + 1, r);
  }
  
  // 对[l, r]区间的元素进行分隔操作，返回分隔位的索引p
  // 使得  [l, p-1]区间的元素 < p位置的元素 < [p+1, r]区间的元素
  function __partition(arr, l, r) {
    // 在[l, r]区间中随机取一个元素作为起始元素
    // 当数组近乎有序时，快速排序会退化为O(n^2)级别的算法，选择一个随机位置可以保证复杂度的期望为O(nlogn)
    let random = Math.floor(Math.random() * (r - l) + l);
    // 将随机选到的元素跟l位置的元素进行交换，使得随机位置的元素在最前面
    let begin = arr[random];
    arr[random] = arr[l];
    arr[l] = begin;
    // 交换位置后保存为当前作为参考的元素
    let curi = arr[l];
    // 记录当前中位数的索引，最开始的中位数索引为l
    let j = l;
    // 从第l+1个元素开始遍历比较大小
    for (let i = l + 1; i <= r; i++) {
      // 当前遍历的元素小于参考元素时，将当前元素与 j + 1位置进行交换
      // 遍历之后会得到两个区间，使得左侧的元素 < 参考元素 < 右侧的元素
      if (arr[i] < curi) {
        let mid = arr[i];
        arr[i] = arr[j + 1];
        arr[j + 1] = mid;
        // 交换后左侧的元素增加，中位数位置向后移一位
        j++;
      }
    }
    // 将参考元素换到两个区间的中间，保证最后数组为：[左侧的元素, 参考元素, 右侧的元素]
    arr[l] = arr[j];
    arr[j] = curi;
    // 返回中位数位置的索引
    return j;
  }
  return arr;
}

双路快速排序

一般快速排序在处理大量重复数据的数组时，因为大量重复数据的数组会有很多值和中位数相同，所以会导致划分的两个区间极度不平衡。使用双路快速排序可以解决这种问题。

// 双路快速排序
function quickSortDouble(arr) {
  __quickSortDouble(arr, 0, arr.length - 1);
  // 与一般快速排序一样递归快速排序
  function __quickSortDouble(arr, l, r) {
    if (l >= r) {
      return;
    }
    // 在需要排序的元素数量较少时，可以转为使用插入排序，因为元素数量较少时，插入排序会更快
    // if (r - l <= 15) {
    //   insertSortRange(arr, l, r)
    //   return
    // }
    let p = __partitionDouble(arr, l, r);
    __quickSortDouble(arr, l, p - 1);
    __quickSortDouble(arr, p + 1, r);
  }
  function __partitionDouble(arr, l, r) {
    // 与一般快速排序一样使用随机位置作为参考位
    let random = Math.floor(Math.random() * (r - l) + l);
    let begin = arr[random];
    arr[random] = arr[l];
    arr[l] = begin;
    let curi = arr[l];
    // 定义两个对比位，一个为从前往后，索引为l+1，一个从后往前，索引为r
    // 双路快速排序实际是将右半区的元素搬到了数组的末尾，两个索引分别为左半区的结束位置和右半区的起始位置
    let i = l + 1,
      j = r;
    // 在循环体内部判断循环结束的条件
    while (true) {
      // 下面两个while实际上是把和参考为相等的元素分散在了左右两个区间中，这样就不会出现和参考位相等的数据过多时
      // 两个区间大小极度不平衡的情况。
      // 参考位的元素大于i位置的元素时，不用处理
      while (i <= r && arr[i] < curi) {
        i++;
      }
      // 参考位的元素小于j位置的元素时，不用处理
      while (j >= l + 1 && arr[j] > curi) {
        j--;
      }
      // 判断循环结束条件，遍历结束跳出
      if (i > j) {
        break;
      }
      // 交换当前正在对比的i和j位置，保证左侧元素 < 参考位元素 < 右侧元素
      let mid = arr[i];
      arr[i] = arr[j];
      arr[j] = mid;
      i++;
      j--;
    }
    // 两个区间都排序完成时，将参考位置元素和j位置元素交换，即将参考位置元素放到两个区间中间
    // 使得数组为：[左侧元素，参考位元素，右侧元素]
    let mid = arr[l];
    arr[l] = arr[j];
    arr[j] = mid;
    // 返回最终参考位，即中位数位置的索引
    return j;
  }
  return arr;
}

三路快速排序

三路快速排序和双路快速排序一样对大量重复数据的数组做了优化

// 三路快速排序
function quickSortThrid(arr) {
  // 与一般快速排序一样递归快速排序
  __quickSortThrid(arr, 0, arr.length - 1);
  function __quickSortThrid(arr, l, r) {
    if (l >= r) {
      return;
    }
    // 在需要排序的元素数量较少时，可以转为使用插入排序，因为元素数量较少时，插入排序会更快
    // if (r - l <= 15) {
    //   insertSortRange(arr, l, r)
    //   return
    // }
    // 与一般快速排序一样使用随机位置作为参考位
    let random = Math.floor(Math.random() * (r - l) + l);
    let begin = arr[random];
    arr[random] = arr[l];
    arr[l] = begin;
    let curi = arr[l];
    // 定义3个对比位，使得左侧元素为[l, lt]，右侧元素为[gt, r]，i为当前对比位
    // 三路快速排序实际是将等于参考位的元素也划分为了一个区间放在中间
    let lt = l;
    let gt = r + 1;
    let i = l + 1;
    // 当遍历到gt位置，即遍历到右区间时，结束遍历
    while (i < gt) {
      // 当前对比位的元素小于参考位的元素时，将对比位元素和中间区间的第一个元素进行交换
      if (arr[i] < curi) {
        let mid = arr[lt + 1];
        arr[lt + 1] = arr[i];
        arr[i] = mid;
        // 左侧区间像后移一位，这样交换过来的对比位元素就成为了左侧区间的最后一个元素
        lt++;
        // 对比位向后移一位对比下一个元素
        i++;
      } else if (arr[i] > curi) {
        // 当前对比位元素大于参考位元素时，将对比位元素和右侧区间的第一个元素进行交换
        let mid = arr[gt - 1];
        arr[gt - 1] = arr[i];
        arr[i] = mid;
        // 只需要将右侧区间起始位像前移动一位，对比位元素因为是从右侧区间交换过去的，所以不需要动
        gt--;
      } else {
        // 当前对比位元素等于参考位元素时，直接不作处理对比下一个元素
        // 这样自然就将等于参考位的元素都放在了中间区域
        i++;
      }
    }
    // 最后将参考位元素和左侧区间的最后一个元素进行交换
    // 使得数组为：[左侧元素，中间区域元素，右侧元素]
    let mid = arr[lt];
    arr[lt] = arr[l];
    arr[l] = mid;
    __quickSortThrid(arr, l, lt - 1);
    __quickSortThrid(arr, gt, r);
  }
  return arr;
}