void InsertSort(ElemType A[], int n) {
int i, j, low, high, mid;
for (i = 2; i <= n; i++) {
A[0] = A[i];
low = 1;
high = i - 1;//设置折半查找的范围，从1到i-1,A[0]用来暂存元素
while (low <= high) {
mid = (low + high) / 2;
if (A[mid].key > A[0].key) high = mid - 1;//查找左半子表
else low = mid + 1;//查找右半子表
}
for (j = i - 1; j >= high + 1; --j)
A[j + 1] = A[j];//统一向后移动元素，空出插入位置
A[high + 1] = A[0];//插入操作
}
}
