|
这篇文章主要介绍了JavaScript插入排序算法原理与实现方法,简单分析了插入排序的概念、原理并结合实例形式分析了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前一个位置，进入循环后，a[j+1]就表示了a的位置，实现了a和a[i-1]的第一次比较；随着j第一次自减，实际上比较了a[i-1]和a[i-2]；依次类推。如果将arr[j+1]改成a是不行的，因为没有实现位置的移动。
上述代码使用在线HTML/CSS/JavaScript代码运行工具http://tools.jb51.net/code/HtmlJsRun测试运行结果如下：
PS：这里再为大家推荐一款关于排序的演示工具供大家参考：
在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具：
http://tools.jb51.net/aideddesign/paixu_ys
更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》
希望本文所述对大家JavaScript程序设计有所帮助。 | 
发表于 2018-8-6 10:03:17
