算法INSERTION-SORT的JavaScript实现

作为一个有理想有抱负的小前端,怎么能不看看算法相关的书籍呢?说不准哪天前端就能写操作系统了呢。这篇文章就来介绍《算法导论 第三版》中的第一个算法INSERTION-SORT。别被名字虎住了,中文翻译过来就是插入排序,就是一种将一堆无序数字或者元素按照一个规则排序的方法而已。

插入排序原理介绍

这个排序原理非常简单,以打牌为例,我们左手拿牌,右手摸牌。

1. 最开始时我们左手手上一张牌都没有,然后一张一张的从牌堆里摸牌。
2. 摸第一张牌的时候,我们完全不用排序,因为左手根本没有牌。
3. 而从第二张开始,我们是把右手上的牌按照某个顺序找一个合适的位置插入到左手上来的。
4. 如此循环,直到我们把牌堆的牌摸完为止,我们左手上的牌也就排好序了。

上面步骤可以看出,从第二张牌开始,我们左手上的牌始终是有顺序的。并且每次摸牌插入的时候需要遍历左手上的牌来寻找插入位置。

这就是插入排序的原理,是不是很简单呢?

伪代码

书中给出了实现的伪代码,并不能真正的执行,如下:

INSERTION-SORT(A)
for j=2 to A.length
    key = A[j]
    // InsertA[j] into the sorted sequence A[1..j-1]
    i = j-1
    while i>0 and A[i]>key
        A[i+1] = A[i]
        i = i-1
    A[i+1] = key

JavaScript实现

function insertion_sort(arr) {
   var i,j;
   console.log('开始时,左手中的牌有【%s】',arr.slice(0,1).toString());
   // 循环从第二张牌开始
   for(i=1;i<arr.length;i++){
      // 右手牌的大小
      var right = arr[i];
      console.log('-->摸第%d张牌,摸到点数%d,开始排序找位置',i+1,right);

      // 循环左手中的牌,从后向前循环,直到右手的牌比循环中的牌大为止
      // 循环结束时,j即为右手牌的上一张牌
      for(j=i-1;j>=0&&arr[j]>right;j--){
         arr[j+1]=arr[j];
      }
      console.log('找到位置%d,移动位置%d至位置%d',j+1,i,j+1,right,'=>',arr[j+1]);
      arr[j+1]=right;
      console.log('此时左手中的牌有【%s】',arr.slice(0,i+1).toString());
   }

   console.log('排序完成【%s】',arr.toString());
}

上面代码中打印了整个排序过程,我们使用一个例子来测试一下。如下:

// 假设这个A是我们需要排序的数字
var A=[3,4,9,2,6,5];

// 调用我们的插入排序方法
insertion_sort(A);

整个过程打印如下:

开始时,左手中的牌有【3】
-->摸第2张牌,摸到点数4,开始排序找位置
找到位置1,移动位置1至位置1 4 => 4
此时左手中的牌有【3,4】

-->摸第3张牌,摸到点数9,开始排序找位置
找到位置2,移动位置2至位置2 9 => 9
此时左手中的牌有【3,4,9】

-->摸第4张牌,摸到点数2,开始排序找位置
找到位置0,移动位置3至位置0 2 => 3
此时左手中的牌有【2,3,4,9】

-->摸第5张牌,摸到点数6,开始排序找位置
找到位置3,移动位置4至位置3 6 => 9
此时左手中的牌有【2,3,4,6,9】

-->摸第6张牌,摸到点数5,开始排序找位置
找到位置3,移动位置5至位置3 5 => 6
此时左手中的牌有【2,3,4,5,6,9】

排序完成【2,3,4,5,6,9】

总结

这个排序很简单,不过书中分析得比较复杂,有循环不变式及其证明步骤,有时间复杂度的计算方法,有算法性能的分析等等。慢慢看吧。


还没有关注订阅号的朋友,扫描二维码,或者识别图片二维码关注哦。

有最新干货会第一时间通知您哦。

image.png



打赏作者

发表评论

电子邮件地址不会被公开。 必填项已用*标注