/*
 * 插入排序
 * 1、从第 2 个元素开始，作为要插入的元素，跟前一个元素进行比较
 * 2、当要插入的元素比前一个元素小时，当前位置改成前一个元素的值，光标向前移一位
 * 3、如果前面还存在元素，则继续和前一个元素进行比较
 * 4、如果前面不存在元素，或者要插入的元素比前一个元素大时，当前位置为要插入元素的位置
 * 5、以此类推，进入下一轮比较
 */
#include <stdio.h>
#define SIZE 10
int main()
{
    /*
     * i, j 是 for 循环语句中的索引
     * pos 为前一个元素所在的位置，pos + 1 为当前位置
     * temp 用来保存本轮循环中要插入的元素
     * arr[] 是要排序的数组
     */
    int i, j, pos, temp, arr[SIZE];
    printf("请输入10个数：");
    for (i = 0; i < SIZE; i++) {
        scanf("%d", &arr[i]);
    }
    // 插入排序
    for (i = 1; i < SIZE; i++) {
        /*
         * 从第 2 个元素开始，作为要插入的元素
         * 设置前一个元素的位置为 pos
         */
        temp = arr[i];
        pos = i - 1;
        while (temp < arr[pos] && pos >= 0) {
            /*
             * 要插入的元素比前一个元素小
             * 并且前一个元素至少是第 1 个元素（不能再往前了）
             * 把当前位置改成前一个元素的值
             * 光标往前移一位
             */
            arr[pos + 1] = arr[pos];
            pos--;
        }
        // 从循环出来，当前位置为要插入的元素
        arr[pos + 1] = temp;
        
        // 输出数组元素
        printf("第 %d 轮：", i);
        for (j = 0; j < SIZE; j++) {
            printf("%d ", arr[j]);
        }
        printf("\n");
    }

    return 0;
}

D:\Works> set PATH=D:\Visual C++ 6\VC98\Bin;D:\Visual C++ 6\Common\MSDev98\Bin
D:\Works> set INCLUDE=D:\Visual C++ 6\VC98\Include
D:\Works> set LIB=D:\Visual C++ 6\VC98\Lib

D:\Works> cl -GX insertionSort.c

D:\Works> insertionSort.exe
请输入10个数：3 7 1 9 8 5 6 0 4 2
第 1 轮：3 7 1 9 8 5 6 0 4 2
第 2 轮：1 3 7 9 8 5 6 0 4 2
第 3 轮：1 3 7 9 8 5 6 0 4 2
第 4 轮：1 3 7 8 9 5 6 0 4 2
第 5 轮：1 3 5 7 8 9 6 0 4 2
第 6 轮：1 3 5 6 7 8 9 0 4 2
第 7 轮：0 1 3 5 6 7 8 9 4 2
第 8 轮：0 1 3 4 5 6 7 8 9 2
第 9 轮：0 1 2 3 4 5 6 7 8 9