首页 > 代码库 > 快速排序算法的修改，，

快速排序算法的修改，，

2024-07-27 11:38:10   215人阅读

参考了一下别人的程序，把bug的问题解决了，先把正确的代码贴上，让后分析一下之前的错误：

#include<iostream>using namespace std;void vector_initial(int *array,int n);void vector_print(int *array,int n);void fast_sort(int *array,int p,int r);int separate_2part(int *array,int p,int r);int main(){	int a[100];	int n;	cout<<"输入数的个数：";	cin>>n;	vector_initial(a,n);	fast_sort(a,0,n-1);	vector_print(a,n);	return 0;}void vector_initial(int *array,int n){	int i=0;	while(i<n)	{		cin>>array[i];		i++;	}}void vector_print(int *array,int n){	for(int i=0;i<n-1;i++)		cout<<array[i]<<" ";	cout<<array[n-1]<<endl;}void fast_sort(int *array,int p,int r){	int q;	if(p<r)	{		q=separate_2part(array,p,r);		fast_sort(array,p,q-1);		fast_sort(array,q+1,r);	}}int separate_2part(int *array,int p,int r){		int n1,n2,x;	n1=p;	n2=r;	x=array[p];	while(1)	{		while(array[++n1]<x);		while(array[n2]>x)			n2--;		if(n1>=n2) break;		swap(array[n1],array[n2]);			}	for(int i=p+1;i<=n2;i++)	{		array[i-1]=array[i];	}	array[n2]=x;	return n2;}

　　

我之前的错误，其实就一处：没有充分考虑清楚n1和n2的大小情况，错误得认为n1只能小于或等于n2,其实，n2-n1可能大于等于1，可能等于0，还可能等于-1，共三种情况。而，之前的代码，把n2-n1大于等于1和等于-1当成一种情况进行处理，即，进行两个数据的交换。在这种情况下，如果n2>n1是对的，如果n2<n1就错啦，排序就乱套了。
教训：算法要进行的操作和可能出现的情况，编程之前脑袋里一定要非常非常清晰才行。

快速排序算法的修改，，


联系
我们