请写一个折半插入排序算法(最好用C语言写出来,只要求写一个函数)。

发布网友发布时间：2024-10-07 00:27

共1个回答

热心网友时间：2024-11-24 09:18

折半插入排序算法：

//创建链表
Status EnSqList(SqList *L,ElemType e,int n)
{
    if (L->length >= n)
        return ERROR;
    L->data[L->length + 1] = e;
    L->length++;
    return OK;
}

//折半插入排序算法
void BInsertSort(SqList *L)
{
    int i, j, mid, high, low;
    for (i = 2; i <= L->length; i++)
    {
        low = 1;
        high = i - 1;
        L->data[0] = L->data[i];
        while (low <= high)
        {
            mid = (low + high) / 2;
            if (L->data[0] < L->data[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }
        for (j = i - 1; j >= high + 1; j--)
            L->data[j + 1] = L->data[j];
        L->data[high + 1] = L->data[0];
    }
}

int main(void)
{
    SqList L;
    int n, i;
    ElemType e;
    L.length = 0;
    printf("输入元素个数：");
    scanf("%d", &n);
    L.data = (int *)malloc(sizeof(int)*n);
    printf("输入各个元素的值：");
    for (i = 0; i < n; i++)
    {
        scanf("%d", &e);
        EnSqList(&L, e, n);
    }
    BInsertSort(&L);
    for (i = 1; i <= n; i++)
        printf("%d ", L.data[i]);
    printf("\n");
    return 0;
}