直接插入排序(Insertion Sort)
基本思想:每次將一個待排序的記錄意荤,按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子序列中的適當(dāng)位置琉雳,直到全部記錄插入完成為止益缠。開始時有序表中只包含1個元素蒂胞,無序表中包含有n-1個元素税手,排序過程中每次從無序表中取出第一個元素蜂筹,將它插入到有序表中的適當(dāng)位置,使之成為新的有序表芦倒,重復(fù)n-1次可完成排序過程艺挪。
代碼實現(xiàn)C語言版
#include<stdio.h>
void InsertSort(int R[], int n)
{
int i, j, k;
int temp;
for(i=1; i<n; i++)
{
j = i - 1;
temp = R[i];
while(j>=0 && temp < R[j])
{
R[j+1] = R[j];
j--;
}
R[j+1] = temp;
printf("the %d times:", i);
for(k=0; k<9; k++)
{
printf("%d ", R[k]);
}
printf("\n");
}
}
int main()
{
int a[9] = {9, 3, 1, 4, 2, 7, 8, 6, 5};
int i;
printf("begin\n");
printf("before:");
for(i=0; i<9; i++)
{
printf("%d ", a[i]);
}
printf("\n\n");
printf("InsertSort...\n");
InsertSort(a, 9);
printf("\nafter:");
for(i=0; i<9; i++)
{
printf("%d ", a[i]);
}
printf("\nend\n");
return 0;
}
輸出結(jié)果: