快速排序

快速排序（QuickSort）的确是该排序方法的一个恰如其是的命名，因为恰到好处时它是迄今为止在内排序方面最快的一种排序方法。快速排序的应用非常广泛，其中典型的应用就是UNIX系统调用库函数例程中的qsort函数。但是有趣的是快序排序往往由于最差性能时间代价而在默写应用中无法采用。

快速排序的算法;
1、选择一个轴值（piovt），把要排序的数组中小于轴值的元素换到轴值前面，比轴值大的元素换到轴值后面。
2、以上面的轴值为标志，将原来的一组数据分成两组，（这也称是该数组的一个分割（partition）），再分别对这个分割的两部分实行步骤1.最后则就排好了。

快排算法代码：

void QuickSort::QSort(int index1,int index2)
{
	if(index2 <= index1) return;//结束条件
	int piovt = FindPiovt(index1,index2);//寻找轴值
	Swap(piovt,index2);
	int k = Partition(index1,index2,p[index2]);//数组的分割
	Swap(k,index2);
	QSort(index1,k-1);
	QSort(k+1,index2);
}

对于寻找轴值piovt，现在一般选择中间的额值，方便写算法。但是在实际中选择大小在中间的元素，算法比较复杂，但是这能提高快速排序的时间代价性能。

int QuickSort::FindPiovt(int x1,int x2)
{
	return (x2+x1)/2;//在这里选择中间的值为轴值
}

对于分割算法。
1、先将轴值和最后一个元素交换。
2、从该分割的第一个元素开始向后找，从该分割倒数第二个元素向前找，向后找到比轴值大的向前找到比轴值小的元素，然后将两个元素交换。直到寻找的路线交叉，即向前找的元素到向后找元素的前面了。
3、此时在交换最后的左右标志值。
4、返回分割的标志位

int QuickSort::Partition(int l,int r,int& Piovt)
{
	do
	{
		while(p[l]<Piovt)
		{
			l++;
		}
		while(r!=0&&p[--r]>Piovt)
		{
		}
		Swap(l,r);
	}while(l<r);
	Swap(l,r);
	ShowElem();
	return l;
}

下面是完整代码

//QuickSort.h
#pragma once
#include<fstream>
#include<iostream>
using namespace std;
const int Max = 40;
class QuickSort
{
public:
	QuickSort();//构造数据
	~QuickSort();//释放内存
	void QSort(int index1,int index2);//快速排序
	int FindPiovt(int x1,int x2);//寻找轴值
	void Swap(int i,int j);//交换下标为ij的数据
	void ShowElem();//打印数据
	int Partition(int l,int r,int &);//分割
	int GetSize();//返回数据规模
private:
	int  *p;
	int Size;
};

QuickSort::QuickSort()
{
	p = new int[Max];
	int a,i=0;
	ifstream infile("f1.txt",ios::in);//这里实现文件操作也可以改成自己传入数据的代码
	if(!infile)
	{
		cout<<"文件打开失败！"<<endl;
		exit(0);
	}
	while(infile>>a)
	{
		p[i++]=a;
	}
	infile.close();
	Size = i;
}

QuickSort::~QuickSort()
{
	delete []p;
}

void QuickSort::QSort(int index1,int index2)
{
	if(index2 <= index1) return;//结束条件
	int piovt = FindPiovt(index1,index2);//寻找轴值
	Swap(piovt,index2);
	int k = Partition(index1,index2,p[index2]);//数组的分割
	Swap(k,index2);
	QSort(index1,k-1);
	QSort(k+1,index2);
}


int QuickSort::FindPiovt(int x1,int x2)
{
	return (x2+x1)/2;//在这里选择中间的值为轴值
}


void QuickSort::Swap(int i,int j)
{
	int temp = p[i];
	p[i] = p[j];
	p[j] = temp;
	cout<<"交换"<<p[i]<<"和"<<p[j]<<endl;//这只是显示排序过程方便检查
}

void QuickSort::ShowElem()
{
	for(int i = 0;i< Size;i++)
	{
		std::cout<<p[i]<<" ";
		if(9 == i%10)
			std::cout<<std::endl;
	}
}

int QuickSort::Partition(int l,int r,int& Piovt)
{
	do
	{
		while(p[l]<Piovt)
		{
			l++;
		}
		while(r!=0&&p[--r]>Piovt)
		{
		}
		Swap(l,r);
	}while(l<r);
	Swap(l,r);
	ShowElem();
	return l;
}

int QuickSort::GetSize()
{
	return Size;
}
//main.cpp

#include<iostream>
using namespace std;


#include"QuickSort.h"

int main()
{
	QuickSort qsort;
	cout<<"原始数据:\n";
	qsort.ShowElem();
	cout<<"排序过程:\n";
	qsort.QSort(0,qsort.GetSize()-1);
	cout<<"最终结果:\n";
	qsort.ShowElem();
	return 0;
}