#include <iostream>
#include <string>
using namespace std;

/**
 * 插入排序
 * @param arr  数组
 * @param n  数据个数
 * @return 
 */
bool InsertSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        if (arr[i] < arr[i - 1]) { //若关键字小于前驱
            int t = arr[i]; //暂存关键字
            int j;
            for (j = i - 1; j >= 0 && arr[j] > t ; j--) { //检查前面排序的元素
                arr[j + 1] = arr[j]; //所有大于t的元素完后挪位
            }
            arr[j + 1] = t; //复制到插入位置
        }
    }
}

/**
 * 输出数组
 * @param arr 
 * @param n 
 */
void PrintArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << "  ";
    }
    printf("\n");
}
int main() {
    int arr[] = {12, 28, 20, 50, 48, 1, 5, 28};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "输出初始数组" << endl;
    PrintArray(arr, n);
    cout << "直接插入排序" << endl;
    InsertSort(arr, n);
    cout << "输出排序后数组" << endl;
    PrintArray(arr, n);
    return 0;
}

输出初始数组
12  28  20  50  48  1  5  28
直接插入排序
输出排序后数组
1  5  12  20  28  28  48  50

/**
 * 折半插入排序
 * @param arr
 * @param n
 * @return
 */
bool SplitInsertSort(int arr[], int n ) {
    for (int i = 2; i <= n ; i++) {
        arr[0] = arr[i]; //暂存关键字
        int low = 1, high = i - 1; //折半查找范围
        while (low <= high) { //折半查找
            int mid = (low + high) / 2;
            if (arr[mid] > arr[0]) { //查找左子表
                high = mid - 1;
            }else { //查找右半子表
                low = mid + 1;
            }
        }
        for (int j = i - 1; j >= high + 1 ; --j) {
            arr[j + 1] = arr[j]; //统一后移操作，空出插入位置
        }
        arr[high + 1] = arr[0]; //插入操作
    }
}