挑战程序设计竞赛 数据结构与竞赛笔记插入排序
问题:
用插入排序,将一组有n个数的数组,排序,排序结果由小到大,2<n<=10000
我的想法:
for(i=1;i<n;i++)
{ for(j=0;j<i;j++)
{
if(str[i]<str[j])
{ t=str[j];
str[j]=str[i];
str[i]=str[j];}
}
}
使用了两个for语句,n较大时,不算好方法
书上:
for(i=1;i<n;i++)
{
v=str[i];
j=i-1;
while(j>0&&str[j]>v)
{
str[j+1]=str[j];
j--;
}
str[j+1]=v;
}
思路是将:整个数组分为未排序的和已经排序的部分。
i表示未排序的部分第一个
j表示在已经排序的部分中,从最后以个已经排序的开始往str[0]走,
如果,在已经排序中有str[j]大于str[i],
那么 首先在已排序的部分中第一个数一定是j最大时即j=i-1,时,这时
将j+1也就是str[i]变为str[j]; 那么这一步后,有str[j]=str[i],
然后,j减一,如果还有str[j]>v,那么在再, str[j+1]=str[j];
这一步后,造成图中第三步
......
直到str[j]这个数不大于v,就跳出循环,使这个数的上一位str[j+1]=v;
,
可能我讲的一点也不清楚,,,,图中用长度表示数的大小