快速排序的实现（双指针方法）

概念：

快速排序算法通过多次比较和交换来实现排序，是对冒泡排序的算法的一种改进。（冒泡排序的时间复杂度是0(n*2)）

时间复杂度：

平均时间复杂度为O(N*logN)，比冒泡排序的性能得到很大提升

基本思路：

在数组中选中一个值（或者随机取一个数），一般取第一个或者最后一个作为我们的基准值，所有比我们的基准值小的数都放在基准值的左边，所有比我们基准值大的数都放在我们基准值的右边。这样的我们的以基准值为界限把左右又能分成两个数组，左右两个分组按着同样的方法继续拆分，知道不可分割为止。

实现方案：

我们借用双指针法来帮助我们实现此排序：

1.我们选中数组中的第一个元素作为我们的基准值

2.定一个左指针left和右指针right

3.左指针从数组左边开始查找，直到找到第一个比基准值大的值不再查找

4.右指针从数组右边开始查找，直到找到找到第一个比基准值小的值不再查找

5.如果此时left和right没有相遇（即此时left<right）则把left和right对应的值进行交换

6.如果此时left和right相遇（即此时left=right）则把基准值和left此时的对应值进行交换并返回left

7.此时通过left吧数组分成两个部分，把这两个部分按照相同时做递归处理

图解：

给定数组：[3,5,8,1,2,9,4,7,6]

1、确定基准值 数组中的第一位：arr[0]

2、 从 left 位置开始和基准值 3 比较，直到 left 对应的值比基准值 3 大时停下，否则向右移动，如图因为第一次 left 向右移动对应时的 5 时大于 3 ，所以到 5，left 停下不动；接着从 right 位置开始和基准值 3 比较，直到 right 对应的值比基准值 3 小的时候停下，否则向左移动，如果 right 向左移动 对应的 2 时小于 3 ，所以到 2，right 停下不动。并同时 left<right

3、交换left、right位置

4、接着继续移动，找到 8 比3大， 1 比 3 小，并同时满足 left<right

5、交换left、right位置

6、此时在移动left或者right 会使left>=right,所以此时交互基准值和left值的位置

7、此时根据基准值我们把我们左右数组分成了左右两个部分

8、接下来通过递归左右两个数组做相同操作即可完成最终排序

代码实现：

let array = [3, 5, 8, 1, 2, 9, 4, 7, 6]

function quickSort (arr, left, right) {
  if (left < right) {
    let index = quick(arr, left, right)
    quickSort(arr, left, index - 1)
    quickSort(arr, index, right)
  }
  return arr
}

function quick (arr, left, right) {
  let init = left
  let referenceVal = arr[left]
  left++
  while (left <= right) {
    while (arr[left] < referenceVal) {
      left++
    }
    while (arr[right] > referenceVal) {
      right--
    }
    if (left <= right) {
      [arr[left], arr[right]] = [arr[right], arr[left]]
      left++
      right--
    }
  }
  [arr[init], arr[left - 1]] = [arr[left - 1], arr[init]]
  return left
}


console.log(quickSort(array, 0, array.length - 1));
复制代码

结果呈现：

总结：

以上就是利用双指针法来实现的快速排序，时间复杂度是O(N*logN)