排序（之插入排序）

插入排序是穩定的排序，平均情況和最壞情況的算法復雜度為O(n^2)，最好情況為O(n)；空間復雜度為：O(1)。

[cpp] 
#include<stdio.h> 
 
void InsertSort(int a[],int n) 
{ 
    int i,j,rc; 
 
    for(i=1;i<n;i++) 
    { 
        if(a[i-1]>a[i]) 
        { 
            rc=a[i]; 
            j=i; 
            while(j-1>=0 && rc<a[j-1]) 
            { 
                a[j]=a[j-1]; 
                j--; 
            }    www.2cto.com
            a[j]=rc; 
        } 
    } 
} 
 
void main() 
{ 
    int a[]={49,38,65,97,76,13,27,49}; 
    int n=sizeof(a)/sizeof(a[0]); 
 
    InsertSort(a,n); 
 
    for(int i=0;i<n;i++) 
    { 
        printf("%d\n",a[i]); 
    } 
}