EXP1.1.c

#include <assert.h> // assert
#include <math.h>   // pow
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h> // malloc, free
#include <string.h> // memcpy

static void PaiXuInternal(int array[], const int from, const int to)
{
    const int length = to - from;
    if (from >= to)
        assert(false);
    else if (length == 1)
        return;

    const int step = (int)pow(length, 0.5); // 每个子问题的长度为根号n
    int from2 = from;                       // 子问题开头
    int to2 = from + step;                  // 子问题结尾
    while (to2 < to)
    {
        PaiXuInternal(array, from2, to2);
        from2 = to2; // 下一个子问题
        to2 += step;
    }
    PaiXuInternal(array, from2, to); // 最后一个子问题长度可能不足根号n

    int *newArray = malloc((length) * sizeof(int));
    int *p = newArray;
    // char flags[length];
    bool *flags = calloc(length, sizeof(bool)); // 标识是否已经取出

    while (p < newArray + length) // 合并
    {
        int mini = -1; // 最小项的下标

        from2 = from;
        to2 = from + step;
        while (to2 < to)
        {
            for (int i = from2; i < to2; i++)                                       // 遍历子问题
                if (flags[i - from] == 0 && (mini == -1 || array[i] < array[mini])) // 未被取出时，最小项不存在或小于最小项
                    mini = i;
            from2 = to2;
            to2 += step;
        }
        for (int i = from2; i < to; i++)
            if (flags[i - from] == 0 && (mini == -1 || array[i] < array[mini]))
                mini = i;

        flags[mini - from] = 1; // 注意偏移
        *p++ = array[mini];
    }

    memcpy(array + from, newArray, length * sizeof(int)); // 注意偏移
    free(newArray);
    free(flags);
}

void PaiXu(int length, int array[length])
{
    return PaiXuInternal(array, 0, length);
}

static int arr[] = {85, 75, 75, 59, 7, 30, 36, 16, 27, 80, 53, 78, 69, 85, 75};
int main(void)
{
    int length = sizeof(arr) / sizeof(*arr);

    for (int i = 0; i < length; i++)
        printf("%d ", arr[i]);
    putchar('\n');

    PaiXu(length, arr);
    for (int i = 0; i < length; i++)
        printf("%d ", arr[i]);
    putchar('\n');

    return 0;
}

void PaiXu(int length, int array[length])
{
    return PaiXuInternal(array, 0, length);
}

static int arr[] = {85, 75, 75, 59, 7, 30, 36, 16, 27, 80, 53, 78, 69, 85, 75};
int main(void)
{
    int length = sizeof(arr) / sizeof(*arr);

    for (int i = 0; i < length; i++)
        printf("%2d ", arr[i]);
    putchar('\n');

    PaiXu(length, arr);
    for (int i = 0; i < length; i++)
        printf("%2d ", arr[i]);
    putchar('\n');

    return 0;
}