小哥哥为你通俗讲算法-忘都忘不掉

2018-03-21

算法简单说

先来讲经典例题：出栈入栈、快排、插入排序、折半插入排序、希尔排序

好吧，我讲实话，前端实际工作中很少写这个东西，都是以前写好的东西，封装成util文件，即使要用也是直接调函数的，基本不手写；下面从插入排序开始其实都是以前写好的

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

let us begin!

用某一例题演示（怎么这张图好大-_-!）

像看到这种题目，第一时间看这句：入栈序列是m、n、x、y、z
把下面这张图先画出来

先来看上面的c、d选项，像这种最容易判断，具有统一特点的：”n”先出栈。
直接就能得出结论：n一定是入栈之后立马出栈；那么接下来跟着出栈的必然是 m 或者 x 或者 z，和y没有半毛钱关系。
直接锁定选项c一定是错的
n出栈后的情况如下图所示：

接下来，再来看选项A、B、D,就很顺其自然了
A一定是：m入栈之后直接出栈；n入栈之后直接出栈；x、y、z也都是入栈后直接出栈
B的顺序是： m入栈；n入栈；x入栈后直接出栈；n跟着出栈；y入栈之后直接出栈；z入栈之后直接出栈；最先进去的m最后出栈
D的顺序是： m入栈；n入栈后直接出栈；m跟着出栈；x入栈；y入栈后直接出栈；z入栈后直接出栈；x出栈

快速排序

作为最常见的排序，平均O(nlogn),最坏O(n^2),最优O(nlogn),但快速排序通常明显的优于其它算法
快排思路：

从数组的中间位置挑选出一个数据作为基准（pivot）
重新排序数组，所有元素比基准小的放在左边，比基准大的放在右边，相同的任意摆放，
一趟结束，此时基准处于中间位置，上述的一次操作叫分区（partition）
递归的对第一次分区后的左边数组、右边数组分别分区

js实现如下：

quickSort([1,8,5,9,6]) //[1,5,6,8,9]

function quickSort(arr){
   // length 为1是结束递归的判断标志 
   if(arr.length === 1) return ; 
   // 1 找数组的中间位置，得到这个值，并在当前数组删除中间值
   var pIndex = Math.floor(arr.length/2),
       pivot = arr.splice(pIndex,1)[0],
       left = [],
       right = [];
   // 2 剩余的数组中，把比中间值小的放左边，大的放右边
   for(var i =0;i<arr.length;i++){
      if(arr[i] < pivot){
         left.push(arr[i])
      }else{
         arr.push(arr[i])
      }
   }
   // 3 递归重复判断，将最终的左数组和中间值和右边数组拼接在一起
   // PS. 当当前数组里只有1个、2个或3个数据的时候进行分区，结果一定是有序的
   return quickSort(left).concat([pivot],quickSort(right))         
}

插入排序

插入排序（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;
}

折半插入排序



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;
}

拓展中….