快速排序

1. 原理
   （1）从一个数列中选出一个「基准」
   （2）然后遍历所有元素，把所有比这个「基准」小的元素放在「基准」的左边，所有比「基准」大的元素放在「基准」的右边，如果与「基准」相等，随意放哪边。一轮分区下来，这样会是该「基础」处于整个数列的中间位置。
   （3）递归地，把小于基准值元素的子数列和大于基准值元素的子数列排序。
   （4）递归到最底部时，数列的长度只有0或者1，即本身就是排好序的。这个算法一定会结束，因为在每次的迭代中，它至少会把一个元素摆到它最后的位置去。

2. 代码

function quickSort(arr) {
    function __quickSort__(arr, start, end) {
        if(start >= end) return;
        let key = arr[end];
        let left = start;
        let right = end - 1;
        while(left < right){
            while( arr[left] < key && left < right) left++;
            while( arr[right] > key && left < right) right--;
            [arr[left], arr[right]] = [arr[right], arr[left]];
        }
        if(arr[left] >= key) {
            [arr[left], arr[end]] = [arr[end], arr[left]];
        } else {
            left++;
        }
        __quickSort__(arr, start, left - 1);
        __quickSort__(arr, left + 1, end);
    }
    __quickSort__(arr, 0, arr.length - 1 );
    return arr;
}

• 本代码，以最后一个数为「基准」（key值）
• 从数列首位开始遍历，如果遇到比key小的数，则继续向后扫描，直到遇到比key值大的元素，然后从key值前一个元素开始从后向前扫描，直到遇到比key值小的元素
• 此时交换位置停止的两个元素
• 继续上面的逻辑
• 直到left和right相遇
• 如果相遇时的值大于或者等于key值，则把该相遇的值与key值互换位置
• 如果相遇时的值小于key值，则把left后移一位。

参考：https://zhuanlan.zhihu.com/p/46189099