核心思想： 分而治之。以基准值划分数组， 以此迭代
image.png

  1. 选取第一个为基准值
  2. 遍历， 交互，最终达到， […小于基准值, 基准值, 大于基准值]
  3. 划分为相同更小的问题

    指针交换法

    ``` function quickSort(arr, start, end) { if (start >= end) return; let pivotIndex = partition(arr, start, arr.length - 1); quickSort(arr, start, pivotIndex-1); quickSort(arr, pivotIndex+1, arr.length - 1); }

function partition(arr, start, end) { var pivot = arr[start]; let left = start, right = end; while (left < right) { while (left < right && arr[right] > pivot) right—; while (left < right && arr[left] <= pivot) left++; if (left < right) { [arr[left], arr[right]] = [arr[right], arr[left]] } } [arr[start], arr[left]] = [arr[left], arr[start]] return left; }

  1. <a name="E9tYm"></a>
  2. #### 挖坑法

function quickSort(arr, start, end) { if (start >= end) return; let pivotIndex = partition(arr, start, arr.length - 1); quickSort(arr, start, pivotIndex-1); quickSort(arr, pivotIndex+1, arr.length - 1); }

function partition(arr, start, end) { var pivot = arr[start]; let left = start, right = end; while (left < right) { while (left < right && arr[right] > pivot) right—; if (left < right) { arr[left] = arr[right]; left++; } while (left < right && arr[left] <= pivot) left++; if (left < right) { arr[right] = arr[left]; right—; } } arr[left] = pivot; return left; }

<a name="ssALD"></a>
#### 非递归法
参考：<br />[漫画：什么是快速排序？（完整版）](https://www.cxyxiaowu.com/5262.html)
<a name="GYAGO"></a>
### 练习1:
<a name="etj7g"></a>
#### [剑指 Offer 40. 最小的k个数](https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/)



<a name="EGjYF"></a>
#### [215. 数组中的第K个最大元素](https://leetcode-cn.com/problems/kth-largest-element-in-an-array/)

var findKthLargest = function(nums, k) { // 快速排序 // 目标第nums.length - k const len = nums.length; if (len == 1) return nums[0]; k = len - k; let start = 0; let end = len - 1; while (start <= end) { let p = partition(nums, start, end); if (p == k ) { return nums[p]; } if (p > k) { end = p-1; } else { start = p+1; } } return -1; };

function partition(arr, start, end) { if (start >= end) return start; let pivot = arr[start]; while (start < end) { while(start < end && arr[end] >= pivot) end—; if (start < end) { arr[start] =arr[end]; start++; } while (start < end && arr[start] < pivot) start++; if (start < end) { arr[end] =arr[start]; end—; } } arr[start] = pivot; return start; } ``` 快速排序： 70， 53
选择排序： 20， 50
时间提高明显

参考：
https://mp.weixin.qq.com/s/TRO3FOKT90Mpvn3hQWVBAQ