插入排序

插入排序的原理：

將待排序的元素分為兩部分，第一部分用來保存已排序的，第二部分保存還未排序的，初始時第一部分為空，第二部分為整個數組；

開始排序：

從第二部分取出一個元素放到第一部分，接著又取出一個元素插到第一部分（插入到合適位置），第二個元素插入時就和第一部分中現有的元素比較，直到插入到準確位置，然后一個一個的將第二部分的元素插入到第一部分直到排好序；

一般寫程序之前要先用自然語言有個清晰的描述然后才用程序語言來寫，上面算是自然語言吧，這也只是一種方法，其實有了插入排序的思想，怎么插都行，我下面寫一個插入排序也是按自己喜好來插，關鍵是要理解插入排序的思想就好了；

    #include<stdio.h>  
    #include<malloc.h>  
    #define M 1000  
    void InsertSort(int*,int);  
    int main()  
    {  
        int n;  
        int * a=new int[M];  
        printf("輸入待排序元素個數：\n");  
        scanf("%d",&n);  
        for(int i=0;i<n;++i)  
            scanf("%d",a+i);  
        InsertSort(a,n);  
        printf("排序后：\n");  
        for(int i=0;i<n;++i)  
            printf("%d ",*(a+i));  
        return 0;  
    }  
    void InsertSort(int*a,int n)  
    {  
        int i,j,temp;  
        for(i=1;i<n;++i)  
        {  
            if(*(a+i)<*(a+i-1))  
            {  
                temp=*(a+i);  
                j=i-1;  
                while(temp<*(a+j))  
                {  
                    *(a+j+1)=*(a+j);  
                    j--;  
                }  
                *(a+j+1)=temp;  
            }  
        }  
    }  

首先把數組的第一個元素放到了第一部分，然后用for遍歷后面的所有元素，一個一個的插入到第一部分；

這里我們要承認任何時刻第一部分的所有元素是有序的，我們將第二部分一個元素插入到第 一部分應該首先和第一部分中的最后一個元素比較，如果大于第一部分中最大的元素那么就放在末尾就行了，如果小于最戶一個元素那么這個元素就前移和前一個元 素比較，直到移到合適的位置，這里就會有有一些值得賦值操作，有的人就不知道咋弄了，看下我的代碼大家借鑒一下，首先是設了一個變量temp來保存正在移 動的值；

雖然快速排序很好，不過了解一下其他排序的算法對自己的編程思維也是有好處的，