最近的一次前端实习面试题。。因为没准备充分，导致在快排这一块就直接死了。。太丢人了。回来之后好好总结了下，然后写下这篇js实现快排。

原理

原理其实很简单，我们要先设一个基准数，我们一般设为第一个，然后我们从数组的两端开始找，这边我们开始节点设为low，尾节点设为high，我们从high开始往左找一个比基准数要小的数，（至于为什么要先从high开始往左查找后边我们会讲到），我们在从low开始往右找比基准数大的值，这里一定要满足low是小于high的，然后我们交换找到的两个值，然后当我们找的过程中low=high了则这个值与基准数进行交换，可以看下图的过程演示。

在这里插入图片描述
在这里插入图片描述

这样后我们第一次就结束了，可以看到基准数为9，最后一次执行完后，9左边的都比9小，右边的都比9大。这样我们第一次就完成了，有一种’二分’的思想，之后我们只要对左边和右边分别进行上述操作即可，可以轻松的用递归来实现了。

问题

为什么要从右边找，这其实很好理解，因为我们最后low=high了，找到的那个值，必须比基准小（仅限从小到大排序，且基准在左边），因为要确保左边的比基准都小。这边可以举个例子：

4 3 6 5 7

如果先从左边找的话：第一个比4大的值为6，那么我们再从右边找一个比4小的值，我们会发现是3，但是如果要找到3那么high要比low要小了，我们在low=high的时候就要交换和基准了，所以最后结果会变成

6 3 4 5 7

这样就并不能保证4左边的一定比4小，右边的比4大。

搞懂原理，代码实现就很简单了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*
 * @Author: Meng Jiawei
 * @Date: 2020-06-18 16:01:59
 * @LastEditTime: 2020-06-18 17:06:46
 * @FilePath: \node_demo1\index.js
 */ 
function sort(arr,left,right){
    if(left>=right){
        return
    }
    let symbol=arr[left]
    let i=left
    let j=right
    while(i!=j){
        while(i<j&&arr[j]>=symbol)
        j--;
        while(i<j&&arr[i]<=symbol)
        i++
        if(i<j){
            let temp=arr[i]
            arr[i]=arr[j]
            arr[j]=temp
        }
      
    }
    let temp1=arr[i]
    arr[i]=arr[left]
    arr[left]=temp1
    sort(arr,0,i-1);
    sort(arr,i+1,right);
}
var a=[9，5，11，4，1，7，6]
sort(a,0,a.length-1)
console.log(a)