c - 这个快速排序有什么问题吗？

Question

已关闭。此问题不符合 Stack Overflow guidelines 。目前不接受答案。

---

这个问题似乎与 help center 中定义的范围内的编程无关。 .

已关闭 9 年前。

Improve this question

快速排序。代码是用纯 C 语言编写的。这个算法实现有什么问题吗？

void quick_sort(void *base, size_t num, size_t size, int (*comp)(const void*, const void*)) {
    unsigned int i = 0, j = num-1;
    int rpos = rand() % num;
    do {
        while(comp((char*)base + size*i, (char*)base + rpos*size) < 0) i++;
        while(comp((char*)base + size*j, (char*)base + rpos*size) > 0) j--;
        if (i <= j) swap((char*)base + size*i++, (char*)base + size*j--, size);
    } while (i <= j);
    if (i < num) quick_sort((char*)base, j, size, comp);
    if (j > 0) quick_sort((char*)base + size*i, num - i, size, comp);
}

陷入无限递归。

Answer 1

应该有 if(i<=j) swap 和 do 。 。 。 while(i<=j) 不仅仅是 (i < j )。并且交换后还需要增加 i 并减少 j。

有http://www.algolist.net/Algorithms/Sorting/Quicksort有示例代码非常容易理解:)