js实现冒泡排序和快速排序

前言

冒泡排序和快速排序是面试中经常被提到的问题,这种算法类的基础知识还是有必要掌握的,有次面试让手写一个快排,由于自己之前没有理解,只能在脑子里回忆个大概,最终也没写太好,回来后就找了些资料,在此总结一下,代码都是我上机验证过的,如果有问题,欢迎老哥们加微信指正。


在上代码之前先啰嗦一下这两个排序算法的概念[来自百度百科]点我查看冒泡排序 | 点我查看快速排序

冒泡排序算法的原理

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较
  5. 算法稳定性

    冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,是不会再交换的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

  • 下面上代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    function babbleSort(arr){
    let m = arr.length;
    for(let i = 0; i< m-1; i++){
    for(let j = 0; j < m-i-1; j++){
    if(arr[j] > arr[j+1]){
    // var temp = arr[j];
    // arr[j] = arr[j+1];
    // arr[j+1] = temp;

    //es6解构赋值中的数组解构用法 互换两个变量的值
    [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
    }
    }
    }
    return arr;
    }

    var arr = [3,6,4,8,1,7,14,5,43,2,44,0];
    console.log(babbleSort(arr));

其中es6的解构赋值可以参考这篇文章ES6解构赋值

运行结果如下图:
Loding...

快速排序算法的原理

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
简言之:先找一个基准[一般取中间的项作为基准],然后遍历剩余的数组成的数组,其中小于基准的放在左边,大于基准的放在右边,最后把左边-基准-右边拼接起来就是排序后的数组

  • 下面上代码
    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
    function quickSort(arr){
    //如果数组<=1,则直接返回
    if(arr.length<=1){return arr;}
    var pivotIndex=Math.floor(arr.length/2);
    //找基准,并把基准从原数组删除,剩下的和基准作比较
    var pivot=arr.splice(pivotIndex,1)[0];
    //定义左右数组
    const left=[];
    const right=[];

    //比基准小的放在left,比基准大的放在right
    for(let 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));

    //或者用es6的三点扩展运算符 做连接
    return [...quickSort(left), pivot, ...quickSort(right)]
    }

    var arr = [132,345,55,332,3,5,2,34,65,1,7,9,44,21];
    console.log(quickSort(arr));

其中es6的三点运算符可以看一下这篇文章ES6三点扩展运算符

运行结果如下图:
Loding...

总结

这两个排序一定要掌握,其实理解了,很容易记住,反而是死记硬背的记不牢,如果此文对你有一点点的帮助,我很开心!

如果觉得文章不错,请我吃根辣条吧~~