多图分析快速排序

时间:2021-1-18 作者:admin

发现问题,冷静分析,仔细思考,得出结果——我凉了,居然手写快速排序都写错了一次。

递归

写快速排序的时候,要用到递归,所以先简单过下递归。

递归:JavaScript中一个函数在其内部调用自己,那么这个函数就是自调函数,自调用的这种方式叫做递归。(日常吐槽:调用的好,有后门,这叫递归;没有后门,死循环了,那么叫递不归。)

栗子:

// 需求:递归累加,传入两个参数,求参数1到参数而中间每个数字的和(包括参数1和参数2)
// 举例:传入(1,4),结果为:10;计算过程:1+2+3+4 = 10
function add(minNum,maxNum){
    // 进行判断,判断当前的传入的一个参数是否大于第二个参数,
    // 如果是,则退出循环,并且本次循环的累加值为0
    if(minNum > maxNum){
        return 0;
    };
    //返回本次的值和 第一个参数加 1 后的下一次循环
    return minNum+add(minNum+1, maxNum);
};
console.log(add(1,10));
// 55

递归这个最麻烦的就是遇见吃自己尾巴的贪吃蛇(例如成语接龙里面的:为所欲为),所以,最好是进入函数后,第一步先判断退出函数的条件。

快速排序

据不正规统计(我花了10s钟编造的数据)90%的前端都应该知道 快速排序这个名字,然后这其中的70%应该知道快速排序的排序的大概排序原理,再然后,70%的人里面大概有30%的人可以手写快速排序代码。

所以,如果你是前端,现在马上低头,用了不超过10分钟写出了快速排序的代码,那么你算法的功力可能已经超过了81.1%(0.9 * 0.7 * 0.3 = 0.189)的前端了。

如果你没有写出快排,那么也没关系,反正10年后,大家会在美团外卖取餐口再见面的。

正文开始

快速排序:官方定义我就不说了,网上一堆一堆的,说下我自己的理解。

快速排序使用二分法,将一个数组分成左右两边两个数组和一个中间位置数据,然后左右两边再次进行二分,直到不可进行二分(数组只有一个数据或者没有数据了)为止。

代码(可以先大概看下代码,然后直接看后面的举例分析)

// 手写快速排序
function quickSort(array){
    // 1、如果array的legth<=0,那么就返回原数组
    if(array.length <= 0){
        return array;
    };
    // 2、获取中间的数字,并从原数组中删除它
    let middleNum = array.splice(Math.floor(array.length/2),1)[0];
    // 3、for循环,大于中间数字的放右边,小于的放左边
    let leftArr = [], rightArr = [];
    for(let i=0; i<array.length; i++){
        array[i] >= middleNum ? rightArr.push(array[i]) : leftArr.push(array[i]);
    };
    // 4、递归+左中右顺序进行拼接
    return quickSort(leftArr).concat(middleNum,quickSort(rightArr));
};
let arr = [2,3,6,1,87,12,0,6];
console.log(quickSort(arr));
// [0, 1, 2, 3, 6, 6, 12, 87]

举例分析

1、空数组——[]:数据为空,length为0,所以直接返回原数组

2、有一个数字的数组——[1]:length为1,不需要排序,直接返回原数组

3、数字是两个的数组——[12,8]:

4、数字多于两个的数组——[2,3,6,8,87,12,0,6]:

欧克,又水了一篇文章。

少年不识愁滋味,爱上层楼。爱上层楼,为赋新词强说愁。而今识尽愁滋味,欲说还休。欲说还休,却道天凉好个秋!——辛弃疾

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。