[数据结构与算法]JS双指针快速排序

1. 快速排序是什么

   • 快速排序的本质思想是二分法，先找出一个基准值，经过一个遍历后，把比基准值小的数据放在左面，大的放在右面，再将分好的左面和右面的依次进行这种操作。

2. 时间复杂度

   • 因为是二分法，所以时间复杂度是$Ologn$，代表数据增大n倍，耗时增加 $Ologn$ 倍。
   • 大$O$加上()的形式，里面包裹的是一个函数f()，$O(f())$ 代表某个算法的耗时或耗空间与n(数据量)增长之间的关系。比如数据n增大256倍，$log$以2为底256的对数是8，所以耗时只需增加8倍。

3. 实现

• 快速排序是面试经常问到的一种排序算法，我们来梳理下思路。
  现在有个数组，首先找到一个基准值，可以将头部的当做基准值，也可以将尾部的当做基准值，我们取头部的当做基准值，定义一个temp指向头部。然后声明两个指针，一个left指向头部，一个right指向尾。right指针找比基准值小的，left指针找比基准值小的，交换两个指针的数字，再继续移动两个指针直到他们两个相遇，再交换temp和他们停下来指的位置。

const arr = [3, 6, 1, 2, 5, 4]

先移动right指针，right指向5，比3大，接着移动，指向2，比3小，停止。再移动left指针，指向6，比3大，停止。

接着交换两个指针所指向的值。

right接着向左移动，指向1，比3小，停止。left向右移动，指向1，这时left和right相遇了，证明整个数组都被遍历了一遍，此时把temp和left right指向的数字交换。

到此时，第一轮的遍历结束，将数组分成了两部分，3左边的数字都是比3小的，右边都是比3大的。再次重复刚才的步骤，接着对左侧和右侧两个数组排序，不断的二分下去。

right和left相遇，和temp指向同一个，左侧排序结束。接着右侧。

right指向的4比temp指向的6小，停止。移动left，指向5，比6小，继续移动，指向4，和right相遇。交换两个值。

排序结束。

过程就是这样，接下来代码实现下。

function quickSort(arr, begin, end) {
  if (begin >= end) {
      return
  }
  let temp = arr[begin];
  let left = begin;
  let right = end;
  while(right > left) {
      while(right > left && arr[right] >= temp) {
          right--;
      }
      while(right > left && arr[left] <= temp) {
          left++;
      }
      [arr[left], arr[right]] = [arr[right], arr[left]];
  }

  [arr[begin], arr[right]] = [arr[right], arr[begin]];
  quickSort(arr, begin, right - 1);
  quickSort(arr, right + 1, end);
  return arr;
}
const arr = [3, 6, 1, 2, 5, 4];
const result = quickSort(arr, 0, arr.length - 1);
console.log(result);