前面说到了三种简单的排序和归并排序，今天中午就开始来谈一谈我理解的快速排序。快速排序是前面冒泡排序的一个改进版本，我们在学习的时候可以对照两个来进行学习

一、 首先来个简单的需求

首先我们在了解快排之前，我们先来完成这样一个需求：在一个无序数组中随机选定一个值为基点，将数组的根据该基点进行排序，将比基点小的元素放在基点的左边，比基点大的元素放在基点的右边。
具体的操作如下：

1.1、 初始化数组和指针

假定我们得到这样一个数组：

temp=5

如上表格所示，给定一个无序数组，然后再给定两个指针i、j，分别将指针i，j拨向数组的首尾位置。然后再设置一个变量temp用来存储数组中的第一个元素5。也就是说将temp定义成我们前面的基点。

1.2、拨动指针

1> 首先我们先拨动指针j，从数组的末端开始查找 直到找到一个比temp要小的元素，找到之后将该值赋值给数组的首位。

temp=5

2> 然后再拨动指针i，从数组的开头开始查找，直到找到一个比temp要大的元素位置，并且将该值赋值给上面查到的数组位置。

temp=5

3> 重复上面两步操作，直到两指针指向同一个元素

temp=5

1.3、赋值

最后将temp赋值给指针i，j指向的位置，此时左边的元素肯定比该元素要小，右边的肯定比该元素要大，就满足了前面说的需求了。

temp=5

1.3、详细的代码如下：

function partition(arr,left,right){
    let temp = arr[left];
    while(left<right){
        // 从右边开始查找
        while(left<right&&arr[right]>=temp) right--;
        // 如果指针没有相遇的情况下，找到就，就赋值
        if(left<right) arr[left] =arr[right];
        // 从左边开始查找
        while(left<right&&arr[left]<=temp) left++;
        // 如果指针没有相遇的情况下，找到就，就赋值
        if(left<right) arr[right]=arr[left];
    
    }
    // 将temp赋值到最中间的元素
    arr[left]=temp;
    return arr;
}

二、 真正的快速排序来了

前面一章我们在使用归并排序的时候其实也讲到了分治，那么快速排序是不是也可以用分治来解决呢？
回答是肯定的，没错，快排的思想也是分治。
我们重新整理一下思想：
给定一个数组：

 [5 ,4 ,9 ,1 ,7 ,6 ,2]
    |      |       |
[2,4,1]    5    [7,6,9]
1  2  4    5     6 7 9

如上图所示，我们首先利用一次快排将比5小的数值放在5的左边，比5大的数值放在5的右边。然后我们可以将5左边的数列在进行快排，同样在该数列内2左边的肯定比2小，2右边的肯定比大。就这样不断的细分 就将原本无序的数列组合成了一个有序的数列了。
具体分治的代码如下：

function quickSort(arr,left,right){
    if(left<right){
        //找到中心的位置
        let datas = partition(arr,left,right);
        // 排序中心左边的数列
        quickSort(arr,left,datas-1);
        // 排序中心右边的数列
        quickSort(arr,datas+1,right);
    }
    return arr;
}

全套代码如下：

function partition(arr,left,right){
    let temp = arr[left];
    while(left<right){
        // 从右边开始查找
        while(left<right&&arr[right]>=temp) right--;
        // 如果指针没有相遇的情况下，找到就，就赋值
        if(left<right) arr[left] =arr[right];
        // 从左边开始查找
        while(left<right&&arr[left]<=temp) left++;
        // 如果指针没有相遇的情况下，找到就，就赋值
        if(left<right) arr[right]=arr[left];
    
    }
    // 将temp赋值到最中间的元素
    arr[left]=temp;
    return left;
}

function quickSort(arr,left,right){
    if(left<right){
        //找到中心的位置
        let datas = partition(arr,left,right);
        // 排序中心左边的数列
        quickSort(arr,left,datas-1);
        // 排序中心右边的数列
        quickSort(arr,datas+1,right);
    }
    return arr;
}

三、 其实还有更简单的排序方式

其实关于这个，我还想到了更简单的解决方法。思想大概就是寻找一个基点，我这里寻找的是数组的最后一项temp作为基点（当然你也可以选择其他的元素）。然后数组内剩下的元素进行遍历，并且将比temp小的元素放在一个新的数组内，比数组大的放在另一个新的数组内。然后再将两个新数组通过分治在进行快速排序，直到数组的长度为小于2时停止，最后将排序好的数组和基点进行组合，就得到了新的有序数列了。
具体的代码如下：

function quickSort(arr){
    // 如果数组只有一项就直接放回了
    if(arr.length<=1) return arr;
    //取出元素的最后一项
    let temp=arr.pop();
    let left=[];
    let right=[];
    for(let i=0;i<arr.length;i++){
        // 将比pivot
        if(arr[i]<=temp) left.push(arr[i]);
        else right.push(arr[i]);
    }
    return [...quickSort(left),...[temp],...quickSort(right)]
}

说在最后

快速排序也是面试经常会考的点，怎么说呢？有备无患吧。额，要睡觉了，只能睡5分钟了 中午不睡 下午崩溃呀！！