关于自己实现的双路快速排序partition出现问题
来源:3-7 双路快速排序法
Wonwayshon
2021-11-18
请教bobo老师,我在复习课程时按照双路快速排序的思想写出了如下的partition部分代码,出现了栈溢出,应该是递归逻辑出现了错误,对partition代码部分添加了注释,麻烦bobo老师看看
//对数组[l,r)部分进行partition
void partitionTwoWays(pTable& t, int l, int r) {
//将i设置第二个元素开始向后扫描,j设置为最后一个元素索引向左扫描
int i = l + 1, j = r - 1;
//暂时没有添加随机化,将区间第一个元素取为标定点
int v = t->data[l];
//数组的[l+1,i)部分<v
while (i <= j) {
//i扫描到>=v的元素停住开始用j从后往前扫描
if (t->data[i] >= v) {
//数组的(j,r-1]部分<v
while (i <= j) {
//j扫描到<=v的元素停住并交换i,j索引对应元素
if (t->data[j] <= v) {
swap(t->data[i], t->data[j]);
i++;
j--;
//交换完成后退出循环继续用i从左往右扫描
break;
}
else {
j--;
}
}
}
else {
i++;
}
}
//i和j相遇,将j与标定点l索引元素对调,把标定点放在该在的位置
swap(t->data[l], t->data[j]);
//递归分别对左右两个区间进行partition
partitionTwoWays(t, l, i);
partitionTwoWays(t, i + 1, r);
}
完整包含测试的代码:
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
typedef int ElemType;
typedef struct table {
ElemType* data;
int length;
}table, * pTable;
void initTable(pTable& t, int length) {
t = (pTable)malloc(sizeof(table));
t->data = (ElemType*)malloc(sizeof(ElemType) * length);
t->length = length;
srand((unsigned int)time(NULL));
for (int i = 0; i < length; i++) {
t->data[i] = rand() % 100; //填充0~99的随机数
}
}
void printTable(pTable t) {
for (int i = 0; i < t->length; i++) {
printf("%3d", t->data[i]);
}
printf("\n");
}
void swap(ElemType& a, ElemType& b) {
ElemType temp;
temp = a;
a = b;
b = temp;
}
//双路快排
void partitionTwoWays(pTable& t, int l, int r);
void sortTwoWays(pTable& t) {
partitionTwoWays(t, 0, t->length);
}
//对数组[l,r)进行partition
void partitionTwoWays(pTable& t, int l, int r) {
int i = l + 1, j = r - 1;
int v = t->data[l];
while (i <= j) {
if (t->data[i] >= v) {
while (i <= j) {
if (t->data[j] <= v) {
swap(t->data[i], t->data[j]);
i++;
j--;
break;
}
else {
j--;
}
}
}
else {
i++;
}
}
swap(t->data[l], t->data[j]);
partitionTwoWays(t, l, i);
partitionTwoWays(t, i + 1, r);
}
//测试
int main() {
pTable t;
initTable(t, 10);
printTable(t);
sortTwoWays(t);
printTable(t);
}
1回答
-
我没有完整调试你的代码,只是简单测试加大概看了一遍,我来指出我调试问题的方向是怎样的,供你参考。
1,
首先,我尝试运行你的代码。复现问题。你的程序直接执行,显然排序结果是错误的。
下面我做什么?下面我做的事情是:
1)尝试固定一个测试用例,复现问题(而不是随机化的测试用例);
2)尝试缩小测试用例,看在更小的测试用例,是不是能复现错误。
于是,我使用 [1, 0] 测试,你的程序也是错误的。
这个测试用例已经足够小了(对于排序来说,近乎是最小的测试用例),请你参考这个测试用例,在你的程序下做调试,你脑子里的逻辑,在这个测试用例下,应该是怎样的?实际上每一步的执行结果是怎样的?在哪里出了问题?为什么会出问题?哪里错了?是你头脑中的逻辑错了?还是实现有问题?
如果这个测试用例调过了,可以近一步去测试诸如 [2, 1, 0],[3, 2, 1, 0] 这样的测试用例。而不是一上来就用一个随机的,包含有 10 个元素的测试用例测试。
在一个随机的测试用例下,你无法用纸笔模拟你的程序。纸笔模拟程序,首先需要一个固定的,足够小的测用例。
2.
下面,我简单看了一下你的逻辑。我是怎么看的?
我直接跳过了你的程序中最复杂的 while 部分,我先假设它做了他应该做的事情,然后直接看整个递归主体,在这里就有问题。
问题1)
为什么没有递归终止条件?请再回顾一下我的体系课程中介绍的,到底如何写一个递归程序。这一点非常重要。
问题2)
你的这一句话:
//i和j相遇,将j与标定点l索引元素对调,把标定点放在该在的位置 swap(t->data[l], t->data[j]);
把标定点放在应该的位置,应该的位置到底是哪里???如果我没有理解错,应该是 j(因为你将 j 和 l 对调了。)
那下面的递归过程,为什么没有 j 的参与?而是基于 i 去递归?
请仔细体会我的课程参考代码 47-54 行:https://git.imooc.com/class-105/Play-Algorithms-and-Data-Structures/src/master/12-More-about-QuickSort/03-QuickSort-2-Ways/src/QuickSort.java
这是整个双路快排程序的“逻辑框架”,你上面的两个问题,都在这短短 4 行里体现出来了。
请再仔细体会一下,我们写程序,不是一下子就陷入具体的逻辑中,而是自顶向下的,逐步实现出来的。正是因为有这样的实现过程,我们在调试的时候也能够一步一步看到问题可能在哪里。
(如果上面的递归框架问题解决了,你的程序还有可能有问题,那在进一步去看你的 while 部分是否有问题,也就是 partition 是否有问题。)
继续加油!:)
122021-12-10
相似问题
回答 1
回答 2