唠唠快速排序算法

[originalix]

每一个从事计算机相关方向工作的同学一定听说过快速排序算法，在面试的准备过程中，快排也一定是一个必须要牢牢掌握的算法。那么今天就来唠唠快速排序算法。

快速排序算法又称划分交换排序，简称快排，是一种排序算法。在平均状态下排序n个项目需要O(nlogn)次比较，在最坏的情况下则需要O(n^2)次比较，不过这种情况并不常见。事实上呢，快速排序通常要比其他算法更快，因为它的内部循环可以在大部分的架构上很有效率地达成。

快速排序的动画演示：

快速排序算法采用的是分治法的思想，将一个完整的待排序的序列一分为二，分而治之，并递归的对子序列继续排序。

可以这么简单的描述快速排序的步骤：

1、从数组中随机的选择一个元素，称之为“基准” （pivot）。

2、从数组中按顺序取出元素与基准比较，如果取出的元素比基准小，则放置入基准之前的数组，而如果取出的元素比基准大，则放入基准之后的数组，如果取出的元素与基准相等，则与基准放置于同一数组中。该操作可以称之为分区（partition）操作。

3、在第一遍排序完之后，再递归的对基准之前的数组与基准之后的两个数组进行排序，直至拆分至最小的数组大小，则可视为排序完成，按照调用栈返回结果。则排序完成。

介绍完步骤之后，来看看用javaScript如何来实现快速排序：

/**
 *  快速排序算法
 *  最优时间复杂度 O(nlogn)
 *  平均时间复杂度 O(nlogn)
 *  最坏时间复杂度 O(n^2)
 *  是否稳定 否
 */
class QuickSort {
  sort(originalArray) {
    const array = [...originalArray];

    // 如果数组小于等于一个元素的时候就返回，可以理解为已经排好序
    if (array.length <= 1) {
      return array;
    }

    // 定义左右两个数组
    const leftArray = [];
    const rightArray = [];

    // 取出第一个元素作为比较对象
    const pivotElement = array.shift();
    const centerArray = [pivotElement];

    // 把数组切分为左中右三部分
    while (array.length) {
      const currentElement = array.shift();

      if (currentElement === pivotElement) {
        centerArray.push(currentElement);
      } else if (currentElement < pivotElement) {
        leftArray.push(currentElement);
      } else {
        rightArray.push(currentElement);
      }
    }

    // 对左右两个数组递归排序
    const leftSortedArray = this.sort(leftArray);
    const rightSortedArray = this.sort(rightArray);

    // 将返回的已经排好序的左中右三个数组合并 完成排序
    return leftSortedArray.concat(centerArray, rightSortedArray);
  }
}

// 排序测试
const array = [6, 10, 1, 9, 4, 8, 2, 7, 3, 5];
const quick = new QuickSort();
const res = quick.sort(array);
console.log(res);

最后温馨的提醒各位同学，一定要牢牢的掌握快速排序算法，直到能随意白板手写快排为止。

javaScript版快排源码