关于自己实现的双路快速排序partition出现问题

Question

请教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);
}

Answer 1

liuyubobobo 2021-11-19 04:59:41

我没有完整调试你的代码，只是简单测试加大概看了一遍，我来指出我调试问题的方向是怎样的，供你参考。

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 是否有问题。）

继续加油！：）

• 提问者 Wonwayshon #1

  非常感谢，受益匪浅!

• 提问者 Wonwayshon #2

  时隔一段时间再次回复，写细致的注释真的是分析的好习惯；
  
  在学习算法时出问题往往不知道从何下手来查找问题，IDE有调试功能却也不知道该在哪里下断电注意什么的变化，一个函数都是逻辑又不方便边写边增量测试；这个时候如果从头开始写非常细致的注释再一点点看注释后面的一小段代码是否符合想法和逻辑就很有调理，也容易注意到错误或者确定该调试的位置，最坏情况即使错误没有解决，对于求助来说也很有帮助；
  
  写细致注释梳理的做法在这段时间帮助我自己发现解决了很多算法学习中遇到的问题，相当值得推荐的好方法!