3回答

liuyubobobo

2021-01-25

已采纳

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

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

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

3 1 2

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

继续加油！：）

0

1

托尔的眼镜

非常感谢！

2021-01-25

共1条回复

托尔的眼镜

提问者

2021-01-25

好像可以啊，，我刚刚用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;
}

0

4

liuyubobobo

回复

托尔的眼镜

刚才我这里运行你的程序有问题，你的前面的写法确实是正确的；第二个是错误的。[1, 2, 3] 就能复现错误。会把本来有序的数组打乱，试试看？

2021-01-25

共4条回复

托尔的眼镜

提问者

2021-01-24

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及之前的数都小于等于选定的数，交换后不能，要再做一个判断

0

2

托尔的眼镜

回复

liuyubobobo

嗯呐好的~

2021-01-28

共2条回复