排序之直接插入排序

一、数据结构
        约定排序均为升序排序，要排序的记录存储在线性表中，线性表由排序关键字和其它域组成，其定义如下：
        #define MAXITEM 100
        struct rec
        {
            KeyType key;        // 关键字域
            ElemType data;     // 其它数据域
        };
        struct rec sqlist[MAXITEM];
        这里的KeyType和ElemType可以是任何相应的数据类型，比如int，float或char等，在算法中，约定其为int类型。

二、算法思想
        直接插入排序的基本思想是：每一趟将一个待排序的记录，按其关键字值的大小插入到已经排序的部分文件中适当位置上，直到全部插入完成。
        假设记录存放在r[1, n]之中，r[1, i-1]是已排好序的记录；r[i-1, n]是没排序的记录。插入排序把未排序记录中的r[i]插入到r[1, i-1]之中，使r[1, i]成为有序，r[i]的插入过程就是完成排序中的一趟。随着有序区的不断扩大，使r[1, n]全部有序。

三、程序实现
        实现直接插入排序的函数如下：
        void insertsort(sqlist r, int n)        // 排序元素r[1]~r[n]
        {
            int i, j;
            for (i=2; i<=n; i++)
            {
                r[0] = r[i];                        // r[0]是监视哨
                j = i - 1;
                while (r[0].key < r[j].key)    // 进行元素移动，以便腾出一个位置插入r[i]
                {
                    r[j+1] = r[j];
                    j--;
                }
                r[j+1] = r[0];                    // 在j+1位置处插入r[0]
            }
        }
        当原始记录已按关键字递增有序排列，即为正序时，呈现最佳状态，整个排序过程总的比较次数为n-1次，记录中移动次数为2(n-1)；反之，原始记录逆序时，呈现最坏状态，整个排序过程总的比较次数为(n+2)(n-1)/2，总的移动次数为(n+4)(n-1)/2,。插入排序算法的时间复杂度是O(n²)，它是一种稳定的排序方法。