插入排序（直接插入排序和折半查找插入排序）

佚名 7年前 (2019-04-19) 随笔 1401人围观抢沙发百度已收录

#include <stdio.h>

// 直接插入排序
void insert_sort(int sz[], int len)
{
    for (int i = 2; i < len + 1; i++)
    {
        // 位置0作为哨兵
        sz[0] = sz[i];
        int j;
        // 寻找该插入的位置
        for (j = i - 1; sz[j] > sz[0]; j--)
        {
            sz[j + 1] = sz[j];
        }
        sz[j + 1] = sz[0];
    }
}
// 折半查找插入排序
void half_insert_sort(int sz[], int len)
{
    for (int i = 2; i < len + 1; i++)
    {
        // 位置0作为哨兵
        sz[0] = sz[i];
        // 折半查找该插入的位置
        int low = 1, high = i - 1;
        while (low <= high)
        {
            int mid = (low + high) >> 1;
            if (sz[0] < sz[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }
        for (int j = i - 1; j >= high + 1; j--)
            sz[j + 1] = sz[j];
        sz[high + 1] = sz[0];
    }
}

int main()
{
    // 0位置未用作为哨兵，待排序数组
    int a[] = {0, 5, 10, 8, 100, 50, -10, 60};
    insert_sort(a, 7); // 7为数组实际长度
    //half_insert_sort(a, 7); 
    // 输出排序结果
    for (int i = 1; i < 8; i++)
    {
        printf("%d%c", a[i], i == 7 ? '\n' : ' ');
    }
    return 0;
}