1

我删除了代码，因为它是家庭作业。如果您确实需要帮助，您可以查看我与 George B 的讨论（如下），或 PM 我。

嗨，大家好。这是一个家庭作业。我已经针对其他排序算法对其进行了测试，QS 是唯一在某些随机输入上崩溃的算法。

该程序退出时间很长（与其他东西一起），但输入是随机生成的......

我花了几个小时跟踪代码，仍然无法找出任何错误.... QS 对于专业人士来说可能很容易，所以我希望收到有关此实施的建议....

任何输入表示赞赏！

问：什么是“随机”？

A：包含了一部分生成。

void randomArray(unsigned long*& A, unsigned long size)
{
 //Note that RAND_MAX is a little small for some compilers (2^16-1).
 //In order to test our algorithms on large arrays without huge
 //numbers of duplicates, we'll set the high-order and low-order
 //parts of the return value with two random values.
 A = new unsigned long[size];
 for(unsigned long i=0; i<size; i++)
  A[i] = (rand()<<16) | (rand());

 //Another note:  initially, if you want to test your program out with smaller
 //arrays and small numbers, just reduce A[i] mod k for some small value k as in the following:
 //A[i] = rand() % 16;
 //this may help you debug at first.
}

问：什么样的错误？

好吧，我没有收到编译错误。没有QS，我可以毫无问题地运行其他四种排序算法（我可以连续运行排序）。QS启动后，程序运行一两三遍，甚至第一次运行，程序就结束了（我用的是Eclipse，所以控制台就结束了）。

输入元素的数量，或者一个负数退出：5 {一些数组}

选择排序耗时 0 秒。合并排序耗时 0 秒。快速排序耗时 0 秒。堆排序耗时 0 秒。桶排序耗时 0 秒。{5 个排序数组的输出}

输入元素的数量，或负数退出：6 {一些数组}

选择排序耗时 0 秒。合并排序耗时 0 秒。快速排序耗时 0 秒。堆排序耗时 0 秒。桶排序耗时 0 秒。

{5 个排序数组的输出}

输入元素的数量，或者一个负数退出：8 {arrays} --- 控制台结束---

同样，问题是它经常崩溃，所以这表明访问冲突的可能性很高，但是进行 10 多次跟踪我没有看到问题......（也许我的大脑堆栈超载 - _ - )

谢谢。

4

2 回答 2

1

暗示：

q is unsigned (the result of the partition function)
so, q-1 is also unsigned
what if q is zero?

（这是家庭作业，所以我猜你必须弄清楚:)）

于 2010-12-12T23:47:59.777 回答
0

使用数组跟踪您的算法{2,5,2}。显然，只要您的列表中有重复的数字，您的程序就会崩溃。Partition 的第一次调用将2作为 的索引返回r。因此，第二次调用quickSort(A,3,2)将访问不在数组边界内的内存位置。手动对数组进行边界检查并生成可理解的输出以更轻松地跟踪和调试程序总是一个好主意。

于 2010-12-12T23:52:47.180 回答