欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

JavaScript插入排序算法原理与实现方法示例

程序员文章站 2022-04-24 13:29:32
本文实例讲述了javascript插入排序算法原理与实现方法。分享给大家供大家参考,具体如下: 一、插入排序简介: 想象我们斗地主,摸排阶段,手里的牌都按照从小到大排序...

本文实例讲述了javascript插入排序算法原理与实现方法。分享给大家供大家参考,具体如下:

一、插入排序简介:

想象我们斗地主,摸排阶段,手里的牌都按照从小到大排序。如果每摸一张牌,我们就把他插入合适的位置,使得它比后面位置的牌小,比前面位置的牌大或者相等。

类似这样的一种排序方法就是插入排序:

在一个数组a中,我们要实现升序排序,假设我们前面已经对a[0]a[k]排好序,现在需要将a[k+1]的值放入合适的位置。

(为简便,此处不讨论k的取值范围,只是用它代表数组的某个位置)

1、首先,我们将a[k+1]的值与a[k]比较,如果小于a[k]就交换两者的值,相等或者大于都不需要交换。假设交换了,那么现在a[k]存放的是原先a[k+1]的值,新的a[k]的值有可能比前面位置的值小,故又需要再次对a[k]a[k-1]进行比较,以此类推。直到发现某个位置a[p](p是0到k之间数)的值已经不比a[p-1]的值小,比较结束,a[k+1]的值已经放入合适的位置a[p]。或者a[k+1]的值比前面的值都小,一步步交换之后a[0]存放了原先a[k+1]的值,那么也结束。现在a[0]a[k+1]是一个有序数组。

2、对a[k+1]之后a[k+2]a[a.length-1]的每一个元素都依次进行相同操作,最终得到一个有序数组。

二、javascript实现插入排序

function insertion_sort(arr) {
  var temp;
  for (var i = 1; i < arr.length; i++) {
    for (var j = i-1; j >=0; j--) {
      if (arr[j+1]<arr[j]) {
        temp=arr[j+1];
        arr[j+1]=arr[j];
        arr[j]=temp;
      }else if (arr[j+1]>=arr[j]) {
        break;
      }
    }
  }
  return arr;
}
var a=[11,2,3,445,7,32,71,8,94];
console.log(insertion_sort(a));
var b=[94,11];
console.log(insertion_sort(b));

说明:

1、一旦发现arr[j+1]的值不比前面的值小,就可以结束内层循环了,break实现这一功能;

2、内层循环用arr[j+1]的原因:初始时a[j](即a[i-1])代表a[i]前一个位置,进入循环后,a[j+1]就表示了a[i]的位置,实现了a[i]a[i-1]的第一次比较;随着j第一次自减,实际上比较了a[i-1]a[i-2];依次类推。如果将arr[j+1]改成a[i]是不行的,因为没有实现位置的移动。

上述代码使用在线html/css/javascript代码运行工具http://tools.jb51.net/code/htmljsrun测试运行结果如下:

JavaScript插入排序算法原理与实现方法示例

ps:这里再为大家推荐一款关于排序的演示工具供大家参考:

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具:

更多关于javascript相关内容感兴趣的读者可查看本站专题:《javascript数学运算用法总结》、《javascript数据结构与算法技巧总结》、《javascript数组操作技巧总结》、《javascript排序算法总结》、《javascript遍历算法与技巧总结》、《javascript查找算法技巧总结》及《javascript错误与调试技巧总结

希望本文所述对大家javascript程序设计有所帮助。