算法之旅 快速排序 速度超过库函数，挑战 stl

快速排序之续

个人信息：就读于燕大本科软件工程专业 目前大三;

本人博客：google搜索“cqs_2012”即可;

个人爱好：酷爱数据结构和算法，希望将来搞科研为人民作出自己的贡献;

博客内容：快速排序之续；

博客时间：2014-4-9

编程语言：C++

编程坏境：Windows 7 专业版 x64

编程工具：vs2008 32位编译器

引言

每次做题都有不同的感觉，渐渐才体会到自己的能力慢慢提高，同时也说明了自己不懂得总结，一条路走了好多次，每一次脚印都不同。

中心

实现并优化快速排序，提高效率

以前我写过一篇博客是 快速排序，但是自己跑实验没有跑过库函数，这一次终于突破了库函数。想自己敬礼，超越永无止境

以前自己的快速排序有两种 1 单向遍历 2，双向异步遍历

这一次我用的是 双向同步遍历

核心思想如下

		while( i < j )
		{
			if( V[i] > key && V[j] < key )
			{
				Swap(V,i,j,Size);
			}
			if( V[i] <= key )
			{
				i++;
			}
			if( V[j] >= key )
			{
				j--;
			}
		}

因为一会要去上课了，所以没有举例子，没有用照片说的更详细一些，还请见谅，等晚上下课回来后，立马补上。

实验

程序比较

1 。单向遍历

2.双向异步遍历

 

3. 双向同步遍历

4 库函数

代码

双向同步遍历代码(其他的代码，都在快速排序博客里有)

test.cpp

#include<iostream>
#include <windows.h>
#include<fstream>
using namespace std;

// data declare
size_t const size = 1000000 ;

// function declare
template<class T>
void Initialize( T * &V ,size_t s);
template<class T>
void QuickSort(T * &V,size_t s,size_t e,size_t Size);
template<class T>
void Swap(T * &V,size_t i,size_t j,size_t Size);

void SwapInt(size_t &i,size_t &j);
template<class T>
void DataCout(T * &V, size_t Size);

// function main
int main()
{
	int * V = new int[ size ] ;
	DWORD time_s ,time_e ;

	Initialize(V,size) ;

	//VectorCout(V);
	cout<<"quick sort"<<endl;
	DataCout(V,size);
	time_s = GetTickCount();
	
	QuickSort(V,0,size - 1,size);
	time_e = GetTickCount() ; 
	
	cout<<"给 "<<size<<" 个数据排序 用时 "<< time_e - time_s <<" 毫秒 "<<endl;
	//system("pause");
	DataCout(V,size);
	delete V;

	system("pause");
	return 0;
}


// function: initialize data
// input: a array point
// output: void
// 功能: 实验数据初始化
template<class T>
void Initialize( T * &V ,size_t s)
{
	if( V && s >= 0 )
		for(size_t i = 0; i < size; i++)
		{
			V[i] = rand() % 100000 ;
		}
}

// function: Quick sort
// input: a array data ,two label s and e , and the max size of the array
// output: void
// 功能: 对 data【s···e】进行快速排序
template<class T>
void QuickSort(T * &V,size_t s,size_t e,size_t Size)
{
	if(V && 0 <= s && s < e && e < Size )
	{	
		T key = V[s];
		size_t i = s ;
		size_t j = e ;

		while( i < j )
		{
			if( V[i] > key && V[j] < key )
			{
				Swap(V,i,j,Size);
			}
			if( V[i] <= key )
			{
				i++;
			}
			if( V[j] >= key )
			{
				j--;
			}
		}

		//cout<<key<<endl;
		if(i==j)
		{
			if(V[i] > key)
			{
				if( i == s )
				{
					Swap(V,s,e,Size);
					j++;
				}
				else i -- ;
			}
			else if(V[i] < key)
			{
				if( j == e )
				{
					Swap(V,s,e,Size);
					i--;
				}
				else j++;
			}
			else
			{
				i--;
				j++;
			}
			QuickSort(V,s,i,Size);
			QuickSort(V,j,e,Size);
		}
		else if(i>j)
		{
			QuickSort(V,s,j,Size);
			QuickSort(V,i,e,Size);
		}
	}
}


// function: swap data
// input: a array data ,two label s and e , and the max size of the array
// output: void
// 功能: 对 data【s】 and data【e】进行数据交换
template<class T>
void Swap(T * &V,size_t i,size_t j,size_t Size)
{
	if(i >= 0 && i < Size && j >= 0 && j < Size )
	{
		T d = V[i];
		V[i] = V[j];
		V[j] = d;
	}
}

// function: swap data
// input: two label s and e 
// output: void
// 功能: 对 s and e 进行数据交换
void SwapInt(size_t &i, size_t &j)
{
	size_t d = i ;
	i = j;
	j = d;
}


// function: output data
// input: a array data point and its size with size_t  
// output: void
// 功能: 输出array里的数据
template<class T>
void DataCout(T * &V, size_t Size)
{
	cout<<"data follows"<<endl;
	ofstream writer;
	writer.open("data.txt");
	writer.clear();
	for(size_t i = 0; i < Size; i++)
	{
		writer<<V[i]<<"\n";
	}
	writer.close();
}

 

算法之旅 快速排序 速度超过库函数，挑战 stl,布布扣,bubuko.com

算法之旅 快速排序 速度超过库函数，挑战 stl

原文：http://blog.csdn.net/cqs_experiment/article/details/23263351