我有一个想法，通过递归地划分数组来实现快速排序，直到我得到数组的单元格树。然后我把排序后的数组组合成一个整体。有人能帮我找到一个错误，告诉我为什么程序不能正常工作吗?
#include <iostream>
#include <ctime>
using namespace std;
void random(int arr[], int N)
{
for(int i = 0; i < N; i++)
arr[i] = rand()%10;
}
void print(int arr[], int N)
{
for(int i = 0; i < N; i++)
cout << arr[i] << " ";
}
int quickSort(int arr[], int N)
{
int pivot = arr[0];
int i, j = 0, k = 0, arr1[N], arr2[N], N1, N2;
for(i = 1; i < N; i++)
{
if(arr[i] <= pivot)
{
arr1[j++] = arr[i];
N1 = j;
}
else
{
arr2[k++] = arr[i];
N2 = k;
}
}
arr1[N] = quickSort(arr1, N1), arr2[N] = quickSort(arr2, N2);
for(i = 0; i < N1; i++)
{
arr[i] = arr1[i];
}
arr[N1] = pivot;
for(i = N1 + 1; i < N; i++)
{
arr[i] = arr2[i];
}
}
int main()
{
srand(time(NULL));
int N;
cout << "How many elements should be in array?" << endl;
cin >> N;
int arr[N];
random(arr, N);
print(arr, N);
cout << endl;
quickSort(arr, N);
print(arr, N);
return 0;
}
0 1 5 2 9 6——快速排序——>0 1 2 5 6 9
这两个问题是:
<1:初始化/h3>int i, j = 0, k = 0, arr1[N], arr2[N], N1, N2;
^^^^^^^ Not initialized.
int i, j = 0, k = 0, arr1[N], arr2[N], N1, N2;
^^^^^^^ Not initialized.
展望它们是如何初始化的
if(arr[i] <= pivot)
{
arr1[j++] = arr[i];
N1 = j;
}
如果没有点小于或等于枢轴点，则N1将保持未初始化。您对
arr1[N] = quickSort(arr1, N1)
在这里，你传递了一个未初始化的值作为参数。这将导致Unspecified Behavior没有Undefined Behavior那么糟糕，但仍然不好。实际上，您传递的是一个随机数，它是该内存位置中的值。当您使用它作为零大小数组的大小时，任何大于0的值都将导致程序错误，任何大于N的值都将导致下一级的Undefined Behavior。
2:递归无出口
这是一个递归函数
目前没有退出条件，所以这将永远递归(或者直到您达到硬件限制并且操作系统杀死应用程序(它崩溃))。
在quickSort()的顶部，您应该添加一个退出测试。如果列表的长度为零，则不需要排序。如果长度是1，那么它已经排序了，所以不需要做额外的工作。
所以任何值N小于2的输入都退出。
int quickSort(int arr[], int N)
{
if (N < 2) {
return;
}
我的主要建议是这两个问题都被编译器发现了。
- 如果您正在使用
g++/clang，则提高-Wall -Wextra -Werror的警告级别 - 如果你正在使用dev studio
其他需要修复的问题。
从技术上讲，这是无效的c++
arr1[N]
std::vector，那么没关系。学习时请使用它们。但是一旦你了解了std::vector，你就更喜欢这个
函数quickSort()没有返回值。所以把它的返回类型改为void。然后更改递归调用，使其不将返回值赋给arr
void quickSort(int arr[], int N)
/// .....
quickSort(arr1, N1);
quickSort(arr2, N2);
其他需要注意的事项
OK。rand()对于肮脏的黑客来说很好。但是您应该开始使用适当的c++随机数生成器。让它成为你的习惯。
下面是一个例子。
停止使用
using namespace std;
关于它的一切:问题最好的答案(IMO)
请用大括号括住块语句(即使它们是一行)。这将为您节省一天的调试时间。
for(int i = 0; i < N; i++) { // Add this brace
arr[i] = rand()%10;
} // This brace
有一天，你将尝试做一些事情，在循环中添加另一行，并且不小心忘记在代码周围添加现在需要的大括号，这将无法工作，并且在你的代码中失明将无法发现它，直到你让实习生查看代码，他们将在30秒内发现它。
这种传递数组和长度的方式非常像C。
void print(int arr[], int N)
当然可以。但是它不符合大多数c++函数的风格(尤其是来自标准库的函数)。通常你传递一个begin和end指针(在c++中更常被称为迭代器)。
void print(int* begin, int* end) {
{
for(int* loop = begin; loop != end; ++loop) {
std::cout << *loop << " ";
}
}
现在你可以这样调用:
print(arr, arr + N);
这是懒惰的:
int i, j = 0, k = 0, arr1[N], arr2[N], N1, N2;
对于其他工程师来说也很难阅读。对你的工程师同事好一点，请每行一个声明。个人(但其他人有其他意见)停止使用i/j/k作为循环变量。这是Fortran遗留下来的。变量命名是一种技能，开发它。
提高你的c++技能的其他方法
获得一些代码审查。
有一个处理c++代码审查的堆栈交换站点，它将帮助您编写更好的符合习惯的c++代码。请注意他们只审查工作代码(这不是一个修复bug的网站)。
快速排序是一个常见的审查请求(特别是在c++中)。所以你可以看看别人做了什么，他们哪里出错了，以及更好的处理方法。
在CodeReview上搜索快速排序