js算法之最常用的排序

摘要：算法之最常用的排序参加百度前端的课程真的是好多知识点不知道。快速排序也是在实际中最常用的一种排序算法，速度快，效率高。插入排序的思路很简单，很清晰，是一种最常见最简单的排序方法。

参加百度前端的课程真的是好多知识点不知道。边学边做题，在问题中学习，知识点从点到面，但是要善于总结记录才行。加油吧，骚年！

时间复杂度是衡量一个算法效率的基本方法
我们把它记作：O(n)

大白话介绍：比较相邻的两个数，如果后面的比前面的小，把小的放在前面。
时间复杂度: O(n2)
动画演示:冒泡算法
实际代码：

（优化算法:如果数组已经是有序了，就没必要再比较了）：
var arr=[5,3,2,4,1,0];
function bubbleSort(arr){
    var flag = false;  // 定义一个变量为false，未交换位置
    for(var i=0;i
优化方法设置一个中断标志位，在条件测试中如果发生了交换就将中断位屏蔽，然后在外层循环中检查中断位，如果中断位没有被屏蔽，将结束循环。每次开始内层循环之前重置中断位。这样就可以在已经是正序排列时不继续进行循环，达到最优的复杂度.
计算时间复杂度主要是看这几个指标：
1 input size(输入)
2 basic operation/most costly operation(基本操作)
3 determine average cases(决定最坏和平均的时间)
4 sove it(计算)
在冒泡排序中的核心部分是
for(i=0;ifor(j=0;jif(a[j+1]
根据上面的步骤
1 size = n
2 basic operation = key comparison(比较)
因为比较是每次都要做的，而交换不一定每次都要做
3 average case = worst case
4 solve it
就是计算一共进行多少次比较这里就是用数学里的求和公式sigma求出来
最内层循环key comparison的次数是从0到n-i-1，外层循环i从0到n-1
所以总数是对(n-1-i)求和，i从0到n-1
(n-1)*n - （1+2+3+4+…+n-1）= n(n-1)/2 = O(n^2)
所以时间复杂度是n的平方

选择排序
大白话介绍：先从原始数组中选择一个最小的数据，和第一个位置1的数据交换。再从剩下的n-1个数据中选择次小的数据，将其和第二个位置的数据交换。不断重复，知道最后两个数据完成交换。可以很清楚的发现，选择排序是固定位置，找元素.
时间复杂度：O(n2)
动画演示:选择排序
实际代码：
var arr=[5,3,2,4,1,0];
function selectionSort(array){
    var min,temp;
    for(var i=0; i
分析:
从选择排序的思想或者是上面的代码中，我们都不难看出，寻找最小的元素需要一个循环的过程，而排序又是需要一个循环的过程。因此显而易见，这个算法的时间复杂度也是O(n*n)的。这就意味值在n比较小的情况下，算法可以保证一定的速度，当n足够大时，算法的效率会降低。并且随着n的增大，算法的时间增长很快。因此使用时需要特别注意。

快速排序
也是在实际中最常用的一种排序算法，速度快，效率高。就像名字一样，快速排序是最优秀的一种排序算法。
大白话：
（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
分析
快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k-1次关键字的比较。
最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。时间复杂度为O(n*n)
在最好情况下，每次划分所取的基准都是当前无序区的"中值"记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：O(nlgn)
尽管快速排序的最坏时间为O(n2)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。

插入排序
大白话：首先对前两个数据从小到大比较。接着将第三个数据与排好的前两个数据比较，将第三个数据插入合适的位置。以此类推。(插入排序有两个循环，外循环将数组挨个移动，内循环将对外循环选中的元素及他前面的数进行比较。)
时间复杂度：O(n^2) 
代码：
var arr=[5,3,2,4,1,0];
function insertSort(arr){
    var temp, j;
    for(var i=1; i0 && arr[j-1]>temp){
            arr[j]=arr[j-1];
            j--;
        }
        arr[j]=temp;

    }
    return arr;
}
document.write(insertSort(arr));  //0,1,2,3,4,5
分析
(插入排序有两个循环，外循环将数组挨个移动，内循环将对外循环选中的元素及他前面的数进行比较。)
插入排序的思路很简单，很清晰，是一种最常见最简单的排序方法,。但是可以看出，由于需要两层循环，外层循环n-1次，内层循环每次递增一次。当输入完全从小到大有序时，只需要常数的时间，这当然是最好的情况。但是我们不能期望输入，当输入完全逆序时，最坏的情况就出现了，显然时间复杂度是O(n*n)的。我们都很清楚，这个时间复杂度在排序中并不能算好的。这也是为什么插入排序虽然简单，但并没有被广泛应用的原因所在。

归并排序（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]

参考资料：
1.算法的时间复杂度
2.算法的时间复杂度分析
3.如何计算时间复杂度
4.js算法之最常用的排序
5.快速排序（Quicksort）的Javascript实现
6.排序算法——快速排序