快速排序.cpp

/*快速排序采用分治算法

/*快速排序采用分治算法，将所需要排序的内容从文件读入放入数组a[p:r]，按以下三个步骤进行排序
以a[p]为基准元素将数组分为三段，将大于基准元素的放到后面的单元，小的放到前面的单元，
再用递归对a[p:q-1],a[q+1:r]进行排序，最后合并

时间复杂度:最坏时间复杂度：O(n2)
           平均时间复杂度：O(nlogn)
*/

#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include<stdio.h>
#define N 10

int QKPass(int r[], int low, int high)
{
	int Pkey=r[low];
	r[0]=r[low];
	while(low<high)
	{
		//从前往后从后往前搜索比基准元素大或者小的元素，并进行交换
		while(low<high && r[high]>=Pkey)--high;
		if(low==high)
		{
			r[low]=r[0];
			return high;
		}
		else
			r[low]=r[high];
		while(low<high && r[low]<=Pkey) ++low;
		if(low==high)
		{
			r[low]=r[0];
			return low;
		}
		else
			r[high]=r[low];
	} //while
	r[low]=r[0];
	return low;  //返回枢轴所在位置
} //QKPass

void QKSort(int r[], int s, int t)
{
	//对记录序列L.r[s..t]进行快速排序
	if (s<t)
	{
		//长度大于1
		int pos=QKPass(r, s, t);
		//对 L.r[s..t] 进行一次划分
		QKSort(r, s, pos-1);
		//对低子序列递归排序, pos是枢轴位置
		QKSort(r, pos+1, t);  //对高子序列递归排序
	} //if
} //QKSort

void main()
{
	srand(time(0));
	int i,r[N+1];
	int n;
	//从文件读入
	FILE *fp;
	fp=fopen("input.txt","r");
	fscanf(fp,"%d",&n);
	for(i=1; i<=n; i++) fscanf(fp,"%d",&r[i]);
	QKSort(r, 1, n);
	fclose(fp);
	//从文件写入
	fp=fopen("output.txt","w");
	for(i=1; i<=n; i++) 
		fprintf(fp,"%d\n",r[i]);
}