快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

    • 从数列中挑出一个元素，称为 “基准”（pivot）；
    • 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
    • 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

    https://leetcode-cn.com/submissions/detail/117244196/

    1. function quickSort(arr: number[]) {
    2.     quick(arr, 0, arr.length - 1)
    3. }
    5. function quick(arr: number[], left: number, right: number) {
    6.     const index = partition(arr, left, right)
    7.     if(index - 1 > left) {
    8.         quick(arr, left, index - 1)
    9.     }
    11.     if(index < right) {
    12.         quick(arr, index, right)
    13.     }
    14. }
    16. // 以一个数为基准 将大于基数的元素移到右边 小于基数的元素移到左边
    17. function partition(arr: number[], left: number, right: number): number {
    18.     // 取随机值为基准
    19.     const random = arr[Math.floor(Math.random() * (right - left + 1)) + left]
    20.     let i = left, j = right
    21.     while(i <= j) {
    22.         // 左边大于基准的值
    23.         while(arr[i] < random) {
    24.             i++
    25.         }
    27.         // 右边小于基准的值
    28.         while(arr[j] > random) {
    29.             j--
    30.         }
    32.         // 交换
    33.         if(i <= j) {
    34.             swap(arr, i, j)
    35.             i += 1
    36.             j -= 1
    37.         }
    38.     }
    39.     return i
    40. }
    42. // 交换数组元素
    43. function swap(arr: number[], i: number, j: number) {
    44.     let temp = arr[i]
    45.     arr[i] = arr[j]
    46.     arr[j] = temp
    47. }