[数据结构与算法]插入排序外加折半查找

//KEEP CALM AND CARRY ON
#include "stdio.h"
//最普通的插入排序，设置哨兵
void InsertSort(int A[], int n) {
    int j;
    for (int i = 2; i <= n; i++) {
        //当当前值小于前一个时
        if (A[i] < A[i - 1]) {
            //设置哨兵
            A[0] = A[i];
            //开始转移，保持稳定，且第二个不能是≤为了稳定
            for (j = i - 1; A[0] < A[j]; --j) {
                A[j + 1] = A[j];
            }
            A[j + 1] = A[0];
        }
    }
}

//插入折半排序
void InsertSort_Search_half(int A[], int n) {
    int i, j, low, high, mid;
    for (i = 2; i <= n; i++) {
        low = 1;
        high = i - 1;
        A[0] = A[i];
        while (low <= high) {
            mid = (high + low) / 2;
            if (A[mid] > A[i]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

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

int main() {
    int a[] = {-1, 4, 5, 3, 1, 2, 7, 88, 55, 33, 2, 99};
    InsertSort_Search_half(a, 11);
    for (int i = 1; i < 12; ++i) {
        printf("%d  ", a[i]);
    }
}

注意

1.设置A[0]为哨兵
2.注意折半查找的应用

 while (low <= high) {
            mid = (high + low) / 2;
            if (A[mid] > A[i]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

这个运行过之后，被插入点就变成low(等价为 high+1 )

该行和折半查找的不同在于

		else {
                low = mid + 1;
            }

即当A[mid]≤要查找的值时： low均为mid+1;
小于时不用讨论，
等于时，仍要加一是为了保持稳定的特性，当＋1时，low 指向的地方也大于要查找的值了，正好在这里放置