c-这个函数我做错了什么，它没有结束

Question

这是我几个月前看到的一个函数，我试图复制它，但我认为我缺少了一些东西，因为程序并没有结束。

void quick_sort(int *array, int len) {
for (int i = 0; i < len - 1; i++) {
if (array[i] > array[i + 1]) {
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
quick_sort(array, len);
}

我在这里做错了什么？有人能帮忙吗？

Answer 1

首先，这个函数的名称不正确：这绝对不像快速排序。它看起来像一个气泡排序算法的内部循环，而致命的赠品是相邻元素的上升比较和潜在交换

也就是说，要使这个排序例程递归，只需将传统bubblesort的外循环推入递归激活堆栈即可。要理解这一点，请考虑一个基本的非交换检测优化气泡启动：

void bubblesort(int arr[], size_t len)
{
while (len-- > 0) // THIS LOOP
{
for (size_t i=0; i<len; ++i)
{
if (arr[i] > arr[i+1])
{
int tmp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = tmp;
}
}
}
}

你可以看到上面的外循环是我们想要存储在堆栈中的东西。那么我们该怎么做呢？首先，我们需要停止递归的条件，以及内部循环。然后，我们可以用比当前长度小一个元素的长度递归：

void bubblesort(int arr[], size_t len)
{
if (len-- < 2) // base case to exit on trivial sequence
return;
for (size_t i=0; i<len; ++i)
{
if (arr[i] > arr[i+1])
{
int tmp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = tmp;
}
}
// recurse with one fewer element.
bubblesort(arr, len);
}

就是这样。这也是尾部递归应用程序的一个教科书式例子，因此我们可以用迭代循环来实现它(很明显，这就是我们最初的做法(。

因此，总而言之，您错过了退出案例以及最终到达该退出案例的长度缩短。针对这两个问题，函数应该"工作"(术语使用松散，因为没有人会用这样的函数对非平凡的数据进行排序(。

Answer 2

您必须给出一个exit condition，否则它将永远运行
您的代码没有任何退出条件，因此它是无限运行的。
您一直在调用quick_sort(array, len);，但考虑一个场景，您需要停止调用quick_sort(array, len);，并为其设置条件(这将是您的退出条件(，这样您就可以停止无限循环运行它。