【咨询】实现一个 qsort 函数？

Programming
1 
/*
  Swap
    Swap the data of two element
  Argument
    element_first
      The first element
    element_second
      The second element
    size_of_element
      The size of each element
  Return Value
    No value will return
 */
void Swap(void *element_first, void *element_second, int size_of_element)
{
    void *temp_buffer = NULL;
    temp_buffer = malloc(size_of_element);
    if (NULL == temp_buffer)
        return ;
    memmove(temp_buffer, element_second, size_of_element);
    memmove(element_second, element_first, size_of_element);
    memmove(element_first, temp_buffer, size_of_element);
    free(temp_buffer);
}
/*
  Compare
    Compare two character
  Argument
    Fisrt
      The first character
    Second
      The second character
  Return Value
    The difference value
 */
int Compare(const void *element_1, const void *element_2)
{
    return *(char*)element_1 - *(char*)element_2;
}
/*
  QuickSort
    Use the quick sort algorithm to sort the array
  Argument
    array
      The pointer to store the data
    number_of_elements
      The number of elements
    size_of_element
      Each element's size
    ElementCompare
      The user defined function to compare each element
  Return Value
    No value will return
 */
void QuickSort(void *array, unsigned number_of_elements, unsigned size_of_element, int (*ElementCompare)(const void *element_1, const void *element_2))
{
    unsigned left = 0;
    unsigned right = number_of_elements;
    int i = left;
    int j = right;
    if (left > right)
    {
        return ;
    }
    while (i != j)
    {
        if (j > i)
        {
            Swap(array + i * size_of_element, array + size_of_element * j, size_of_element);
        }
        else
        {
            while (ElementCompare(array + j * size_of_element, array + left * size_of_element) >= 0)
            {
                j--;
            }
            while (ElementCompare(array + i * size_of_element, array + left * size_of_element) < 0)
            {
                i++;
            }
        }
    }
    Swap(array + i * size_of_element, array + size_of_element * left, size_of_element);
    QuickSort(array + left * size_of_element, i - 1 - left, size_of_element, ElementCompare);
    QuickSort(array + (i + 1) * size_of_element, right - (i + 1), size_of_element, ElementCompare);
}

这是我尝试实现的一个 qsort 函数，可是我并不知道它的问题在哪里。

可以帮忙看一下吗？（百思不得其解）

我去看了《C程序设计语言》上面的两种实现方案

第一种就是专注于 int 类型的数组

第二种尽管是 void* 通用类型，但是它使用了 二维指针数组

我希望的是复现 qsort 函数，但是现在也没想出来应该怎么解决 left 和 right 参数传递的问题。

Thanks in advance!

2

这个帖子不是应该放到闲聊灌水区嘛～

3

这不是灌水，我是真的想不出来了（哭）

4

非 Emacs Elisp 直接相关的都应该放在闲聊区。

1 个赞
5
6

非 Emacs 相关但是编程相关的可以放 Programming 区

7

学习了 :grimacing: :grimacing: :grimacing:

8

楼主还是要多动脑筋多练习哈， 论坛有网友投诉楼主经常发这种帖子， 我已经忽略没有处理。

1 个赞
9

建议楼主先从简单的开始实现，逐步理解，也不容易泄气。就是你说的第一种方式先搞定。

然后再来看如何通用化，可以应用于更多的场景。

实在不行就去看下别人怎么实现的，与自己有哪些差别，为什么自己没想到。

1 个赞
10

前面的那种方案我已经实现出来了，我就是再复现 qsort 的时候出现了问题。

11

chatgpt回复说：

您的 qsort 函数看起来基本正确，但我发现几个问题。首先，在 while 循环内，您没有判断 i 和 j 是否已经遍历完整个数组，所以当 i 和 j 的值相同时，循环会无限进行下去。

其次，在调用 QuickSort 函数的递归调用时，您没有正确地计算 left 和 right 参数的值。例如，在调用 QuickSort(array + left * size_of_element, i - 1 - left, size_of_element, ElementCompare) 时，您应该使用 i - left 而不是 i - 1 - left。

最后，在调用 malloc 函数时，您没有检查它是否返回 NULL，所以如果分配内存失败，函数会继续执行，可能会导致程序崩溃。

3 个赞