几大排序思想（由javascript编写）

Hello!我是super喵二~~~今天练了几道面试题，突然觉得好久没有好好归纳过排序算法了。以前都是用C/java编写排序，这次用js来总结下五大排序算法吧：

1、冒泡排序（常用及常考排序算法）：

　　不用多说，冒泡就是一个一个浮上去~~~也就是说需要一个一个比较：

<script type="text/javascript">

    //冒泡排序，一次一次的相邻两个数比，直到把最大数找出来

    var array = [5,2,4,6,8];

    var temp;

    function sort(array){

       for(var i=0;i<array.length-1;i++){

               for(var j=0;j<array.length-i-1;j++){

                   if(array[j]>array[j+1]){

                       temp=array[j+1];

                       array[j+1]=array[j];

                       array[j]=temp;

                   }

               }

       }

       console.log(array);

    }

    sort(array) // [2,4,5,6,8]

</script>

Bubble

2、插入排序：

　　插入插入，当然需要插在该插的位置啦。简单理解就是每循环到一个数，就把它前面的数当做一个数组，然后插在数组里该插的位置：

<script type="text/javascript">

    var array = [5,2,4,6,8];

    var temp;

    //插入排序是从第一个数开始，把第一个当成数组，第二个数与它比较，插入。再将前两个看成数组，第三个来比较插入该插的位置，依次类推

    function sort(array){

       for(var i=0;i<array.length;i++){

               for(var j=0;j<i+1;j++){

                   if(array[i]<array[j]){

                       temp=array[i];

                       array[i]=array[j];

                       array[j]=temp;

                   }

               }

       }

       console.log(array);

    }

    sort(array) // [2,4,5,6,8]

</script>

Insert

3、选择排序：

　　一次一次选择出小的数（按升序来的话），首先认为第一个数最小，就依次比较它后面的数，有更小的就记录位置，将这个更小的记录之后，如果后面还有数，就以这个更小数为基准，再继续找，如果有比更小还小的，就记录位置，然后继续找，直到找到最小的然后和第一个数交换。接下来就从数组中的第二个数开始，依次~~~~

<script type="text/javascript">

    var array = [5,2,4,6,8];

    var temp;

    //选择排序，从第一个数开始比较，遇到小与它的记录位置，再将这个数与它后面的数比较，如果没有就交换这两个数，如果有，则继续比较。

    function sort(array){

       for(var i=0;i<array.length-1;i++){

               var index=i;

               for(var j=i+1;j<array.length;j++){

                   if(array[index]>array[j]){

                       index=j;

                   }

               }

               temp=array[i];

               array[i]=array[index];

               array[index]=temp

       }

       console.log(array);

    }

    sort(array) // [2,4,5,6,8]

</script>

Select

4、快速排序：

　　快速排序，众所周知，速度最快，很多公司面试都会考这个，手写的话还是有点难。大家可以主要掌握下C语言版本，用其他语言写就很容易了。。。我是参照阮一峰老师写的,主要是找一个基准元素，比基准元素小的在左边，比基准元素大的在右边，然后左右看成两个数组，分别找各自的基准元素再分组~~~直到最后~~

<script type="text/javascript">

    var array = [5,2,4,6,8];

    var temp;

    //快速排序：先找一个基准元素，比它小的放在左边数组，大的放在右边数组，然后又分别在左边和右边数组中找出基准元素进行比较

    var quicksort=function(array){

       if (array.length<=1) {

               return array;

       }else{

               var priotIndex=Math.floor(array.length/2);

               var priot=array.splice(priotIndex,1)[0];

               var left=[];

               var right=[];

               for (var i = 0; i < array.length; i++) {

                   if (array[i]<priot) {

                       left.push(array[i]);

                   }

                   else {

                       right.push(array[i]);

                   }

               }

               return quicksort(left).concat([priot],quicksort(right));

       }

    }

    console.log(quicksort(array));

</script>

Quick

5、合并排序：

　　合并排序类似快排，主要也是才用递归，分组比再合，具体实现如下：

//归并排序：从两个两个比较，然后四个一组比较，然后8个一组比较

    var array = [5,2,4,6,8];

    var merge=function(left,right){

        var arr=[];

        while(left.length>0&&right.length>0){

            if (left[0]<right[0]) {

                arr.push(left.shift());

            }else{

                arr.push(right.shift());

            }

        }

        return arr.concat(left,right);

    }

    var mergeSort=function(array){

        if (array.length==1) {

            return array;

        }else if (array.length>1) {

            var middle=Math.floor(array.length/2),

            left=array.slice(0,middle),

            right=array.slice(middle);

            return merge(mergeSort(left),mergeSort(right));

        }

    }

    console.log(mergeSort(array));

Merge

暂时就这五个，排序算法还有很多种，堆排序，随机快排。。。。这就自行了解吧，还有比较每个算法的时间复杂度，空间复杂度来决定谁更好，视情况而定吧~~

巴特西

几大排序思想（由javascript编写）

最新文章

热门文章