快排

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

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

//快速排序（递归版）
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;
}

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

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

分配的内存，应该是用完之后马上释放。
        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这个函数，那么他们就需要各自释放返回的内存。你可以在注释和文档里都强调，但是也很难保证他们都记得释放。