JS实现快速排序

看了一篇通俗易懂的快排文章 快排，下面一步一步 实现整个过程。

快排的基本思想

上面链接的文章对快排的思路提出了一个很形象的概念：挖坑填数 + 分治法，分三个步骤实现：

1. 从数组中取出一个数作为基准(pivot)。
2. 在原数组中进行移动，将大于基准的数放到基准右边，小于基准的数放到基准左边，在基准左右形成两个子数组。
3. 在左右子数组中反复执行步骤1、2，直到所有子数组只剩下一个数。

详细步骤

初始数组如下所示，取第一个数为基准，此时：i = 0， j = 9， pivot = arr[0] = 36，此时 i = 0 的位置就挖了一个坑，等待小于36的数来填这个坑。i 先不变，j-- 从后往前找小于基准的数：

---

i = 0， j = 8 时，24 < 36，将 arr[8] 挖出，放入 arr[0] 的“坑中”（实际上在写程序时，是 arr[8] 与 arr[0] 交换）。接着arr[8] 的坑怎么填？调换顺序从前往后找比基准大的数（i++，j 不变）：

---

i = 3， j = 8 时，43 > 36，将 arr[3] 挖出，放入 arr[8] 的“坑中”。接着去找数填 arr[3] 的坑，调换顺序从后往前找比基准小的数：

---

i = 3， j = 5 时，20 > 36，反向查找：

---

i = j = 5 时，退出，第一趟排序完成，以 arr[5] = 36 为界分为左右两个子数组：

---

接着在左右两个子数组中重复上面的排序过程，直到每个子数组的长度为1，排序结束！下面只给出每一步的执行结果：

---

JS代码

// 交换元素
function swap(arr, i , j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp; 
}

// 快排
function quickSort(arr, i, j) {
  if(i < j) {
    let left = i;
    let right = j;
    let pivot = arr[left];
    while(i < j) {
      while(arr[j] >= pivot && i < j) {
        j--;
      }
      if(i < j) {
        swap(arr, i , j);
        i++;
      }
      while(arr[i] <= pivot && i < j) {
        i++;
      }
      if(i < j) {
        swap(arr, i , j);
        j--;
      }
    }
    arr[i] = pivot;
    quickSort(arr, left, i-1);
    quickSort(arr, i+1, right);
    return arr;
  }
}
// example
let arr = [2, 10, 4, 1, 0, 9, 5 ,2];
alert(quickSort(arr, 0 , arr.length-1));