快速排序的划分

Question

老师好，我按照双指针的方法自己实现了一下划分，但是有个问题，标记处这两个语句交换一下位置，交换前是有序正确的，交换后就是错的，我不知道为啥...

int _partition(int A[],int left,int right){
	int temp = rand() % (right - left + 1) + left;
	
	swap(A[left],A[temp]);
	
	temp = left;
	
	while(left < right){
	        //***这是交换前，是正确的
		while(left < right && A[right] > A[temp]) right--;
		while(left < right && A[left] <= A[temp]) left++;
		//***这是交换后，是错误的
		while(left < right && A[left] <= A[temp]) left++;
		while(left < right && A[right] > A[temp]) right--;
		
		swap(A[left],A[right]); 
	}
	
	swap(A[temp],A[left]);
	
	return left;
}

Answer 1

liuyubobobo 2021-01-25 01:51:10

你的这两种写法都是错误的。

为了测试方便，你可以把随机化去掉。int temp = left。

在这个只包含三个元素的测试用例下，这两个写法都不能成功完成排序：

3 1 2

你可以使用这个测试用例跟踪一下你的这个逻辑，看最终返回的索引是什么，A 被整理成了什么样子，返回的索引是否将将整个数组按照快速排序的要求，进行了切分，

继续加油！：）

• 提问者 托尔的眼镜 #1

  非常感谢！

Answer 2

提问者 托尔的眼镜 2021-01-25 02:21:51

好像可以啊，，我刚刚用3 1 2试了，一般的案例也试了，能正确排序，但是相对慢一点。。

刚才没打掉，打掉了也正常的

这个是随机生成的测试。。

int _partition4(int A[],int left,int right){
	//int temp = rand() % (right - left + 1) + left;
	
	//swap(A[left],A[temp]);
	
	int temp = left;
	
	while(left < right){
		
		while(left < right && A[left] <= A[temp]) left++;
		while(left < right && A[right] >= A[temp]) right--;
		
		swap(A[left],A[right]); 
	}
	
	if(A[left] <= A[temp]){
		swap(A[temp],A[left]);
		return left;
	}else{
		swap(A[temp],A[left-1]);
		return left-1;
	} 
}

void _quickSort(int A[],int left,int right){
	if(left >= right) return;
	
	int p = _partition4(A,left,right);
	
	_quickSort(A,left,p-1);
	_quickSort(A,p+1,right);
}

void quickSort(int A[],int n){
	srand((unsigned)time(NULL));
	_quickSort(A,0,n-1);
}

int main(){
	
	int A[3] = {3,1,2};
	
	quickSort(A,3);
	
	for(int i = 0;i<3;i++){
		printf("%d ",A[i]); 
	}
	int *arr = generateRandomArray(1000000,0,1000000);
	
	testSort("quickSort",quickSort,arr,1000000);
	
	return 0;
}

• liuyubobobo #1

  我建议你随机生成数据，或者生成 n 个数字的全排列多测试一下，这个逻辑目测有问题的。最典型的是，标定点放在了最左边，但是下面的比较，标定点 left 参与了进去。不是从 left + 1 开始的。

• liuyubobobo #2

  你这个截图我看不见partition，随机有没有打掉？我这里测试有问题的。

• 提问者 托尔的眼镜 回复 liuyubobobo #3

  老师这个我考虑了，因为left这个标定点按照我的逻辑就是在左边的，所以排除不排除都行

点开查看后面1条评论

Answer 3

提问者 托尔的眼镜 2021-01-24 23:54:52

int _partition1(int A[],int left,int right){
	int temp = rand() % (right - left + 1) + left;
	 
	swap(A[left],A[temp]);
	
	temp = left;
	
	while(left < right){
		
		while(left < right && A[left] <= A[temp]) left++;
		while(left < right && A[right] >= A[temp]) right--;
		
		swap(A[left],A[right]); 
	}
	
	if(A[left] <= A[temp]){
		swap(A[temp],A[left]);
		return left;
	}else{
		swap(A[temp],A[left-1]);
		return left-1;
	}
	
}

一点点试出来了(＠_＠;)，交换前能保证left及之前的数都小于等于选定的数，交换后不能，要再做一个判断

• liuyubobobo #1

  大赞！不过你这样写，其实没有解决我们引入双路快拍的核心原因：面对大量重复元素，这样写还是退化成 n^2 的算法了。可以使用课程中的方式做一下性能测试试试看？继续加油！：）

• 提问者 托尔的眼镜 回复 liuyubobobo #2

  嗯呐好的~