插入排序——直接插入排序

/*
 *直接插入排序算法思想:
 *  将整个数据表分成左右两个子表,其中左子表为有序表,右子表为无序表;
 *  整个排序过程就是将右子表中的元素逐个插入到左子表中,直到右子表为空,
 *  而左子表成为新的有序表。
 */

/*
 *算法过程分析:
 *  将待排序的元素存放在数组r[n+1]中,在初始状态下,r[0]为监视哨,r[1]为有序区,
 *  r[2]~r[n]为无序区。当操作r[i+1]时,此时r[1]~r[i]为有序区,则需要把r[i+1]分别
 *  与r[i]~r[1]关键字比较。用r[j+1](1<=j<=i)与r[i+1]比较,若r[i]较小,则赋值为
 *  r[j+1]=r[j],否则赋值为r[j+1]=r[i+1]
 */

/*
 *算法性能分析:
 *  算法执行时比较、移动元素的次数约为(n*n)/4,所以算法时间复杂度为O(n*n);
 */

#include <stdio.h>
#define length 9
void InserSort(int *order)
{
    int i=0,j=0;
    for(i=2;i<length;i++)
    {
        order[0]=order[i];//设置监视哨
        j=i-1;
        while(order[0]<order[j])
        {
            order[j+1]=order[j];
            j--;
        }
        order[j+1]=order[0];//不会越界,最坏的情况是j=0,相等,依然会停止循环
    }
    return;
}
int main()
{
    int order[length]={0,49,38,65,97,76,13,27,49};
    //0是监视哨位,不参与排序
    InserSort(order);
    int i=0;
    for(i=1;i<length;i++)printf("%d  ",order[i]);
    return 0;
}
相关文章
相关标签/搜索