舍伍德——快速排序源码报告和算法分析

舍伍德——快速排序源码报告和算法分析 有需要的朋友看下

/*
* Copyright （c） 2010浙江工业大学科学与技术学院 软件学院
* All rights reserved
* 
* 文件名称：fastsort.cpp
* 文件标识：
* 摘    要：
*
* 当前版本：0.1
* 作    者：阮体洪
* 作者标识：软工0807班 200826630715
* 完成日期：2010年12月28日

*/

#include 
#include “d_random.h“
#include “d_timer.h“

#define NUMBER 100000

template
void QuickSort（Type a[] int p int r）
{
	if（p < r）
	{
		int q = Partition（apr）;
		QuickSort（apq-1）;
		QuickSort（aq+1r）;
	}
}

template
int Partition（Type a[] int p int r）
{
	int i = p j = r + 1;
	Type temp;
	Type x = a[p];
	//将 < x 的元素交换到左边区域
	//将 > x 的元素交换到右边区域
	while（true）
	{
		while（a[++i] < x && i < r）;
		while（a[--j] > x）;
		if（i >= j） break;
		temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	a[p] = a[j];
	a[j] = x;
	return j;
	
}

template
int RandomizedPartition（Type a[] int p int r）
{
	randomNumber rand;
	//产生一个大于等于p小于等于r的值
	int i = p + rand.random（r-p+1）;
	Type temp;
	//交换a[i]与a[j]的值
	temp = a[i];
	a[i] = a[p];
	a[p] = temp;
	
	return Partition（a p r）;
}

template
void RandomizedQuickSort（Type a[] int p int r）
{
	if（p	{
		int q = RandomizedPartition（apr）;
		RandomizedPartition（apq-1）;
		RandomizedPartition（aq+1r）;
	}
}
//定义mian函数
int main（）
{//函数main开始
	randomNumber rand;			//定义一个随机数类的变量
	timer t;					//定义一个计时类
	int a[NUMBER]b[NUMBER];	//定义两个数组

	//对a与b数组赋值
	for（int i = 0; i < NUMBER; i++）
	{//for循环开始
		a[i]=rand.random（NUMBER*10）;
		b[i]=a[i];
	}//for循环结束

	cout<<“QuickSort start\n“;
	t.start（）;
	QuickSort（a 0 NUMBER-1）;
	t.stop（）;
	cout<<“QuickSort stop\n“;
	cout<<“QuickSort time:“<	cout<<“RandomizedQuickSort start\n“;
	t.start（）;
	RandomizedQuickSort（b 0 NUMBER-1）;
	t.stop（）;
	cout<<“RandomizedQuickSort stop\n“;
	cout<<“RandomizedQuickSort time:“<	return 0;
}//函数main结束

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       1576  2000-02-19 11:53  舍伍德——快速排序\d_random.h

     文件       1440  2000-08-12 12:10  舍伍德——快速排序\d_timer.h

     文件       2073  2010-12-28 23:07  舍伍德——快速排序\fast_sort.cpp

     文件      94208  2010-12-28 23:03  舍伍德——快速排序\基于舍伍德算法快速排序.doc

     目录          0  2010-12-28 23:03  舍伍德——快速排序

----------- ---------  ---------- -----  ----

                99297                    5