本文介绍 JavaScript 中直接插入排序的实现原理与代码。通过扩展 Array.prototype 定义 insertionSort 方法，利用循环和 while 语句将无序元素插入有序区间，生成最终有序数组。
直接插入排序原理
1、基本思想
假设待排序的记录存放在数组 R[1..n] 中。初始时，R[1] 自成 1 个有序区，无序区为 R[2..n]。从 i=2 起直至 i=n 为止，依次将 R[i] 插入当前的有序区 R[1..i-1] 中，生成含 n 个记录的有序区。
JavaScript 代码实现
代码如下:
<!doctype html>
<html>
<head><title>javascript直接插入排序</title>
<meta charset = "utf-8" />
</head>
<body>
<script>
var arr = [];
for(var i=0;i<20;++i)
{
arr.push(~~(Math.random()*20));
}
document.write(arr+"<br/>");
Array.prototype.insertionSort = function()
{
var j;
var value;
for(var i=1;i<this.length;i++)
{
j=i;
value = this[j];
while(j>0 && this[j-1]>value)
{
this[j] = this[j-1];
j--;
}
this[j] = value;
}
}
arr.insertionSort();
document.write(arr+"<br/>");
</script>
</body>
</html>