js理解常见排序算法

2017-09-08

包含插入排序、希尔排序、选择排序和快速排序
一般我们常用的是冒泡排序，但是常用的不代表就是好的（当然这种算法思路很好）.冒泡在处理数量大的数据时表现的比较乏力，
而且顺便了解多一些的基本算法，对日常的工作肯定是比较有好处的，不然，你可能会看到有的人工作好几年了，但是依然是只会冒泡（我不是歧视冒泡，只是就一个冒泡排序算法行走江湖，是不是有点过分?老铁）

在开始正式话题之前，突然想到一个很搞笑的对”老铁”的解释，以前实训的时候班上有一个可能是老铁这个词发源地的女生说：
她们那里特别冷，老铁最开始是指那些小时候的玩伴，几个人在外面玩的时候，可能有小朋友在铁棒上伸舌头玩，又特别冷，就被冻在铁棒上拿不下来了，就很着急，怎么办呢，其他他的好朋友就在旁边帮他吹气一起舔,然后大家的舌头就都被冻在铁棒上了.
想象那种场景，感觉还是比较奇幻的，一排小朋友，翘着屁股，表情狰狞，舌头都被冻在铁棒上

let us begin!

插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法。它的基本思想是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。这个过程就类似生活中打扑克牌时给手中的扑克牌排序，开始时，手中没有扑克牌，然后不停的取出一只牌，然后比较手中牌的顺序大小，找到正确的顺序位置，然后插入进去。(一开始”类似”这种官方的话，大家就心照不宣的知道我开始抄”类似”了,再说打比方我为什么会想到打牌呢 -0-！ )

插入排序算法的基本思想是：
1.从第一个元素开始，该元素可以认为已经被排序。
2.取出下一个元素，在已经排序的元素序列中从后向前扫描。
3.如果该元素（已排序）大于新元素，将该元素移到下一位置。
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
5.将新元素插入到该位置后。
6.重复步骤2~5

理解一下： 1、2、3都已经比较清晰了，4就是一个循环，而6是一个套住4的循环 ;这样一看就明白了，原来冒泡插入这两个东西半斤八两，差异就在交换过程，其实查找过程差不多

在最完美的情况下，排序前对象已经按照要求的有序，只需要比较n−1次 ; 移动次数为0，则对应的时间复杂度为O(n)；最坏情况下,排序前对象为要求的顺序的反序，则第i趟时第i个对象必须与前面i个对象都做排序码比较,并且每做1次比较就要做1次数据移动，对应的时间复杂度为O(n^2)。所以插入排序也仅适用于少量数据的排序。


function insertSort(arr){

  var i,
      j,
      temp;
      
  for(i=1;i < arr.length;i++){
   temp = arr[i];
   j = i-1;
    while(j>=0 && arr[j] > temp){
       arr[j+1] = arr[j];
       j--;
    }//while
    arr[j+1] = temp ;
  }//for   
  return arr;
}

上面的实现过程是先取一个待排序的值与前面已排好序的数列中的元素从右往左逐个比较，如果数列中的元素比它大的话，就将元素移到下一位，直到遇到比它小的元素，便在该元素的后面插入值.

估计有人看到后，肯定会说，这个菜b，浪费老子时间，这个和冒泡有什么大的区别？能不能来个立竿见影的？就这样我不会去百度啊，一搜一大把，菜鸡

我们当然不能止步于这里，在这里我们加入折半查询来提高效率

折半插入排序



function insertPlusSort(arr) {
    var temp,
        i,
        j,
        low,
        high;
    for(i=1;i<arr.length;i++){
        temp = arr[i];
        low = 0 ;
        high = i -1 ;

        while(low <= high){
            var mid = parseInt((low + high)/2);
            if(temp < arr[mid]){
                high = mid-1;
            }else{
                low = mid +1;
            }
        }//while

        for(j=i-1;j >=low;j--){
            arr[j+1] = arr[j]
        }//for 2
        arr[low] = temp;
    }//for
    return arr;
}

希尔排序

希尔排序是我个人比较喜欢的一种排序方法，当然希尔还是脱胎于插入排序.

希尔排序算法是插入排序的一种，也称递减增量排序算法，是一种更高效的插入排序改进版本，最佳情况下时间复杂度是O(nlog2n)，最坏情况下是O(n^2)，平均情况为O(n^1.5)，所以希尔排序是非稳定排序算法。

希尔排序算法的基本思想是：
1.将整个待排元素序列分割成若干个子序列（由相隔某个“增量”g1（g1 < n）的元素组成）。
2.然后对各组元素进行插入排序。
3.重复步骤2，3（增量逐次递减，直至等于1）。
4.最后将所有子序列放在同一个组中进行直接插入排序。

希尔排序通过将全部元素分为几个区域来提升插入排序的性能。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已经排好序的了（此时插入排序较快）.



function shellSort(arr) {
    var gap = Math.floor(arr.length/2);
    
    while(gap>0){
        for(var i=gap;i<arr.length;i++){
            for(var j=i;0<j;j -= gap){
                if(arr[j-gap] > arr[j]){
                    var temp = arr[j-gap];
                    arr[j-gap] = arr[j];
                    arr[j] =temp;
                }else{
                    break;
                }
            
            }//for 2
            
        }//for
        gap = Math.floor(gap/2);
    }//while
    return arr;
}

拓展中….