快排

C++语言 码拜 6年前 (2015-05-11) 570次浏览 0个评论

这个代码为什么结果一直不对,会出来0
[code=c#include<iostream>
#include<stdlib.h>
#include<time.h>
using namespace std;

void Swap(int &a, int &b)//交换两个数的函数
{
a+=b;
b=a-b;
a-=b;
}

int* New_Partition(int *A, int p, int r)  //新的分区函数    
{      
    int *index=(int *)malloc(sizeof(int)*2);
srand((unsigned)time(NULL));
int k=rand()%(r-p+1)+p;//随机化快排
Swap(A[k],A[r]);
int i=p-1;
for(int j=p;j<r;j++) //把比主元小的元素都排到前面
{
if (A[j]<A[r])
{
++i;
Swap(A[i],A[j]);
}
}
index[0]=i+1;//记录相等元素开始的下标
for(int l=i+1;l<r;l++)//再把和主元相等的元素排到中间
{
if (A[l]==A[r])
{
++i;
Swap(A[l],A[i]);
}
}
index[1]=i+1;//记录相等元素结束的下标
Swap(A[i+1],A[r]);
return index;

     
void QuickSort(int  *A, int p, int r)      
{  
    
    if(p < r)      
    {      
        int *new_index= New_Partition(A, p, r); 
        QuickSort(A, p, new_index[0]-1); 
        QuickSort(A, new_index[1]+1, r);
    }      

int main()
{
int A[12]={13,19,9,5,12,8,7,4,11,2,6,21};
for(int m=0;m<=11;m++)
cout<<A[m]<<” “;
cout<<endl;
QuickSort(A,0,11);
for(int n=0;n<=11;n++)
cout<<A[n]<<” “;
cout<<endl;
return 0;
}  ][/code]

给个我之前写的快速排序代码,楼主参考下:

是用类模板写的,只要实现了比较运算的类型都支持

//快速排序(递归版)
template<class T> class Quick : public Sort<T>
{
    private:
		void QSort(T* a,int left,int right);//划分函数
	public:
		Quick(T* arr,int len,bool sequen = true) : Sort<T>(arr,len,sequen){}
		virtual void sort(){if(len > 1) QSort(arr,0,len-1);}
};

//快速排序(非递归版)
template<class T> class Quick2 : public Sort<T>
{
	private:
		int* stack; //创建一个栈的指针
		int Partition(T* a,int left,int right);//划分函数
	public:
		Quick2(T* arr,int len,bool sequen = true) : Sort<T>(arr,len,sequen){stack = NULL;}
		virtual ~Quick2(){delete[] stack;}
		virtual void Release(){delete[] stack; stack = NULL;}
		virtual void sort();
};

//快速排序(递归版)-------------------------------------------------------------------------------
template<class T>
void Quick<T>::QSort(T* a,int left,int right)
{
	T tmp = a[left];
	int p = left;
	int i = left,j = right;
	while(i<=j)
	{
		if(sequen) //升序
		{
			while(a[j]>=tmp && j>=p)
				j--;
			if(j>=p)
			{
				a[p] = a[j]; //比划分元小的交换到左边
				p = j;
			}
			while(a[i]<=tmp && i<=p)
				i++;
			if(i<=p)
			{
				a[p] = a[i]; //比划分元大的交换到右边
				p = i;
			}
		}
		else //降序
		{
			while(a[j]<=tmp && j>=p)
				j--;
			if(j>=p)
			{
				a[p] = a[j]; //比划分元大的交换到左边
				p = j;
			}
			while(a[i]>=tmp && i<=p)
				i++;
			if(i<=p)
			{
				a[p] = a[i]; //比划分元小的交换到右边
				p = i;
			}
		}
	}//end while(i<j)
	a[p] = tmp;
	if(p-left>1)
		QSort(a,left,p-1);
    if(right-p>1)
		QSort(a,p+1,right);
}

//快速排序(非递归版)-----------------------------------------------------------------------------
template<class T>
int Quick2<T>::Partition(T* a,int left,int right)
{
	T pivot = a[right];
	while(left<right)
	{
		if(sequen) //升序
		{
			while(a[left]<pivot && left<right)
				left++;
			if(left<right)
				a[right--] = a[left];
			while(a[right]>pivot && left<right)
				right--;
			if(left<right)
				a[left++] = a[right];
		}
		else //降序
		{
			while(a[left]>pivot && left<right)
				left++;
			if(left<right)
				a[right--] = a[left];
			while(a[right]<pivot && left<right)
				right--;
			if(left<right)
				a[left++] = a[right];
		}
	}
	a[left] = pivot;
	return left;
}

template<class T>
void Quick2<T>::sort()
{
	if(len <= 1)
		return;
	int left = 0;
	int right = len - 1;
	stack = new int[right-left+2]; //会浪费大量存储空间
	int top = 0;
	int mid;
	stack[top++] = left;
	stack[top++] = right;
	while(top>0)
	{
		right = stack[--top];
		left = stack[--top];
		if(left<right)
		{
			mid = Partition(arr,left,right);
			if(mid-left > right-mid)
			{
				stack[top++] = left;
				stack[top++] = mid-1;
				if (right > mid)
				{
					stack[top++] = mid + 1;
					stack[top++] = right;
				}
			}
			else
			{
				stack[top++] = mid + 1;
				stack[top++] = right;
				if(mid > left)
				{
					stack[top++] = left;
					stack[top++] = mid - 1;
				}
			}
		}
	}
	delete[] stack;
	stack = NULL;
}

参考代码段
https://github.com/707wk/Senior-middle-school/blob/master/Filling%20in%20the%20gaps.c
引用
引用 1 楼 paschen 的回复:

给个我之前写的快速排序代码,楼主参考下:

是用类模板写的,只要实现了比较运算的类型都支持

//快速排序(递归版)
template<class T> class Quick : public Sort<T>
{
    private:
		void QSort(T* a,int left,int right);//划分函数
	public:
		Quick(T* arr,int len,bool sequen = true) : Sort<T>(arr,len,sequen){}
		virtual void sort(){if(len > 1) QSort(arr,0,len-1);}
};

//快速排序(非递归版)
template<class T> class Quick2 : public Sort<T>
{
	private:
		int* stack; //创建一个栈的指针
		int Partition(T* a,int left,int right);//划分函数
	public:
		Quick2(T* arr,int len,bool sequen = true) : Sort<T>(arr,len,sequen){stack = NULL;}
		virtual ~Quick2(){delete[] stack;}
		virtual void Release(){delete[] stack; stack = NULL;}
		virtual void sort();
};

//快速排序(递归版)-------------------------------------------------------------------------------
template<class T>
void Quick<T>::QSort(T* a,int left,int right)
{
	T tmp = a[left];
	int p = left;
	int i = left,j = right;
	while(i<=j)
	{
		if(sequen) //升序
		{
			while(a[j]>=tmp && j>=p)
				j--;
			if(j>=p)
			{
				a[p] = a[j]; //比划分元小的交换到左边
				p = j;
			}
			while(a[i]<=tmp && i<=p)
				i++;
			if(i<=p)
			{
				a[p] = a[i]; //比划分元大的交换到右边
				p = i;
			}
		}
		else //降序
		{
			while(a[j]<=tmp && j>=p)
				j--;
			if(j>=p)
			{
				a[p] = a[j]; //比划分元大的交换到左边
				p = j;
			}
			while(a[i]>=tmp && i<=p)
				i++;
			if(i<=p)
			{
				a[p] = a[i]; //比划分元小的交换到右边
				p = i;
			}
		}
	}//end while(i<j)
	a[p] = tmp;
	if(p-left>1)
		QSort(a,left,p-1);
    if(right-p>1)
		QSort(a,p+1,right);
}

//快速排序(非递归版)-----------------------------------------------------------------------------
template<class T>
int Quick2<T>::Partition(T* a,int left,int right)
{
	T pivot = a[right];
	while(left<right)
	{
		if(sequen) //升序
		{
			while(a[left]<pivot && left<right)
				left++;
			if(left<right)
				a[right--] = a[left];
			while(a[right]>pivot && left<right)
				right--;
			if(left<right)
				a[left++] = a[right];
		}
		else //降序
		{
			while(a[left]>pivot && left<right)
				left++;
			if(left<right)
				a[right--] = a[left];
			while(a[right]<pivot && left<right)
				right--;
			if(left<right)
				a[left++] = a[right];
		}
	}
	a[left] = pivot;
	return left;
}

template<class T>
void Quick2<T>::sort()
{
	if(len <= 1)
		return;
	int left = 0;
	int right = len - 1;
	stack = new int[right-left+2]; //会浪费大量存储空间
	int top = 0;
	int mid;
	stack[top++] = left;
	stack[top++] = right;
	while(top>0)
	{
		right = stack[--top];
		left = stack[--top];
		if(left<right)
		{
			mid = Partition(arr,left,right);
			if(mid-left > right-mid)
			{
				stack[top++] = left;
				stack[top++] = mid-1;
				if (right > mid)
				{
					stack[top++] = mid + 1;
					stack[top++] = right;
				}
			}
			else
			{
				stack[top++] = mid + 1;
				stack[top++] = right;
				if(mid > left)
				{
					stack[top++] = left;
					stack[top++] = mid - 1;
				}
			}
		}
	}
	delete[] stack;
	stack = NULL;
}

你的程序确实挺好的,但是在一个序列中有很多元素相同的时候性能就不好, 我想做的是改进快排,把一个序列分成三个区域,中间的区域是和主元相同的元素,但是写出来运行结果很奇怪

Swap函数错了。不要这么高大上,就用最简单最入门的交换即可。
或者这样改一下
void Swap(int &a, int &b)//交换两个数的函数
{
if (a != b) // 加上这一行
{
a+=b;
b=a-b;
a-=b;
}
}

当调用Swap(a[i], a[j])的时候,如果i刚好等于j,那Swap进来的两个引用实际上是同一个地址,a+=b的时候实际上是把a和b一起改了,
20分
还有两个小问题:
srand在main里面调用一次即可,不要多次调用。
只有malloc没有free,虽然在这个小程序里面不会造成内存泄漏,但是这个习惯不太好
引用 6 楼 brookmill 的回复:

还有两个小问题:
srand在main里面调用一次即可,不要多次调用。
只有malloc没有free,虽然在这个小程序里面不会造成内存泄漏,但是这个习惯不太好

谢谢指导,菜鸟受教了

引用 5 楼 brookmill 的回复:

当调用Swap(a[i], a[j])的时候,如果i刚好等于j,那Swap进来的两个引用实际上是同一个地址,a+=b的时候实际上是把a和b一起改了,

还想问你下  像这种malloc分配内存的变量作为返回值返回了,在什么地方释放呢

分配的内存,应该是用完之后马上释放。
        int *new_index= New_Partition(A, p, r);
        QuickSort(A, p, new_index[0]-1);
        QuickSort(A, new_index[1]+1, r);
        free(new_index);  // 在这里释放

其实这种情况应该尽量避免,因为有个原则是“谁分配,谁释放”,分配和释放最好在同一个函数里面,这样不容易出错。遇到有些情况必须这么做的,那就只好加倍小心了。
比如有另外七八个程序员都在各自的代码里面调用了New_Partition这个函数,那么他们就需要各自释放返回的内存。你可以在注释和文档里都强调,但是也很难保证他们都记得释放。

引用 9 楼 brookmill 的回复:

分配的内存,应该是用完之后马上释放。
        int *new_index= New_Partition(A, p, r);
        QuickSort(A, p, new_index[0]-1);
        QuickSort(A, new_index[1]+1, r);
        free(new_index);  // 在这里释放

其实这种情况应该尽量避免,因为有个原则是“谁分配,谁释放”,分配和释放最好在同一个函数里面,这样不容易出错。遇到有些情况必须这么做的,那就只好加倍小心了。
比如有另外七八个程序员都在各自的代码里面调用了New_Partition这个函数,那么他们就需要各自释放返回的内存。你可以在注释和文档里都强调,但是也很难保证他们都记得释放。

哦哦 感觉平时写算法导论习题的时候很难想到这些


CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明快排
喜欢 (0)
[1034331897@qq.com]
分享 (0)

文章评论已关闭!