quicksort.cpp

快速排序 算法题 有运行结果 分治法思想 二分搜索技术

#include <iostream>
#include <iomanip>
using namespace std;


template<class Type>
void QuickSort(Type a[],int p,int r)
{
	if(p<r)
	{
		int q = Partition(a,p,r);
		QuickSort(a,p,q-1);
		QuickSort(a,q+1,r);
	}
}

template<class Type>
int Partition(Type a[],int p,int r)
{
	int i = p,j = r+1;
	Type x = a[p];
	while(true)
	{
		while(a[++i]<x&&i<r);
	    while(a[--j]>x);
		if(i>=j)
			break;
		Swap(a[i],a[j]);
	}
	a[p] = a[j];
	a[j] = x;
	return j;
}


template<class Type>
void Swap(Type &a,Type &b)
{
	Type temp = a;a = b;b = temp;
}


int main()
{
	int ok[8] = {3,8,9,1,2,5,6,4};
	cout<<"排序前的数组为"<<endl;
	cout<<ok[0]<<setw(3)<<ok[1]<<setw(3)<<ok[2]<<setw(3)<<ok[3]<<setw(3)<<ok[4]<<setw(3)<<ok[5]<<setw(3)<<ok[6]<<setw(3)<<ok[7]<<endl;
	cout<<"QuickSort is Running..."<<endl;
	int qq = 7;
	QuickSort(ok,0,qq);
	cout<<"排序后的数组为"<<endl;
	cout<<ok[0]<<setw(3)<<ok[1]<<setw(3)<<ok[2]<<setw(3)<<ok[3]<<setw(3)<<ok[4]<<setw(3)<<ok[5]<<setw(3)<<ok[6]<<setw(3)<<ok[7]<<endl;
}