基本思想
直接插入排序的基本操作是將一個記錄插入到已經排好序的有序列表中，從而得到一個新的、記錄數(shù)增1的有序列表。
void InsertSort(SqList *L){
int i,j;
for(i=2;i<=L->length;i++){
if（L->r[i]<L->r[i-1]）{
L->r[0]=L->r[i];
for(j=i-1;L->r[j]>L->r[0];j--){
L->[j+1]=L->r[j];
}
L->r[j+1]=L->r[0];
}
}
}
復雜度分析
只需要一個記錄的輔助空間
時間復雜度為O（n2)
在性能上優(yōu)先于冒泡排序和選擇排序
最好情況下，要排序的本身就是有序的
最壞情況下，需要比較（n+2）（n-1）/2次，記錄的移動次數(shù)為（n+4）(n-1)/2次
平均比較和移動次數(shù)為你n^2/4
js代碼
<!doctype html>
<html>
<head>
<title></title>
<script type="text/javascript">
function InsertSort(arr){
var i,j;
for (var i = 2; i <=arr.length; i++) {
if (arr[i]<arr[i-1]) {
arr[0]=arr[i];
for (var j=i-1; arr[j]>arr[0]; j--)
arr[j+1]=arr[j];
arr[j+1]=arr[0];
}
}
}
var array=[5,3,4,6,2];
InsertSort(array);
document.write(array[i]);
</script>
</head>
<body>
</body>
</html>
