插入排序法

插入排序法

设从位置0到位置i的元素是已经排序好的，则现在需要将i+1到N-1之间的元素进行插入排序。这需要执行（(N-1) - (i+1)）趟插入排序。如果所有元素已排序好，则该算法执行时间为O(N)， 当所有元素为倒序时，该算法执行最长时间O(N2)

算法：

void InsertSort(int arr[], int N)
{
    int i,j;
    for(i=1; i    {
        int tmp = arr[i];
        for(j=i;  j>0  &&  arr[j-1] > tmp;  j-- )
        arr[j] = arr[j-1];
        arr[j]=tmp;
    }
}