算法的总结

人生就像一列开往坟墓的列车，路途上会有很多站，很难有人至始至终陪你走完全程，当陪你的人要下车时，即便不舍，也要心存感激，然后挥手告别。---sunnyhuang

参考链接

动效展示

常见的算法

1. 冒泡排序：效率低，生产环境中很少使用

   • 依次比较相邻的两个数，如果不符合排序规矩，则调换两个数的位置。这样一遍下来，可以保证最大（或者最小）的数排在最后一位。
   • 再对除了最后一位的数进行上一步动作的排序，直到全部完成。

   function swap(myArray,p1,p2){
    var temp=myArray[p1];
        myArray[p1]=myArray[p2];
       myArray[p2]=temp;
   }
   //传递需要排序的数组
   function bubbleSort(myArray){
    var len=myArray.length;
       var i,j;
        //假如已经排好了i个数字
        for(i=0;i<len;i++){
       //对已经排好了的数字的剩下数字比较
         //这里的len-i-1,是选择了减去已经选择好了的元素和被选中的元素
         for(j=0;j<len-i-1;j++){
           if(myArray[j]>myArray[j+1]){
             swap(myArray,j,j+1)
           }
         }
        }
     return myArray;
   }
   bubbleSort([1,2,3,656,767,4,353,7])  //[1, 2, 3, 4, 7, 353, 656, 767]
   

2. 选择算法

   • 依次比较相邻的2个数，记录出已经比较的最小值（最大值）
   • 等一轮结束后把得到的相应的值，放到开头（结尾）
   • 依次寻找，直到全部找到

   //定义一个交换函数
   function swap(myArray, p1, p2) {
       var temp = myArray[p1];
       myArray[p1] = myArray[p2];
       myArray[p2] = temp;
   }
   function selectionSort(myArray) {
       var len = myArray.length;
       var i,j,min;
       for (i = 0; i < len; i++) {
            //将当前位置设为最小值
           min = i;
            //检查数组的其余部分是否更小
           for(j=i+1;j<len;j++){
             if (myArray[min] > myArray[j]) {
               min=j;
              }
           }
            //如果当前位置不是最小值，就将其换为最小值
           if(i != min){
               swap(myArray,i,min)
           }
       }
       return myArray
   }
   selectionSort([1,3,534,5,64,234,6])  //[1, 3, 5, 6, 64, 234, 534]
   

3. 插入排序

   • 首先把数组分成2个部分，已排序和未排序
   • 假定第一个元素是已经排序了的（所有这里除了第一个元素后，其余的都是未排序的）
   • 将已经排序了的在未排序中的后一个元素，放入已经排序的队列中，所有已经排序的队列增加一个，未排序的队列减少一个
   • 对刚刚放进已经排序的元素和已经在排序好了的队列中的元素比较，将其放入相应的位置。

   //定义一个交换函数
   function insertSort(myArray) {
       var len = myArray.length;
       var i, j, value;
       for (i = 0; i < len; i++) {
           //记录当前的值得大小
           value = myArray[i]  //当前序号是 i,前面有i-1个已经排好序列的元素
           //把当前值得大小和已经排好序列的元素进行比较
           //当已排序部分的当前元素大于value，
           //就将当前元素向后移一位，再将前一位与value比较
           for (j = i - 1; j > -1 && value < myArray[j]; j--) {
               myArray[j + 1] = myArray[j];
           }
           myArray[j + 1] = value;
       }
       return myArray;
   }
   

4. 快速排序

   • 在数据集中，选择一个元素作为“基数”（pivot），一般取中间值
   • 在数据中，小于“基数”的元素，都移到“j基数”的左边，大于“基数”的，都移动到“基数”的右边
   • 对“基数”的左右2个子集，不断的重复第一步和第二步，直到所有子集只剩下一个元素为止。

      function quickSort(myArray) {
        if (myArray.length <= 1) { return myArray; }
        var baseIndex = Math.floor(myArray.length / 2);
        var base = myArray.splice(baseIndex, 1)[0];
        var right = [];
        var left = [];
        for (var i = 0; i < myArray.length; i++) {
            if (myArray[i] < base) {
                left.push(myArray[i])
        } else {
            right.push(myArray[i])
            }
        }
        return quickSort(left).concat([base], quickSort(right))
    }
   
   

5. 洗牌算法（用于生成随机数组）

   1. 写下从 1 到 N 的数字
   2. 取一个从 1 到剩下的数字（包括这个数字）的随机数 k
   3. 从低位开始，得到第 k 个数字（这个数字还没有被取出），把它写在独立的一个列表的最后一位
   4. 重复第 2 步，直到所有的数字都被取出
   5. 第 3 步写出的这个序列，现在就是原始数字的随机排列

   Array.prototype.shuffle = function() {
       for (var i = input.length-1; i >=0; i--) {
           var randomIndex = Math.floor(Math.random()*(i+1));
           var itemAtIndex = input[randomIndex];
           input[randomIndex] = input[i];
           input[i] = itemAtIndex;
       }
         return input;
   }
   
   

参考链接
参考链接