用javascript实现简单排序算法

  声明:本文为原创文章,如需转载,请注明来源WAxes,谢谢!

  本文为楼主自己的学习记录文章,若有不当之处请斧正。

 

  本文主要记录排序算法

 

  【冒泡排序】

  感觉这个是最简单的排序算法了。直接引用*里的解释:

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

  原理相当容易理解:

  实现代码如下:

用javascript实现简单排序算法
var array = [],maxNum = 100;

        for(var i=0;i<maxNum;i++){
            array.push(parseInt(Math.random()*maxNum));
        }
        
        console.log("排序前:"+array);
        bubbleSort(array);
        console.log("排序后:"+array);

        function bubbleSort(array){
            var end = array.length-1;
            while(end>0){
                for(var i=0;i<end;i++){
                    if(array[i]>array[i+1]){
                        var md = array[i+1];
                        array[i+1] = array[i];
                        array[i] = md;
                    }
                }
                end--;
            }
        }
用javascript实现简单排序算法

用javascript实现简单排序算法之后就不贴结果图了,都一样,= =反正都排的出来。

 

  【插入排序】

  插入排序算法大概原理:遍历数组,取两个相邻数据a和b,a数据之前的数据为有序区,b数据之后的为无序区。如果b大于a,继续往下遍历。如果b小于a,则把b跟有序区里的值按<-方向进行比对,比b大的数据索引均加一。当遍历到小于或等于b的数据时,那个位置就是b应该呆的位置。用*上的一张图,就能秒懂了

用javascript实现简单排序算法

   插入也挺容易理解的:

用javascript实现简单排序算法
var array = [],maxNum = 100;

        for(var i=0;i<maxNum;i++){
            array.push(parseInt(Math.random()*maxNum));
        }
        
        console.log("排序前:"+array);
        insertSort(array);
        console.log("排序后:"+array);

        function insertSort(array){
            for(var i=0;i<array.length;i++){
                var a = i,b = i+1;

                if(array[a]>array[b]){
                    var j = b-1,ayb = array[b];
                    while(ayb<array[j]){
                        array[j+1] = array[j]
                        j--;
                    }

                    array[j+1] = ayb;
                }
            }
        }
用javascript实现简单排序算法

 

  【希尔排序】

  希尔排序算法大概原理:遍历的方法跟插入排序差不多,不一样的就是希尔排序是先将数组分成多列,对每一列里的数据进行排序,然后对列数进行N/2操作,再进行逐列排序,直至列数为1时,数组即排列完毕。 

用javascript实现简单排序算法
var array = [],maxNum = 100;

        for(var i=0;i<maxNum;i++){
            array.push(parseInt(Math.random()*maxNum));
        }
        
        console.log("排序前:"+array);
        shellSort(array ,10);
        console.log("排序后:"+array);

        function shellSort(array , d){
            // var d = d;
            while(d>=1){
                sort(array , d);
                d = Math.floor(d/2)
            }
        }

        function sort(array , d){
            var h = array.length/d;
            for(var i=0;i<d;i++){
                for(var j=0;j<h;j++){
                    var a = i+j*d , b=a+d;
                    
                    if(array[a]>array[b]){
                        var g = a,ayb = array[b];
                        while(ayb<array[g]){
                            array[g+d] = array[g]
                            g-=d;
                        }
                        array[g+d] = ayb;
                    }
                }
            }
        }
用javascript实现简单排序算法

  

  【快速排序】

  这个排序算法想了比较久,脑子没那么灵活,所以研究了好一会才弄懂原理。其实说白了就是取个key作为中间值,把比key大的数据扔右边,把比key小的扔左边,循环递归。

  再详细说下快速排序算法原理(我理解的):取数组的一个数据作为key,一般取第一个数据,然后进行遍历,将比key大的值扔在右边,把比key小的值扔在左边。遍历的方法:定义变量i、j,i为0,j为数组最后一个元素的索引。首先先从j到i方向开始遍历,i不动。即是<--方向,当遍历到的数据比key小且比array[i]的值小的时候,交换array[i]和array[j]的值。然后停止j向i的运动,开始i向j方向进行遍历当遍历到的数据比key小且比array[j]的值大的时候,交换array[i]和array[j]的值。然后停止i向j的运动,再开始j向i方向进行遍历,如此循环,当i==j的时候,说明array[i]的位置就是key值应该在的位置,key值在的位置左边都是比key小的值,右边都是比key大的值。 这是第一次循环,所以把key作为中点把数据分成两边,然后再对两边同时进行递归。算到最后排序的开始点与结束点相差仅为1时,整个数组的排序就已经排序好了。

  代码如下:

用javascript实现简单排序算法
var array = [],maxNum = 100;

        for(var i=0;i<maxNum;i++){
            array.push(parseInt(Math.random()*maxNum));
        }
        
        console.log("排序前:"+array);
        quickSort(array , 0 , array.length-1);
        console.log("排序后:"+array);

        function quickSort(array , start , end){
            //key是分割线
            var i=start;j = end,key = array[start];
            while(i<j){
                while(i<j){
                    if(array[j]<=key&&array[j]<array[i]){    //j->i方向的遍历,如果比key小且比array[i]小,交换数据
                        var md = array[i];
                        array[i] = array[j];
                        array[j] = md;
                        break;
                    }
                    j--;
                }
                while(i<j){
                    if(array[i]>=key&&array[i]>array[j]){    //i->j方向的遍历,如果比key大且比array[j]大,交换数据
                        var md = array[i];
                        array[i] = array[j];
                        array[j] = md;
                        break;
                    }
                    i++;
                }
            }
            if(i-start>1){            //对key左边的数据进行递归排序
                quickSort(array , start , i-1)
            }
            if(end-i>1){            //对key右边的数据进行递归排序
                quickSort(array , i+1 , end)
            }
        }
用javascript实现简单排序算法

  

  【选择排序】

  原理:将序列划分为无序和有序区,寻找无序区中的最小值和无序区的首元素交换,有序区扩大一个,循环最终完成全部排序。

  代码:

用javascript实现简单排序算法
        var array = [],maxNum = 100;

        for(var i=0;i<maxNum;i++){
            array.push(parseInt(Math.random()*maxNum));
        }
        
        console.log("排序前:"+array);
        selectSort(array);
        console.log("排序后:"+array);

        function selectSort(array){
            var i = 0;    //无序区最小指针

            while(i<array.length){
                var index = 0 , min = null;  //index为当前遍历到的地址,min存放最小值
                for(var j=i;j<array.length;j++){
                    if(array[j]<min||min===null){
                        min = array[j];
                        index = j;
                    }
                }

                if(array[i]!==min){            //提高排序稳定性,如果两个元素值相同则不交换
                    var md = array[i];
                    array[i] = array[index];
                    array[index] = md;
                }
                i++;
            }
        }
用javascript实现简单排序算法

 

   再贴上一个各个算法之间的计算速度测试DEMO:

     看DEMO请戳我

 

用javascript实现简单排序算法,布布扣,bubuko.com

用javascript实现简单排序算法

上一篇:Python - list, tuple, dict, set的区别


下一篇:Python 中的@修饰符作用