通过遍历将序列分成左右两个部分，左边的小(大)于等于右边,然后对左边的和右边的继续进行分隔，直到不能分隔
    算法流程：
    1、确定一个基准(一般来说是第一个或者最后一个元素，当然也可以算计)
    2、通过这个基准把序列分成左右两个部分，左边的都小(大)于等于有边的部分
    3、将第2步中分成的左右部分分别进行第1步的操作，然后不断的递归进行直到不能分隔

    我们先以第选取第一个元素为基准，采用左右指针的办法进行实现

    代码思想：
    1、在左指针不大于右指针的前提下
    2、右指针不断左移动，直到第一个元素小于基准
    3、左指针不断右移动，直到第一个元素大于基准
    4、交换左右指针元素
    5、上面操作完成以后，交换基准元素和左指针的元素，这样就将元素分成左右部分
    6、不对递归对左右部分重复第1步的操作

    注意：必须要先对右指针先进行移动，因为这里如果左指针先移动会导致左指针最后停留位置会在第一个大于基准的位置，导致交换错误。

    例子如 3、2、1、5、6, 如果左指针先动，会停留在5的位置，导致交换错误
    同理以最后一个元素为基准的时候应该先对左指针进行移动

    代码
    **

    1. function quick(nums, start, end){
    2.   if(start >= end) return 
    3.   let basis = nums[start],
    4.       low = start, high = end
    5.   while(low < high){
    6.     while(low < high && nums[high] >= basis) high--
    7.     while(low < high && nums[low] <= basis) low++
    8.     swap(nums, low, high)
    9.   }
    10.   swap(nums, low, start)
    11.   quick(nums, start, low - 1)
    12.   quick(nums, low + 1, end)
    13. }
    15. function QuickSort(nums){
    16.   quick(nums, 0, nums.length - 1)
    17.   return nums
    18. }

    时间复杂度(O(n) - O(n^2)) 平均O(log(n))
    空间复杂度(O(log(n)) - O(n)) 平均O(log(n))
    **
    这里的空间消耗主要是递归开辟的栈空间

    最坏的情况： 逆序退化为了冒泡排序
    一般的情况： 普通序列

    一种看似更为简单的处理办法，以双左指针进行操作的办法
    **
    这里我们选取最后一个元素作为基准
    代码思想：
    1、定义两个指针p,q指向序列首位，以p为下标开始遍历序列
    2、遇到元素小于基准，就把p,q位置元素交换，同时右移q指针
    3、遍历完交换基准和q元素的位置

    这里主要的目的是得到比q位置小的元素的值都小于q位置元素的值

    代码
    **

    1. function quick(nums, start, end){
    2.   if(start >= end) return 
    3.   for (var i = start, j = start; i < end; i++) {
    4.     if(nums[i] < nums[end]) swap(nums, i, j++)
    5.   }
    6.   swap(nums, j, end)
    7.   quick(nums, start, j - 1)
    8.   quick(nums, j + 1, end)
    9. }
    11. function QuickSort(nums){
    12.   quick(nums, 0, nums.length - 1)
    13.   return nums
    14. }

    随机一个元素作为基准

    我们只需要在序列中随机一个基准，然后交换这个基准到最后或者最前，转化成上面列举的情况

    1. function quick(nums, start, end){
    2.   if(start >= end) return 
    3.   swap(nums, random(start, end), end) // 只需要添加一步
    4.   for (var i = start, j = start; i < end; i++) {
    5.     if(nums[i] < nums[end]) swap(nums, i, j++)
    6.   }
    7.   swap(nums, j, end)
    8.   quick(nums, start, j - 1)
    9.   quick(nums, j + 1, end)
    10. }
    12. function random(min, max){
    13.   return Math.floor(Math.random() * (max - min + 1) + min)
    14. }



    **

    js以消耗额外空间为办法产生更加简洁的代码
    **

    1. /**
    2.  * 普通push concat
    3.  */
    4. function QuickSortSimple([basis, ...nums]){
    5.   if(basis === undefined) return []
    6.   let left = [], right = []
    7.   nums.forEach(v => v >= basis  ? right.push(v) : left.push(v));
    8.   return QuickSortSimple(left).concat(basis, QuickSortSimple(right))
    9. }
    11. /**
    12.  * 借用下filter
    13.  */
    14. function QuickSortSimple([basis, ...nums]){
    15.   return basis !== undefined ? [
    16.     ...QuickSortSimple(nums.filter(v => v < basis)),
    17.     basis,
    18.     ...QuickSortSimple(nums.filter(v => v >= basis))
    19.   ] : []
    20. }
    22. /**
    23.  * 借用下reduce
    24.  */
    25. function QuickSortSimple([basis, ...nums]){
    26.   if(basis === undefined) return []
    27.   let [left, right] = nums.reduce((res, v) => (res[Number(v >= basis)].push(v), res), [[],[]])
    28.   return QuickSortSimple(left).concat(basis, QuickSortSimple(right))
    29. }

    这里会产生额外的空间消耗，以及调用数组的辅助函数的一些额外时间消耗
    **

    非递归版实现
    **
    我们可以利用栈来存储每次排序的左右位置

    1. function QuickSort(arr, left,  right){
    2.     let stack = [left, right]; // 初始化默认排序部分
    3.     while(stack.length){
    4.         let right = stack.pop(), left = stack.pop();
    5.         let index = sort(arr, left, right); // 片段的排序,并获取分割点
    6.         if((index - 1) > left) stack.push(left, index - 1) // 存左边的排序部分
    7.         if((index + 1) < right) stack.push(index + 1, right) // 存右边的排序部分
    8.     }
    9.     return arr
    10. }
    12. function sort(arr, start, end){
    13.     for(var i = start, j = start; i < end; i++){
    14.         if(arr[i] < arr[end]) swap(arr, i, j++)
    15.     }
    16.     swap(arr, j, end)
    17.     return j
    18. }