直接插入排序
2017-11-15 本文已影响0人
Random_
基本思想
直接插入排序的基本操作是将一个记录插入到已经排好序的有序列表中，从而得到一个新的、记录数增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)
在性能上优先于冒泡排序和选择排序
最好情况下，要排序的本身就是有序的
最坏情况下，需要比较（n+2）（n-1）/2次，记录的移动次数为（n+4）(n-1)/2次
平均比较和移动次数为你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>
