直接插入排序

直接插入排序 【基本思想】 直接插入排序(Straight Insertion Sorting)的基本思想是:把n个待排序的元素看成为一个有序和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。 把a[i]插入到a[0]，a[1]，...,a[i-1]之中的具体实施过程为:先把a[i]赋值给变量t,然后将t依次与a[i-1],a[i-2],...进行比较,将比t大的元素右移一个位置,直到发现某个j(0<=j<=i-1),使得a[j]<=t或j为(-1),把t赋值给a[j+1]. 【第i-1趟直接插入排序】 通常将一个R[i](i=2，3，…，n-1)插入到当前的有序区，使得插入后仍保证该区间里的记录是按关键字有序的操作称第i-1趟直接插入排序。 排序过程的某一中间时刻，R被划分成两个子区间 R[1((i-1](已排好序的有序区)和R[i((n](当前未排序的部分，可称无序区)。 直接插入排序的基本操作是将当前无序区的第1个记录R[i]插人到有序区R[1((i-1]中适当的位置上，使R[1((i]变为新的有序区。因为这种方法每次使有序区增加1个记录，通常称增量法。 插入排序与打扑克时整理手上的牌非常类似。摸来的第1张牌无须整理，此后每次从桌上的牌(无序区)中摸最上面的1张并插入左手的牌(有序区)中正确的位置上。为了找到这个正确的位置，须自左向右(或自右向左)将摸来的牌与左手中已有的牌逐一比较。 【一趟直接插入排序方法】 【简单方法】 首先在当前有序区R[1..i-1]中查找R[i]的正确插入位置k(1?k?i-1);然后将R[k((i-1]中的记录均后移一个位置，腾出k位置上的空间插入R[i]。 若R[i]的关键字大于等于R[1((i-1]中所有记录的关键字，则R[i]就是插入原位置。 【例如】:按从小到大对一个数组进行排序: #include void InsertSort(int array[],int length) { int i,j,flag; for(i=1;i=0&&array[j]>flag;j--) { array[j+1]=array[j]; } array[j+1]=flag; } } int main() { int a[10]; int i; for(i=0;i<10;i++) scanf("%d",&a[i]); InsertSort(a,10); for(i=0;i<10;i++) printf("%d\n",a[i]); return 0; }