减小字体
增大字体- ·上一篇文章：希尔排序算法
- ·下一篇文章：Microsoft Visual C++
直接插入排序算法
-->
[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]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | #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 |
直接插入排序算法
