快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列 .

​

1. 从数列中挑出一个元素，称为”基准”(pivot)。

2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

   递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

// 分区 找到中心点, 小的往前 大的往后, 返回中心点
function partition(arr, low, height) {
    let pivot = arr[height];
    let k = low - 1;
    for (let i = low; i < height; i++) {
        if (arr[i] <= pivot) {
            k++;
            let temp = arr[k];
            arr[k] = arr[i];
            arr[i] = temp;
        }
    }

    // 把中心点拖过去
    let temp = arr[k + 1];
    arr[k + 1] = arr[height];
    arr[height] = temp;

    return k + 1;
}

// 排序
function quickSort(arr, low, height) {
    if (low < height) {
        let pi = partition(arr, low, height)
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, height);
    }
}



let arr = [800, 711, 82, 39, 111, 45];
quickSort(arr, 0, arr.length - 1)
console.log(arr)