折半插入排序

最近更新于 2024-05-06 07:58

环境

平台工具集：Visual Studio 2022 v143
C 语言标准：C17
字符集：Unicode

算法实现

折半插入排序是直接插入排序的改进算法，大体类似，都是先分一个有序数组出来，再挨个把无序数组元素插入有序数组的适当位置。只是插入位置的查找方法不同，直接插入排序是挨个从有序数组的尾巴向开头比较，而折半插入排序使用折半查找算法，在查找部分的时间复杂度由 O(n) 降到 O(nlog_2n)，但是移动元素的时间复杂度依然没有改变，总体时间复杂度还是 O(n^2)，折半插入排序是稳定的排序算法。

void sort(int array[], int n)
{
    int low, high;
    for (int i = 1; i < n; ++i)
    {
        int tmp = array[i];
        for (low = 0, high = i - 1; high >= low;)
        {
            int mid = (low + high) / 2;
            if (tmp < array[mid])
            {
                high = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
        }
        for (int j = i - 1; j >= low; --j)
        {
            array[j + 1] = array[j];
        }
        array[low] = tmp;
    }
}