[t]直接插入排序(Insertion Sort)：[/t]
基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止。
[t]程序分析[/t]
| a[0] | a[1] | a[2] | a[3] | a[4] | a[5] | a[6] | a[7] | a[8] | a[9] |
| 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
调用排算法：
| a[0] | a[1] | a[2] |
| 10 | 9 | 8 |
| a[i-1] | a[i] |
temp=a[i] //所以temp=9;
继续执行 for(j=i-1;a[j]>temp;j--)
| j=i-1 | j-- |
| 0 | -1 |
执行循环体中 a[j+1]=a[j];后
即将a[0]赋值给a[1]，即将10覆盖9
得到 a[0]=10, a[1]=10;
| a[0] | a[1] | a[2] |
| 10 | 10 | 8 |
| a[j] | a[j+1] |
最后for语句j--; j=-1;
继续执行 a[j+1]=temp; 此时a[0]=9；完成第一趟排序。
| j | j+1 |
| -1 | 0 |
| a[0] | a[1] | a[2] |
| 9 | 10 | 8 |
[t]源程序如下:[/t]
#include
#define N 10
void insertsort(int a[])
{
int i,j,temp;
for(i=1;i<N;i++)
if(a[i]<a[i-1]) { temp=a[i]; //将待排序的数放到temp中 for(j=i-1;a[j]>temp;j--) //向前移动数字
a[j+1]=a[j];
a[j+1]=temp;
}for(i=0;i<N;i++)
printf("%d ",a[i]);}int main()
{
int a[N]={10,9,8,7,6,5,4,3,2,1};
insertsort(a);
return 0;}
- 直接插入排序
| j=i-1 | j-- |
| 0 | 1 |