C 中 64 位整数数组的快速排序函数问题

Question

我目前正在使用 C 语言处理大型 64 位整数集，我自然需要一个快速排序算法来简化这些集合上的任何传入函数。我尝试了在该网站上的几个地方（例如here）中已经找到的经典实现，并最终得到以下代码：

#include <stdio.h>
#include <stdlib.h>         
#include <time.h>
#include <stdint.h>
static void swap_int(uint64_t *a, uint64_t *b)
{
    uint64_t tmp = *a;
    *a  = *b;
    *b = tmp;
}
uint64_t QuickSortPartition(uint64_t *array, uint64_t begin, uint64_t end){

    uint64_t i=begin, j;

    for (j = begin; j <= end; j++)
    {
        if (array[j] < array[end])
            swap_int(array+j, array + i++);
    }
    swap_int(array+i, array+end);

    return i;
}
void QuickSortFunction(uint64_t *array, uint64_t begin, uint64_t end){
    if (begin < end) {
        uint64_t pivot = QuickSortPartition(array, begin, end);
        QuickSortFunction(array, begin, pivot - 1);
        QuickSortFunction(array, pivot + 1, end);
    }
}

据我测试，它对于小型设备来说效果非常好。然后，我继续使用以下函数伪随机生成 64 位整数，并测试快速排序：

uint64_t rnd64(uint64_t n)
{
    const uint64_t z = 0x9FB21C651E98DF25;

    n ^= ((n << 49) | (n >> 15)) ^ ((n << 24) | (n >> 40));
    n *= z;
    n ^= n >> 35;
    n *= z;
    n ^= n >> 28;

    return n;
}


int main(int argc, char const *argv[]){
    int n=64;
    uint64_t Size = strtoull(argv[1], NULL, 10);

    uint64_t* S=malloc(Size*sizeof(uint64_t));

    uint64_t state = 1;
    for (uint64_t i=0;i<Size;i++)
    {
        const uint64_t n = rnd64(state++);
        S[i] = n;
    }


    QuickSortFunction(S, 0, Size-1);


    printf("Sorted S:\n");
    Display_set(S,Size,n);

}

其中 Size 是作为 argv 参数任意输入的。此外，Display_set 是一个标准函数，以二进制形式按顺序打印 S 的每个元素。 这对于尺寸来说非常合适 <= 11, but once Size = 11, this produces a segmentation fault. What am I doing wrong here?

我尝试实现其他标准快速排序方法，例如第一个或最后一个位置的枢轴，但无济于事。由于这个函数应该（除非我在这里也错了）适用于 int 类型，我猜测转换到 uint64_t 会导致错误。

Answer 1

你不必重新发明轮子；查看 C 库函数qsort。它允许您指定元素的大小，您可以将其设置为

sizeof(your integer type)

。 如果快速排序不是您想要的算法，它的姊妹函数归并排序和堆排序可能更有用。

比较函数——最后一个参数——可以简单地实现为

int compare(const void *a, const void *b) {
    return *(const int_type *)a - *(const int_type *)b;
}

该函数随后被调用为

qsort(array, size, sizeof(*array), compare);
// the last argument is a function; don't call it!

Answer 2

潜在的溢出

数字的类型是

uint64_t

--> 好。

数组大小和索引应该是

size_t

。如果

rnd64()

生成的返回值大于

SIZE_MAX/sizoef(uint64_t)

，那么

Size*sizeof(uint64_t)

就会溢出，就会出现问题。

限制数组。