我如何处理指向数组的空指针以进行排序算法？

Question

我正在尝试在C中创建一个通用的快速排序算法，该算法将空数组作为输入。我的问题是如何处理该数组的索引。下面是我目前对分区功能的尝试。我的代码可以编译，但是我知道它无法访问正确的指针，这会导致分段错误。

static int partition(void *array, int left, int right, size_t elem_sz,
                  int (*comp) (const void*, const void*)) {
    // TODO
    void** arr = array;
    void* p = *(arr + left);
    int s = left;
    for (size_t i = left+1; i<=right; i++) {
      if ( (*comp)(*(arr + i), p) < 0 ) {
        s++;
        swap(*(arr + s), *(arr + i), elem_sz);
      }
    }
    swap(*(arr + left), *(arr + s), elem_sz);   
    return s;
}

Answer 1

将数组指针从void *转换为void **没有意义，因为您（很可能）没有void *数组。

要执行正确的指针算术，您首先需要将指针转换为char *，因为您无法在void *上进行指针算术。然后，由于char的大小为1，因此需要将索引乘以元素大小才能获得正确的偏移量。]

static int lomuto(void *array, int left, int right, size_t elem_sz,
                  int (*comp) (const void*, const void*)) {
    char *arr = array;
    char *p = arr + left*elem_sz ;
    int s = left;
    for (size_t i = left+1; i<=right; i++) {
      if ( comp(arr + i*elem_sz, p) < 0 ) {
        s++;
        swap(arr + s*elem_sz, arr + i*elem_sz, elem_sz);
      }
    }
    swap(arr + left*elem_sz, arr + s*elem_sz, elem_sz);   
    return s;
}

Answer 2

将void指针转换为char指针，以便可以对其执行算术运算。使用char *是因为char是最小的类型，并且elem_sz是sizeof(char)的倍数。