思路大纲

  1. 排序的二分位置函数(随机性)
  2. 交换两个下标的元素函数
  3. 遍历比较/交换元素的函数
  4. 随机的中位置换函数
  5. 快排函数

二分位置函数(随机)

  1. function randomIndex(minIndex, maxIndex) {
  2.     const _min = Math.ceil(minIndex);
  3.     const _max = Math.floor(maxIndex);
  4.     return Math.floor(Math.random() * (_max - _min)) + _min;
  5. };

交换两个下标的元素函数

  1. function swap(arr, minIndex, maxIndex) {
  2.     [
  3.       arr[minIndex],
  4.       arr[maxIndex]
  5.     ] = [
  6.       arr[maxIndex],
  7.       arr[minIndex]
  8.     ];
  9. };

遍历比较/交换元素的函数

  1. function partition(arr, leftIndex, rightIndex) {
  2.   // 默认最右侧元素为最大,leftIndex~rightIndex中的元素都跟它比较
  3.   // 大的排前面,小的排后面
  4.     const right = arr[rightIndex];
  5.   // 哨兵位置。在leftIndex之前
  6.   // 如果完成后,index还是不变,就需要将rightIndex移动到leftIndex,说明right是最大的
  7.   let index = leftIndex - 1;
  8.   // 以leftIndex做遍历起始点,遍历leftIndex~rightIndex中间的数字
  9.   for (let i = leftIndex; i < rightIndex; i++) {
  10.     // 如果当前遍历元素，大于最大的元素
  11.       if (arr[i] > right) {
  12.       // 将哨兵位移后一位
  13.         ++index;
  14.       // 将当前大的元素,移动到哨兵位
  15.       swap(arr, index, i);
  16.     }
  17.   }
  18.   const lastIndex = index + 1;
  19.   // 两种情况
  20.   // 1.rightIndex的元素是这个范围内最大的,就将rightIndex元素移动到这个范围起始位置
  21.   // 2.index到了某个位置后,就没有比right大的了,就将rightIndex移动到那个位置
  22.   swap(arr, lastIndex, rightIndex);
  23.   // 将当前移动的排序后的最大位置的坐标返回出去,供下一轮新的排序
  24.   return lastIndex;
  25. }


随机的中位置换函数

  1. // 只是为了需要一种随机性,不用它,对结果也是没有影响
  2. function randomPartion(arr, leftIndex, rightIndex) {
  3.   // 获取到leftIndex~rightIndex中随机的位置
  4.     const pivot = randomIndex(leftIndex, rightIndex);
  5.   // 将随机位跟rightIndex的位置交换
  6.   swap(arr, pivot, rightIndex);
  7.   // 进行排序
  8.   return partition(arr, leftIndex, rightIndex);
  9. }

快排函数

  1. function randomQuickSort(heap, leftIndex, rightIndex) {
  2.   // 首先必须是两个元素及以上的数组
  3.     if (leftIndex < rightIndex) {
  4.     // 首先将当前范围的数组分成两部分排序,得到这个分离下标
  5.       const q = randomPartion(heap, leftIndex, rightIndex);
  6.     // 以分离下标的作为最大的范围继续遍历
  7.     randomQuickSort(heap, leftIndex, q - 1);
  8.     // 以分离下标最为起始范围遍历
  9.     randomQuickSort(heap, q + 1, rightIndex);
  10.   }
  11. }
  13. /**
  14. * 例子: const heap = [9, 1, 0, 10, 5, 7, -1, -3, 2];
  15. * 开始遍历时,假设当前的随机的中位下标为4,就是元素5.
  16. * 那第一遍遍历的时候,就是将rightIndex(8) 与下标4进行交换. 5 与 2进行交换
  17. * heap = [9, 1, 0, 10, 2, 7, -1, -3, 5];
  18. * 第一次遍历将元素5作为最大值,排序后的数组应该为
  19. * heap = [9, 10, 7, 5, 2, 0, -1, -3, 1]; q = 3;
  20. * 这个时候可以清晰看到,数组被中位元素2分成了两部分,5之前的都是大于5的，5之后的都是小与5的
  21. * left = [9, 10, 7], right = [2, 0, -1, -3, 1],这个时候不会取到5,因为5就是分隔元素
  22. * 如果循环递归,就能得到排序后的数
  23. */