直接插入排序

秒速五厘米 2022-03-22 08:58 92阅读 0赞

### 题目描述： ###

直接插入排序的原理

##### 分析： #####

直接插入排序，故名思义，插入是这个排序中最重要的部分。  
我们可以这样理解：  
对一个数组排序，我们将这n个数，依次作为一个关键数。即当这个数为关键数的时候，其他的所有数，比这个关键数小的数放在这个关键数的左边；比关键数大的数放在这个关键数的右边。  
那么当所有的数都做过关键数的时候，那么这个数组一定是有序的了。  
从这个理解上看，这个代码是很复杂的。而且时间负责度也是很高的。  
但实际上，写代码的时候是可以优化的。  
具体代码如下：

#include"stdio.h"
    #include"string.h"
    //直接插入排序（升序）
    //注意在这个程序中，我没有个下标为0的数组元素赋值。
    //因为我将用下标为0的数组元素保存关键字。
    void InsertSort(int digit[])
    {
        int i,j;
        //这里是从2开始，将每一个元素与他前一个元素进行比较
        for(i=2;i<10;i++)
        {
        //成立这表示第i个元素小于第i-1 个元素，则需要将第i个元素重新插入至合适位置
            if(digit[i]<digit[i-1])
            {
                digit[0]=digit[i];//保存关键字
                for(j=i-1;digit[j]>digit[0];j--)//这里是从第i-1 个元素依次递减，并且条件是小于关键字
                {
                    digit[j+1]=digit[j];
                }
                digit[j+1]=digit[0];//循环结束时，第j个元素小于关键字，所以将关键字赋值到j+1的位置
            }
        }
    }
    int main()
    {
        int digit[10];
        int i;
        for(i=1;i<10;i++)
            scanf("%d",&digit[i]);
        digit[0]=0;
        InsertSort(digit);
        for(i=1;i<10-1;i++)
        {
            printf("%d ",digit[i]);
        }
        printf("%d\n",digit[i]);
    }