直接插入排序
#include <stdio.h>void InsertSort(int A[],int n){int temp;int j;for(int i = 1;i < n;i++){if(A[i] < A[i-1]){temp = A[i];//两个常见错误：//1.内层循环条件不能写成temp < A[j] && j >= 0//2.内层循环条件不能写成用A[i]与A[j]比较，必须用temp与A[j]比较for(j = i -1;j >= 0 && temp < A[j];j--){A[j+1] = A[j];}A[j+1] = temp;}}
}int main() {int nums[] = {5, 2, 4, 6, 1, 3};int n = sizeof(nums) / sizeof(nums[0]);InsertSort(nums, n);for (int i = 0; i < n; i++) {printf("%d ", nums[i]);}printf("\n");return 0;
}折半插入排序
折半插入排序是对直接插入排序的一种优化，在将一个元素插入到已排序序列时，使用折半查找（二分查找）来确定该元素应插入的位置，从而减少比较次数。
void InsertSort(int A[],int n){int temp;int low;int high;for(int i = 1;i < n;i++){if(A[i] < A[i-1]){temp = A[i];low = 0;high = i-1;//折半查找插入位置，循环结束时low就是temp应该插入的位置while(low <= high){//折半查找结束条件是high<low，并且由于high的每次变小都是mid-1，//意味着当刚好high<low时，low等于midint mid = (low + high)/2;if(A[mid] > temp) high = mid - 1;elselow = mid + 1;//A[mid]等于temp时，仍然向右查找确保稳定性}//for(int j = i-1;j > high;j--)//for(int j = i-1;j >= high+1;j--)for(int j = i-1;j >= low;j--) //上面两行也正确，但j>=low逻辑更加清晰A[j+1] = A[j];A[low] = temp;//A[high+1] = temp;//上面一行的写法也对，但是low就是temp应该插入的位置，A[low] = temp;逻辑更加清晰}}
}
