//直接插入排序
void DirectInsertionSort(int* arr, int nLen)
{
    int i, j;
    for (i=1; i<nLen; i++)
    {
        int temp = arr[i];
        for (j=i-1; j>=0; j--)
        {
            if (temp < arr[j])
                arr[j+1] = arr[j];
            else
                break;
        }
        if (j+1 != i)
            arr[j+1] = temp;    //注意這里是j+1
    }
}

//折半插入排序
void BinaryInsertionSort(int* arr, int nLen)
{
    int i, j;
    int low, mid, high;
    for (i=1; i<nLen; i++)
    {
        int temp = arr[i];
        if (temp < arr[i-1])//這個判斷可不要
        {
            low = 0;
            high = i-1;
            while (low <= high) //error: while( low < high) 注意這里還需要 等號
            {
                mid = (low+high)/2;
                if (temp < arr[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            }
            //經(jīng)過上面的折半查找插入位置后，這時插入位置為low或者high+1,這時low等于high+1
            //for (j=i-1; j>=high+1; j--)
            //{
            //    arr[j+1] = arr[j];
            //}
            //arr[high+1] = temp;

            for (j=i-1; j>=low; j--)
            {
                arr[j+1] = arr[j];
            }
            arr[low] = temp;
        }
    }
}