插入排序

插入排序 直接插入排序 (1)基本思想 假设待排序的记录存放在数组R[1..n]中。初始时，R[1]自成一个有序区，无序区为R[2..n]。从i=2 起直至i=n 为止，依次将R[i]插入当前的有序区R[1..i?1]中，生成含n 个记录的有序区。 (2)第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 张并插入左手的牌(有序区)中正确的位置上。为了找到这个正确的位置，需自左向右(或自右向左)将摸来的牌与左手中已有的牌逐一比较。 #include #define M 100 int R[M]; void Insert_Sort(int n) { int i, j; for(i=2; i<=n; i++) { if(R[i] < R[i-1]) { R[0] = R[i]; j = i - 1; do { R[j+1] = R[j]; j--; } while (R[0] < R[j]); R[j+1] = R[0]; } } } int main() { int i, n; puts("Input total element number of the sequence:"); scanf("%d", &n); if(n <= 0 || n > M) { printf("n must more than 0 and less than %d.\n", M); return 0; } puts("Input the elements one by one:"); for(i=1; i<=n; i++) scanf("%d", &R[i]); puts("The sequence you input is:"); for(i=1; i<=n; i++) printf("%4d", R[i]); Insert_Sort(n); // 直接插入排序 puts("\nThe sequence after insert_sort is:"); for(i=1; i<=n; i++) printf("%4d", R[i]); return 0; }