js算法之最常用的排序 – 孙可瘦

引入

  大学学习计算机语言的那几年,从c语言,到c++,再到数据结构JAVA..让我印象最深刻的还是最开始老师讲冒泡算法的时候,直到现在大四快毕业了我才渐渐通窍了。刚学前端的时候以为前端就是做出好看很炫的页面就行了,后来才渐渐懂得前端不只是页面仔。一次美团面试,面试官说他们要的不仅是前端,他们要的是“工程师”,从面试开始到结束问都是算法,顿时把我给打击了。二叉树、基本算法还有时间复杂度都是很重要的东西,不仅体现了一个前端的学习深度,还体现了一名计算机学生的专业水平。所以,为了查缺补漏,我决定开始研究一下程序猿最爱提的算法,今天聊聊最常用的排序算法。鱿鱼看过很多资料觉得都太专业化了,根本看不懂,所以以下我都尽量用能让自己(别人)看懂的介绍来描述啦~

 

常用排序算法

  • 冒泡排序(Bubble sort)

    大白话介绍:比较相邻的两个数,如果后面的比前面的小,把小的放在前面。

    时间复杂度:  O(n2)

      动画演示冒泡排序

    实际代码

方法一:
function
bubbleSort(arr){ for(var i=0;i<arr.length-1;i++){ for(var j=0;j<arr.length-1;j++){ if(arr[j+1]<arr[j]){ temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp; } } } return arr; }

//对比arr中的第j+1项和第j项,如果第j+1项小于第j项,就把第j+1项和第j项调换位置。如果没达到最终的顺序(从小到大),就继续找,继续换,直到达到最终效果

但是上面的方法并不完美,如果数组已经是有序了,就没必要再比较了,所以下面有一种优化冒泡排序算法:

 

优化冒泡排序算法

方法二(优化算法):
function
bubbleSort(arr){ var flag = false; // 定义一个变量为false,未交换位置 for(var i=0;i<arr.length-1;i++){ for(var j=0;j<arr.length-1;j++){ if(arr[j+1]<arr[j]){ temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp; flag = true; //true,已交换位置 } } if(flag){ flag = false; //如果交换了位置,将flag重新设为false }else{ break; //如果未交换,则跳出循环 } } return arr; }


或者写成这样~
function bubbleSort(arr){
    var flag;
    for(var i=0;i<arr.length-1;i++){
        flag =false;
        for(var j=0;j<arr.length-1;j++){
            if(arr[j+1]<arr[j]){
                temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
                flag = true;
            }
        }
        if(!flag){
            return arr;
        } 
    }
    return arr;
}

 

  • 选择排序(selection Sort)

    大白话介绍:在乱序的数组中选择最小的值,然后和每次循环后的数组的第一位进行交换

    时间复杂度:O(n2)

      动画演示选择排序

    实际代码:   

var arr=[5,3,2,4,1,0];
function
findMin(arr,first){ var minindex = first; //定义最小下标 var minNum = arr[first]; //定义数组中的最小值 for(var i=first+1;i<arr.length;i++){ //循环找到最小值和最小下标 if(arr[i]<minNum){ minNum = arr[i]; minindex = i; } }
return minindex;//返回最小值下标 一共查找了六次,最小值下标分别为 :5,4,2,4,4,5 } function selectionSort(arr){ for(var i=0;i<arr.length;i++){ var min =var temp = arr[min]; arr[min] = arr[i]; //eg.第一次循环 :将最小值5和arr[0]进行交换 arr[i] = temp; // 剩下几次同第一次 } return arr; } document.write(selectionSort(arr)); //0,1,2,3,4,5,

     排序过程:(自己画的一个粗糙的框框表嫌弃)

 

        

 

  • 归并排序(mergeSort)

    大白话介绍:   把一个数组分为两个数组,左边排好序,右边排好序,然后合并到一起排序

      专业性介绍:   归并排序是分治法的典型实例,指的是将两个已经排序的序列合并成一个序列的操作

    时间复杂度:   O(nlogn)

    动画演示:归并排序

    实际代码:

     var arr=[-11,17,12,19,0,-222];
     function mergeSort(arr,s,e){
         if(s>e){   //起始位置大于终点位置,返回空数组
             return [];
         }else if(s==e){
             return [arr[s]]; //起始位置等于终点位置,说明数组里只有一个数字,返回只含一个数字的数组    
         }

         var mIndex = Math.floor((s+e)/2); //中间位置的Index
         var arrL = mergeSort(arr,s,mIndex); //将左边的数组排序
         var arrR = mergeSort(arr,mIndex+1,e); //将右边的数组排序
         
         var resultArr = []; //结果数组
         while(arrL.length>0 || arrR.length>0){ //当左右两个数组都不为空时
             if(arrL[0]<arrR[0]){
                 resultArr.push(arrL.shift());
             }else{
                 resultArr.push(arrR.shift());
             }

             if(arrL.length==0){  //当左边的数组为空时
                 resultArr = resultArr.concat(arrR);
                 break;
             }else if(arrR.length==0){
                 resultArr = resultArr.concat(arrL);
                 break;
             }
         }
         return resultArr;
     }

     document.write(mergeSort(arr,0,arr.length-1));

  排序过程:

     

 

  • 快速排序(quickSort)

  大白话介绍:引用阮一峰老师的一句话,感觉是极好理解的~(我的目标也是成为像阮一峰老师这样的)

 (1)在数据集之中,选择一个元素作为”基准”(pivot)。

 (2)所有小于”基准”的元素,都移到”基准”的左边;所有大于”基准”的元素,都移到”基准”的右边。

 (3)对”基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。 

     实际代码:

    var arr=[77,-33,22,32,0,2,11];
    function quickSort(arr){
        if(arr.length<=1){ //如果数组中只有一位数,返回数组
            return arr;
        }
        var mNumIndex = Math.floor(arr.length/2); //取基准值的下标
        var mNum = arr.splice([mNumIndex],1)[0];  //取基准值
        var left = [];  //左边数组
        var right = []; //右边数组
        
        for(var i=0;i<arr.length;i++){
            if(arr[i]<mNum){  //如果数组小于基准值,放在左边数组
                left.push(arr[i]);
            }else{            ///否则
                right.push(arr[i]);
            }
        }        
        return quickSort(left).concat([mNum],quickSort(right)); //返回左边数组+基准值+右边数组
    }

    document.write(quickSort(arr));

  排序过程:

 

 

      以上就是一些常见的排序了,但是还有很多常见的排序没有提到~~ 后期还会写一个常用排序二~敬请期待噢 ~希望我学到的东西也能帮助到大家~有说错的地方欢迎批评指正~

 

 

  学习资料:

  http://bubkoo.com/2014/01/15/sort-algorithm/merge-sort/ 

      http://www.cnblogs.com/binking338/p/3440296.html

      http://www.webhek.com/misc/comparison-sort

      http://www.cnblogs.com/CareySon/archive/2011/10/28/2227703.html

       http://bubkoo.com/2014/01/15/sort-algorithm/merge-sort/

      http://www.cnblogs.com/wteam-xq/p/4752610.html

     http://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html



You must enable javascript to see captcha here!

Copyright © All Rights Reserved · Green Hope Theme by Sivan & schiy · Proudly powered by WordPress

无觅相关文章插件,快速提升流量