插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
<script type="text/javascript">
var InsertionSort ={};
InsertionSort.arr =[];
InsertionSort.init =function(){
var arr =this.arr;
arr.length =0;
arr.push(1); //arr[0]
arr.push(2);
arr.push(3);
arr.push(10); //arr[3]
arr.push(9); // 因 arr[3]>arr[4] 则 arr[preIndx+1] = arr[preIndex]
//比较值的前一值即arr[2]=3 < 当前比较值，退出循环
//arr[4]=arr[3] ，退出后 arr[preindex-1] =current;此时preindex-1 =3
arr.push(12); //完成排序后数组变成1，2，3，9，10，12，0 12>大于前面一值直接退出比较
arr.push(0); //current=arr[6] =0;
// 12>0 arr[6] =12, 比较值往后移动一位，直到不在满足条件
}
InsertionSort.show =function()
{
for(var i=0;i<this.arr.length;i++)
{
console.log(this.arr[i]);
}
}
InsertionSort.insertionSort = function(arr)
{
var len = arr.length;
var preIndex , current ;
for(var i=1;i<len;i++)
{
preIndex =i-1;
current =arr[i];
while(preIndex>=0 && arr[preIndex]>current)
{
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current; //把当前元素赋值给最后一个交换位置的元素
//继续下一个未排序元素，与已排序元素做比较。
}
return arr;
}
InsertionSort.init();
console.log("unsorted arry");
InsertionSort.show();
console.log("sorted arry");
InsertionSort.arrary = InsertionSort.insertionSort(InsertionSort.arr);
InsertionSort.show();
</script>
原文：https://www.cnblogs.com/ms_senda/p/11397286.html