快速排序

作者: Lxylona | 来源:发表于2018-04-04 20:00 被阅读33次

七大排序算法之快速排序
面试准备--排序
排序
算法笔记01-排序#2
PHP 实现快速排序
快速排序的Python实现
数据结构与算法快速排序
数组-快速排序
OC数据结构&算法
要成功就做一百题-94

快排，快忘光了，一直因为太忙了没有复习，导致的后果就是今天阿里打了电话一面，问了快排，我就只能说：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），改用插入排序方法。或者在快速排序递归至每个分组都足够小的时候，停止递归，然后对整个近乎有序的数组实行插入排序。
先递归比较小的分组，然后对大的另一个分组使用尾递归，减少堆栈。