js实现空间复杂度为O(1)的快排-一一网

看了各种快排实现，想寻找一种空间复杂度为O(1)的实现，无奈没有找到合适的。
因此想自己动手试试，半个小时过去没有半点进展。
想起曾经收藏过一个算法可视化网站Data Structure Visualizations。
进去看了下快排的排序过程
（点击Comparison Sorting进入）

再点击”Quick Sort”。
默认展示速度太快，看不出来思路。将速度调至最慢：

慢慢发现思路：

以第一个元素作为pivot(基准), 设置两个指针i, j
i从第二个开始；j从最后开始
如果第i个元素小于pivot, 则i++; 如果大于pivot, 则判断第j个元素
如果第j个元素大于pivot, 则j–；如果小于等于则交换第i, j个元素；并i++, j–
重复第3步，直到i > j
此时第i个元素肯定大于等于pivot, 第i – 1个元素小于pivot；
因此交换pivot和第i – 1个元素（让数组做到小于pivot的在其左边，大于等于pivot的在其右边）
接着就再对左右两边再次执行1-6步即可

代码实现（结合动图食用效果更佳）：

function swap(arr, i, j) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

function divide(arr, start, end) {
  const pivot = arr[start];
  
  let i = start + 1;
  let j = end;
  while (i <= j) {
    if(arr[i] < pivot) {
      i++;
    } else if(arr[j] > pivot) {
      j--;
    } else {
      swap(arr, i++, j--);
    }
  }
  swap(arr, start, i - 1);
  return i - 1;
}

function quickSort(input, start, end) {
  if (start < end) {
    const pivot = divide(input, start, end);
    quickSort(input, start, pivot - 1);
    quickSort(input, pivot + 1, end);
  }
  
  return input;
}
复制代码

下面附上一些测试代码：

// 创建随机数组
function createArr(size) {
  const arr = [];
  for(let i = 0; i < size; i++) {
    const num = Math.floor(Math.random() * size);
    arr.push(num);
  }
  return arr;
}
// 创建一个长度100000的数组
const arr = createArr(100000);

const startTime = Date.now();
quickSort(arr, 0, arr.length - 1);
console.log(Date.now() - startTime);

// console.log(arr);
复制代码