插值排序

　　以前学到这里的时候简单的认为插值必须是保持数组中的值已经一定顺序排列好了，现在学习到了一些其他算法，才认识到这只是把值插入。将这种插入的想法应用到查找并对元素进行排序的算法上，就可以得到插入排序（Insertion-Sort）算法。插入排序的时间复杂度为O(n^2)，比选择排序好不了多少，但对同样多的数据进行排序，插排还是要比选择排序快一些。

　　最初的代码:

#include<stdio.h>
int main()
{
    int a[10]={260,240,220,200,160,140,120,100,80};
    int i,j=0,k,x;
    printf("请输入要插入的数值:");
    scanf("%d",&x);
    for(i=0;i<9;i++)                
    {
        if(a[i]<x)
            break;
        k=i;
    }
    for(j=8;j>=k;j--)
    {
        a[j+1]=a[j];
    }
    a[i]=x;
    for(i=0;i<10;i++)                
    {
        printf("%d ",a[i]);
    }
    printf("
");
    return 0;
}

　　插入排序：

#include <stdio.h>

int main()
{
    int arr[] = {6,4,1,3,5,2};

    for(int i = 1; i < sizeof(arr)/sizeof(int); i++)
    {
        int temp = arr[i];
        int j = i - 1;
        while(j >= 0 && arr[j] > temp)
        {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = temp;
    }
    for(i = 0; i < sizeof(arr)/sizeof(int); i++)
        printf("%d ", arr[i]);
    printf("
");
    return 0;
}