快排，快忘光了，一直因为太忙了没有复习，导致的后果就是今天阿里打了电话一面，问了快排，我就只能说：emmm，选一个基准值，然后遍历数组，把小的换到前面，把大的换到后面，然后递归……
面试官说：没关系，了解原理就好。
🙂️谢谢面试官的安慰。
废话少说，开始吧。
ps：用JS写的代码。
快速排序（quicksort）的主要思想就是：选择一个基准元素，把小于基准的元素全部移到左边，大于基准的元素移到右边。然后对左边和右边的元素分别再进行排序，如此循环到每个小分组只剩下一个元素为止。
对元素的划分有两种算法。一个是Lomuto算法。
function LomutoPartition(a,left,right){
var p=a[left];
var s=left;
//交换函数，交换数组两个元素
function swap(a,x,y){
var temp=a[x];
a[x]=a[y];
a[y]=temp;
}
//开始遍历数组
for(var i=left+1;i<=right;i++){
if(a[i]<p){
s++;
swap(a,s,i);
}
}
swap(a,s,left); // 基准值放中间
return s;
}
把第一个元素作为基准元素。从第二个开始遍历余下的元素，a[i]>=p则继续往前走，当遇到一个小于p的元素时，就停下来，将s增加1，再交换a[s]，a[i]的元素。这样就保证比p小的元素永远在s左边，比p大的元素永远在s右边。
循环结束后，再交换a[s]和a[left]的值。使基准元素成为分界点。
另一个算法是Hoare算法。Hoare就是提出快速排序思想的人，图灵奖得主。
function HoarePartition(a,left,right){
if(left<right){
var key=a[left];
var i=left+1;//跟踪比基准小的元素，从左到右遍历
var j=right;//跟踪比基准大的元素，从右到左遍历
//判断i是否溢出（注意上面i=left+1，有溢出可能）
if(i<=right){
while(i<=j){
while(a[i]<key&&i<right) i++;//依旧检查i是否会溢出
while(a[j]>key) j--;
a[j]={x:a[i],y:(a[i]=a[j])}.x;//此交换语句相当于上文的swap函数
}
a[j]={x:a[i],y:(a[i]=a[j])}.x;//此时j<=i，所以应取消最后一次交换
a[left]={x:a[j],y:(a[j]=a[left])}.x;
}
}
}
变量i跟踪小于基准的元素，从左到右遍历，遇到大于等于基准的元素就停下来。j跟踪大于基准的元素，从右到左遍历，遇到小于基准的元素就停下来，然后交换a[i]和a[j]。直到i，j相遇。再把基准元素和a[j]交换。比较麻烦的就是每次都要判断i是否溢出。
两个划分算法效率是一样的，个人认为Lomuto算法比较容易理解。
有了划分算法之后，要写快速排序就容易多了。
下面是用js写的原地排序（in-place）：
function quickSort(a){
//交换函数，交换数组两个元素
function swap(a,x,y){
var temp=a[x];
a[x]=a[y];
a[y]=temp;
}
//划分算法
function LomutoPartition(a,left,right){
var p=a[left];
var s=left;
for(var i=left+1;i<=right;i++){
if(a[i]<p){
s++;
swap(a,s,i);
}
}
swap(a,s,left);
return s;
}
//递归逻辑
function sort(a,left,right){
if(left>=right) return;
var s=LomutoPartition(a,left,right);
sort(a,left,s-1);
sort(a,s+1,right);
}
sort(a,0,a.length-1);
}
还有另一种比较有js特色的快速排序实现，代码如下：
var quickSort = function(arr) {
if (arr.length <= 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];//把基准元素切出来
var left = [];//存放小于基准的元素
var right = [];//存放大于等于基准的元素
for (var i = 0; i < arr.length; i++){
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));//把切开后的数组连接起来
};
不过这种实现有一个很大的缺点，就是很耗内存，对一个有n个元素的数组进行排序，每一次递归都要新建两个数组来存放两边的元素，最好情况下递归循环log n次，每次需要n个元素的空间，因此需要额外n(log n)的空间，加上创建数组需要一些额外开销。因此这种方法对于大数组而言就不合适了。
关于快速排序的效率：
- 最好情况下，每次都刚好平均分为两个相同长度的分组，递归循环 log n 次， 键值比较次数为C(n)=2*C(n/2)+n,C(1)=0
- 最坏情况下，每次数组都会分成一边长度为0，一边长度为n-1的两个分组，递归循环 n-1次，键值比较次数为 n+(n-1)+(n-2)+……+1
- 平均情况下，键值比较次数约等于 1.39nlog n
所以它们的效率分别是：
关于快速排序的优化：
- 更好的基准元素选择方法。比较有名的是三平均划分法（median-of-three method），以数组最左边，最右边，以及最中间元素的中位数作为基准元素。上文提过平均情况下快速选择的效率大约是1.39nlog n，根据维基百科，使用三平均划分法能使效率达到1.188nlog n 左右。
- 当数组足够小的时候（5-15），改用插入排序方法。或者在快速排序递归至每个分组都足够小的时候，停止递归，然后对整个近乎有序的数组实行插入排序。
- 先递归比较小的分组，然后对大的另一个分组使用尾递归，减少堆栈。
