03月20, 2017

算法记录

因为非科班出身,所以在算法方面,比较薄弱。

此文章算是我在算法方面的笔记,不定期更新。

选择排序法

原理:从当前数组中找到最小的,然后和第一个交换。随后,从第二位之后的数组中找出最小的,和第二个交换。依次进行,直到最后一位。

代码如下:

var arr = [10, 8, 9, 6, 7, 5, 4, 3, 2, 1];
for(var i = 0, len = arr.length; i < len; i++) {
    var minIndex = i;
    for(var j = minIndex + 1; j < len; j ++) {
        if(arr[j] < arr[minIndex]) {
            minIndex = j;
        }
    }
    var tmp = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = tmp;
}

console.log(arr);

插入排序法

原理:第一个不动,从第二个开始,判断前一个和自己哪一个大,自己小的话,和前一个交换。第三个,判断和第二个哪个大,如果比第二个大的话,则break,否则交换,再判断和第一个哪个大。依次进行,直到最后一位。

代码如下:

var arr = [10, 8, 9, 6, 7, 5, 4, 3, 2, 1];

for(var i = 1, len = arr.length; i < len; i++) {
    for(var j = i; j > 0; j --) {
        if(arr[j] < arr[j-1]) {
            var tmp = arr[j-1];
            arr[j-1] = arr[j];
            arr[j] = tmp;
        }else {
            break;
        }
    }
}

console.log(arr);

插入排序的改进

由于在双层循环里面做交换,会比在单层循环里面做交换,更耗时,所以需要有一个新的方案。那就是先复制一份出来,利用赋值操作的方式来达到排序的功能。

该方案在大量有序时,速度方面会很快。

var arr = [10, 8, 9, 6, 7, 5, 4, 3, 2, 1];

for(var i = 1, len = arr.length; i < len; i++) {
    var e = arr[i],
        j;
    for(j = i; j > 0; j --) {
        if(arr[j-1] > e) {
            arr[j] = arr[j-1]
        }else {
            break;
        }
    }
    arr[j] = e;
}

console.log(arr);

冒泡排序

原理:

  • 比较相邻的元素。 如果第一个比第二个大,就交换他们两个。
  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。 这步做完后,最后的元素会是最大的数。
  • 针对所有的元素重复以上的步骤,除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
var arr = [10, 8, 9, 6, 7, 5, 4, 3, 2, 1];
for(var i = 0, len = arr.length; i < len; i++) {
    for(var j = i + 1; j < len; j ++) {
        if(arr[j] < arr[i]) {
            var tmp = arr[j];
            arr[j] = arr[i];
            arr[i] = tmp;
        }
    }
}

console.log(arr);

希尔算法

它的基本思想是:

先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。

可以简单地理解成分组插入。本来有一个动画效果可以iframe嵌套进来的,奈何人家网站挂了。不过我也找到一篇不错的文章,有兴趣的可以读一下:希尔排序,可以直接看下面的图,更助于理解。

var arr = [10, 8, 9, 6, 7, 5, 4, 3, 2, 1],
    len=arr.length;
for (var gap = len >> 1; gap > 0; gap >>= 1){
  for (var i = gap; i < len; i++) {
    var temp = arr[i];
    for (var j = i - gap; j >= 0; j -= gap){
        if(arr[j] > temp) {
          arr[j + gap] = arr[j];
      }else {
          break;
      }
    }
    arr[j + gap] = temp;
  }    
}

console.log(arr);

这里有一个需要学习的东西就是>>

比如:

10 >> 1

得到的结果是5。5>>1得到的结果是2。它就相当于下面的结果:

Math.floor(n/2)

归并排序

归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

原理如下(假设序列共有n个元素):

  • 将序列每相邻两个数字进行归并操作,形成floor(n/2)个序列,排序后每个序列包含两个元素
  • 将上述序列再次归并,形成floor(n/4)个序列,每个序列包含四个元素
  • 重复步骤2,直到所有元素排序完毕
       [1, 5, 6, 2, 4, 3]
       /                 \
[1, 5, 6]             [2, 4, 3]
/       \            /         \
[1]    [5, 6]      [2]       [4, 3]
       /    \                /    \
      [5]   [6]             [4]   [3]
function merge(left, right) {
  var tmp = [];

  while (left.length && right.length) {
    if (left[0] < right[0])
      tmp.push(left.shift());
    else
      tmp.push(right.shift());
  }

  return tmp.concat(left, right);
}

function mergeSort(a) {
  if (a.length === 1) 
    return a;

  var mid = ~~(a.length / 2)
    , left = a.slice(0, mid)
    , right = a.slice(mid);

  return merge(mergeSort(left), mergeSort(right));
}

var result = mergeSort([10, 8, 9, 6, 7, 5, 4, 3, 2, 1]);

console.log(result);

这里有一个语法~~,其实就是向下取整,在维基百科的代码中是用parseInt来取整。

(未完)

本文链接:www.my-fe.pub/post/javascript-algorithm-record.html

-- EOF --

Comments

评论加载中...

注:如果长时间无法加载,请针对 disq.us | disquscdn.com | disqus.com 启用代理。