快排

galois 发布于2019-08-20 16:40 / 1356人阅读

摘要：写这篇文章源于之前的一次面试以及网上看到各种说原生的比快排快的例子，因为他们都没有写好快排。

写这篇文章源于之前的一次面试以及网上看到各种说原生的sort比快排快的例子，因为他们都没有写好快排。面试的时候让我写一个快排，我写出了我在网上看的的很简洁的一段代码（后来发现这个代码在数据结构和算法JavaScript描述这本书上也有）：

function quickSort(arr){
    if(arr.length < 1){
            return [];
    }
    var left = [],right = [],flag = arr[0];
    for(var i=1;i
这样写的话，乍一看确实是快排的思想，把比主元小的元素放到左数组，把比主元大的元素放到右数组，然后分别对左右数组的元素进行排序最终拼接成新的数组。
但是计算机课程里讲解快排的时候都不是这样讲解的，一趟快速排序的算法一般是这样讲解的：

设置两个变量i、j，排序开始的时候：i=0，j=N-1；
以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
重复第3、4步，直到i=j；

采用js实现的版本如下：
function quickSort_two(arr){
    function sort(start,end){
        if(start + 1 > end){
            return;
        }
        var flag = arr[start],f = start,l = end;
        while(f < l){
            while(f < l && arr[l] > flag){
                l--;
            }
            arr[f] = arr[l];
            while(f < l && arr[f] <= flag){
                f++;
            }
            arr[l] = arr[f];
        }
        arr[f] = flag;
        sort(start,f-1);
        sort(f+1,end);   
    }
    sort(0,arr.length-1);
}

对比这两中快排的写法，在时间复杂度上都是O(nlogn)，但是第二种写法使用了更少的空间，第一种写法的空间复杂度是O(nlogn),而第二种的空间复杂度是O(logn),而且对数组的操作都在原数组上进行，减去了创建空间的消耗和时间，在性能上无疑有了更多的提升。

下面是三种排序算法的一个对比：
function quickSort_one(arr){
    if(arr.length < 1){
            return [];
    }
    var left = [],right = [],flag = arr[0];
    for(var i=1;i end){
            return;
        }
        var flag = arr[start],f = start,l = end;
        while(f < l){
            while(f < l && arr[l] > flag){
                l--;
            }
            arr[f] = arr[l];
            while(f < l && arr[f] <= flag){
                f++;
            }
            arr[l] = arr[f];
        }
        arr[f] = flag;
        sort(start,f-1);
        sort(f+1,end);   
    }
    sort(0,arr.length-1);
}

function quickSort_three(arr){
    arr.sort(function(a,b){
        return a-b;
    });
}

function countTime(fn,arr){
    var start = Date.now();
    fn(arr);
    var end = Date.now();
    console.log(end - start);
}

function randomVal(num){
    var arr = [];
    for(var i=0;i
在chrome下的一个运行情况（以100000个数为例,由于每次排序后数组都发生了改变，所以每次都创建了新数组，以100000的基数来算的话，虽然不是同一个数组，但是结果也是值得参考的）：

在firefox下的运行结果：

不论是firefox还是chrome,第一种排序算法的时间都是最长的，第二种是最快的，原生的sort方法比第二种方法稍微慢一点，但比第一种还是快多了。

GPU云服务器云服务器快排快排会写吗

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/83073.html

一篇文章让你真正了解快速排序

摘要：但是大家了解阮一峰快排事件吗，是否知道快排的最佳实践本文从一个争执讲起，通过生动详实的例子让你真正了解快排。参考文档快速排序复杂度分析如何看待文章面试官阮一峰版的快速排序完全是错的快速排序算法的优化思路总结只要是个工程师，就或多或少的知道快排，其中很多人都能轻松的写出一个快排的实现。但是大家了解阮一峰快排事件吗，是否知道快排的最佳实践？本文从一个争执讲起，通过生动详实的例子让你真正了...

Jaden 2019-08-23 13:58 评论0 收藏0
面试官：快排会写吗？

摘要：快排可以说是一道必知的常见面试题，同时也有多种实现方式。之所以使用随机快速排序而不是普通的快排。其中交换数组元素位置，打印元素的方法我就没贴了，代码太长你们也不方便看。快排可以说是一道必知的常见面试题，同时也有多种实现方式。在这篇文章中，我使用的是随机三路快排。之所以使用随机快速排序而不是普通的快排。是因为前者可以使得数列有序的概率降低，从而使随机快速排序平均速度是比快速排序要快的...

UCloud 2019-08-16 13:41 评论0 收藏0
Java数据结构与算法——快速排序

摘要：快排是一种不稳定的排序算法，在经过排序后，等值的元素的相对位置可能发生改变。声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本篇文章介绍排序算法中最常用也是面试中最容易考到的排序算法——快排，包括快排的思想和原理、java快排代码、快排的特点性能和快排的适用场景。 0、其他排序算法索引(待更) java数据结构与...

Panda 2019-08-16 11:12 评论0 收藏0
精词快排SEO不限指数任意关键词1元/天最快最快隔天上首页

摘要：支持百度百度搜狗搜狗神马搜索支持软文内页优化，有排名即可最快隔天上首页效果绝佳，百度移动新算法已经上线，技术源头厂家招商合作可独立后台量大价可谈平台新活动联系客服赠送元余额支持百度PC、百度Wap、搜狗PC、搜狗Wap、360PC、360Wap、神马搜索支持软文内页优化，有排名即可！最快隔天上首页！效果绝佳！，百度PC/移动新算法已经上线！，技术源头厂家招商合作可oem独立后台 ...

honmaple 2021-11-24 10:30 评论0 收藏0
记一次腾讯霸面---前端

摘要：客户端的浏览器根据双方同意的安全等级，建立会话密钥，然后利用网站的公钥将会话密钥加密，并传送给网站。地址必须和一个网络掩码对应使用缺一不可。网络掩码的主要作用是告诉计算机如何从地址中析取网络标识和主机标识。霸面的是前端实习生岗位，当时听同学说前端缺人，还特意设了一个霸面区，就去溜了个弯儿，毕竟不试试，怎么知道自己有多菜呢o(￣︶￣)o一面技术面，面试官关注的点一直在数据结构、算法、计...

ralap 2019-08-22 16:25 评论0 收藏0