[数据结构与算法]算法-快速排序（最好的方法是将代码打断点一步一步走走）

算法-快速排序

原理：(按从小到大排序为例)

考察：双指针+递归分支（本质是一个创建二叉树，搜索树的过程）

方法一：

1. 取数组的随意一个数为基准数，（此例子选第一个元素 arr[0]为基准数）

2. 将数组中的其他元素与这个基准数比较，比基准数小的放到一个数组中，比基准数大的放到另一个数组中；

3. 通过递归的方式重复循环上述操作；

   比如数组：[3,2,9,1,10]

   1. 第一步：随便取出数组中的一个数（此例选数组中第一个元素arr[0]即3），数组剩下[2,9,1,10]

   2. 第二步：遍历数组[2,9,1,10],比3小的放到一个数组中，比如left:[2,1],比3大的放到另一个数组中 right:[9,10]

   3. 第三步：数组left:[2,1],再取一个基准数2，剩下数组[1],比2小，放到left；数组right:[9,10],再取一个基准数9，剩下数组[10],比9大，放到right

   4. 第四步：如果左边或者右边的数组长度仍然大于1，继续递归上面的操作，如果俩数组的长度都小于等于1，则结束递归。

   5. 拼接

   代码实现：

   let arr = [3,2,9,1,10]
   function quickSort(arr){
       if(arr.length<2) return arr;
       let base = arr[0]
       let left = []
       let right = []
       arr = arr.splice(1)//把arr[0]删掉
       arr.forEach(item=>{
           if(item<base){
               left.push(item)
           }else{
               right.push(item)
           }
       })
       return quickSort(left).concat(base,quickSort(right))
       
   }
   quickSort(arr)
   

想要更好的知道代码的执行过程，建议打断点一步一步走走看，一目了然！！！！

方法二：

1. 数组[2,3,1,5,6,4]，创建两指针，一个指向头一个指向尾，再确定一个基准数（此例子取2为基准数）。
   

2. 开始第一次的递归处理，尾指针先从右往左扫，扫到第一个小于（注意是小于，而不是小于等于哦）基准数的位置停住，这时候头指针再从左往右扫，扫到第一个大于基准数的位置停住，这时候是下面的图示状态：
   

交换两个指针所指的数，成为了下面的状态：

5. 两个数交换完毕，右指针此时指的是arr[2] = 3, 左指针指着arr[1] = 1；交换完毕后右指针继续从当前位置往左扫，扫到1的时候发现和左指针相遇了，那么这个时候就结束左右指针的扫描，左右指针同时指着arr[1] = 1，即：
   

   此时退出循环扫描的过程，交换基准数与左右指针同时所指的数的位置，开头说了，基准数我选择的是arr[0] = 2, 指针指的是arr[1] = 1; 交换过后就变成了：

   

   这时候就发现基准数已经出现在了它排完序后应该在的位置（排完序后是[1,2,3,4,5,6]，2出现在了第2位）,比这个基准数小的数组出现在了它的左边（[1]出现在了2的左边），比基准数大的出现在了它的右边（[3,5,6,4]出现在了2的右边）。

6. 之后的过程就是对左右数组的分别递归处理。

代码实现：

function quickSort(arr, begin, end) {
    //递归出口
    if(begin >= end)
        return;
    var l = begin; // 左指针
    var r = end; //右指针
    var temp = arr[begin]; //基准数，这里取数组第一个数
    //左右指针相遇的时候退出扫描循环
    while(l < r) {
        //右指针从右向左扫描，碰到第一个小于基准数的时候停住
        while(l < r && arr[r] >= temp)
            r --;
        //左指针从左向右扫描，碰到第一个大于基准数的时候停住
        while(l < r && arr[l] <= temp)
            l ++;
        //交换左右指针所停位置的数
        [arr[l], arr[r]] = [arr[r], arr[l]];
    }
    //最后交换基准数与指针相遇位置的数
    [arr[begin], arr[l]] = [arr[l], arr[begin]];
    //递归处理左右数组
    quickSort(arr, begin, l - 1);
    quickSort(arr, l + 1, end);
}

var arr = [2,3,4,1,5,6]
quickSort(arr, 0, 5);
console.log(arr)