基础算法复习——快速排序

1. 最近一直在忙课程，每天只能抽空刷几道LeetCode，好久没看JS了...有点慌，但是先抽空把排序算法啥的写一遍吧，等忙完操作系统课设再好好复习JS.

2. 快速排序算法思想大概就是设定一个基准值，根据基准值不断地交换数组中前后的元素值，在此过程中目的是把基准值排序到最终的位置，再对基准值位置之前和之后的数组元素重复以上过程。

（1）给定一个数组 arr，首先寻找它的基准值 base.

（2）设置指针 low 指向指定数组范围首元素，high 指向指定数组范围末尾元素，并设置变量 left 和 right 保存 low 和 high 的值，因为 low 和 high 之后会变化

（3）只要满足 low < high，则循环进行下面操作：

　　从 high 开始判断，如果 arr[ high ] 大于 base 值，且 low < high，则 high--；

　　若小于 base 值，则 arr[ low ] = arr[ high ]，

　　并且改换为从 low 判断，如果 arr[ low ] 小于 base 值，且 low < high，则 low++；

　　若大于 base 值，则 arr[ high ] = arr[ low ]

（4） 循环结束时，条件必定是 low === high，此时 low 处或 high 处就是 base 基准值最终的位置

（5）我们对数组 [ left, low - 1] 和 [ low + 1, right ] 两个范围元素递归进行 （1）~（4）过程，最终得到的数组即为排序后数组。

 TypeScript 代码：

function quickSort(arr: number[]) {
  function sort(arr: Array, low: number = 0, high: number = arr.length - 1) {
    if (low >= high) {
      return;
    }
    const left: number = low, right: number = high;
    let base: number = arr[low];
    while (low < high) {
      while (low < high && arr[high] > base) {
        high--;
      }
      arr[low] = arr[high];
      while (low < high && arr[low] < base) {
        low++;
      }
      arr[high] = arr[low];
    }
    arr[low] = base;
    sort(arr, left, low - 1);
    sort(arr, low + 1, right);
  }
  const arr_clone: Array = Array.from(arr);
  sort(arr_clone);
  return arr_clone;
}
let wait_sort: number[] = [15,6,-4,8,99,-45,26,0];
console.log(quickSort(wait_sort));