引入

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

常用排序算法

冒泡排序（Bubble sort）

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

　　　　时间复杂度: O(n²)

　　　 动画演示：冒泡排序

　　　　实际代码：

方法一：
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(n²)

　　　 动画演示：选择排序

　　　　实际代码：

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

巴特西

js算法之最常用的排序

引入

常用排序算法

冒泡排序（Bubble sort）

选择排序（selection Sort）

归并排序（mergeSort）

快速排序（quickSort）

最新文章

热门文章