10803：通用稳定排序

题目

使用函数指针比较元素，实现按字节操作对象表示的通用稳定插入排序。

解析

把数组首地址转换为 unsigned char * 后，第 i 个元素从 i * element_size 字节处开始。先检查这个乘积是否可能溢出，后续地址计算才有意义。

插入排序可以通过不断交换相邻逆序元素完成。只有比较结果大于 0 时才交换；比较结果为 0 时保留原次序，因此排序稳定。逐字节交换不依赖元素的具体类型，也不会违反对象表示的访问规则。

解析

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef int (*CompareFn)(const void *left, const void *right);

bool generic_stable_sort(
    void *base,
    size_t count,
    size_t element_size,
    CompareFn compare
) {
    if (element_size == 0 || compare == NULL) {
        return false;
    }
    if (count > 0 && base == NULL) {
        return false;
    }
    if (count > SIZE_MAX / element_size) {
        return false;
    }

    unsigned char *bytes = base;

    for (size_t i = 1; i < count; ++i) {
        size_t j = i;

        while (j > 0) {
            unsigned char *left =
                bytes + (j - 1) * element_size;
            unsigned char *right =
                bytes + j * element_size;

            if (compare(left, right) <= 0) {
                break;
            }

            for (size_t k = 0; k < element_size; ++k) {
                unsigned char temporary = left[k];
                left[k] = right[k];
                right[k] = temporary;
            }
            --j;
        }
    }

    return true;
}

来源与改编

题型借鉴 MIT 6.087 Practical Programming in C 的 Assignment 4，采用 CC BY-NC-SA 4.0；本题改写为带失败契约的稳定通用排序接口。