Copy the code code as follows:
//Direct insertion sort
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; //Note that this is j+1
}
}
//Insertion sort by half
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])//This judgment is not necessary
{
low = 0;
high = i-1;
while (low <= high) //error: while( low < high) Note that an equal sign is needed here
{
mid = (low+high)/2;
if (temp < arr[mid])
high = mid - 1;
else
low = mid + 1;
}
//After searching for the insertion position through the above half-way search, the insertion position is low or high+1, and low is equal to 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;
}
}
}