快速排序(QuickSort) -- C++实现


实现代码--vector版

// QuickSort.h
#ifndef QUICKSORT_H
#define QUICKSORT_H

#include<iostream>
using namespace std;

#include "Component.h"

namespace jay{

	template<typename T>
	int Partition(vector<T> &input,int left,int right)
	{
		// 切分元素
		T partitionValue = input[left];

		// 左扫描指针
		int left_index = left + 1;
		// 右扫描指针
		int right_index = right;

		T temp;
		while(left_index <= right_index)
		{
			// 从左至右找一个大于等于切分元素的值
			while (partitionValue > input[left_index])
			{
				left_index++;
				if (left_index == right)
					break;
			}

			// 从右至左找一个小于等于切分元素的值
			while (partitionValue < input[right_index])
			{
				right_index--;
				if (right_index == left) 
					break;
			}

			// 如果左右扫描指针还没有重合
			if (left_index < right_index) 
				// 交换input[left_index]和input[right_index]的值
				ExchangeArrayElements(input, left_index++, right_index--);
			else
				break;

		}

		// 交换切分元素和右扫描指针的值
		ExchangeArrayElements(input, left, right_index);

		return right_index;
	}

	template< typename T >
	void QuickSort(vector<T> &input,int left,int right)
	{
		if (left >= right)
			return;

		// 切分元素的索引
		int nPartitionIndex = Partition(input,left,right);

		// 切分元素nPartitionIndex的左部分进行排序
		QuickSort(input,left,nPartitionIndex-1);

		// 切分元素nPartitionIndex的右部分进行排序
		QuickSort(input,nPartitionIndex+1,right);
	}

};

#endif

测试代码

//main.cpp

#include <time.h>
#include<windows.h>

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

#include "Component.h"
#include "SelectSort.h"
#include "InsertionSort.h"
#include "ShellSort.h"
#include "MergeSort.h"
#include "MergeInsertionMixSort.h"
#include "MergeSortBottomToTop.h"
#include "QuickSort.h"

using namespace jay;


int main(int argc, char* argv[])
{
	int iCount = 0;
	cin>>iCount;

	vector<int> myvector(iCount);

	iCount = 0;
	int p;
	while(cin>>p)
	{
		myvector[iCount] = p;
		iCount++;
	}

//	PrintArray<int>(myvector,iCount,"排序前:");

	TimeCalculator timec;
	QuickSort<int>(myvector,0,iCount-1);
	timec.PrintTimeInfo();

//	PrintArray<int>(myvector,iCount,"排序后:");

	cout << "是否已序? " << isSortedAndPrintInfo<int>(myvector,0,iCount-1) << endl;

}

在测试的时候发现此版本比归并排序和希尔排序都慢很多,后来取消了vector<T>作泛型参数使用,再使用同样的数据[千万级别]测试发现性能提升了接近10倍

 

下面附上数组版本的实现

实现代码-数组版

// QuickSort.h
#ifndef QUICKSORT_H
#define QUICKSORT_H

#include<iostream>
using namespace std;

#include "Component.h"

namespace jay{

	template<typename T>
	int Partition(T *input,int left,int right)
	{
		// 切分元素
		T partitionValue = input[left];

		// 左扫描指针
		int left_index = left + 1;
		// 右扫描指针
		int right_index = right;

		T temp;
		while(left_index <= right_index)
		{
			// 从左至右找一个大于等于切分元素的值
			while (partitionValue > input[left_index])
			{
				left_index++;
				if (left_index == right)
					break;
			}

			// 从右至左找一个小于等于切分元素的值
			while (partitionValue < input[right_index])
			{
				right_index--;
				if (right_index == left) 
					break;
			}

			// 如果左右扫描指针还没有重合
			if (left_index < right_index) 
				// 交换input[left_index]和input[right_index]的值
				ExchangeArrayElements(input, left_index++, right_index--);
			else
				break;

		}

		// 交换切分元素和右扫描指针的值

		ExchangeArrayElements(input, left, right_index);

		return right_index;
	}

	template< typename T >
	void QuickSort(T *input,int left,int right)
	{
		if (left >= right)
			return;

		// 切分元素的索引
		int nPartitionIndex = Partition(input,left,right);

		// 切分元素nPartitionIndex的左部分进行排序
		QuickSort(input,left,nPartitionIndex-1);

		// 切分元素nPartitionIndex的右部分进行排序
		QuickSort(input,nPartitionIndex+1,right);
	}

};

#endif

测试代码

//main.cpp

#include <time.h>
#include<windows.h>

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

#include "Component.h"
#include "SelectSort.h"
#include "InsertionSort.h"
#include "ShellSort.h"
#include "MergeSort.h"
#include "MergeInsertionMixSort.h"
#include "MergeSortBottomToTop.h"
#include "QuickSort.h"

using namespace jay;


int main(int argc, char* argv[])
{
	
	int iCount = 0;
	cin>>iCount;
	int *testarray = new int[iCount];

	iCount = 0;
	int p;
	while(cin>>p)
	{

		testarray[iCount] = p;

		iCount++;
	}

//	PrintArray<int>(testarray,iCount,"排序前:");
	TimeCalculator timec;
	QuickSort<int>(testarray,0,iCount-1);
	timec.PrintTimeInfo();
//	PrintArray<int>(testarray,iCount,"排序后:");

	cout << "是否已序? " << isSortedAndPrintInfo<int>(testarray,0,iCount-1) << endl;
	delete []testarray;

}

 

暂无评论

注册用户登录后才能发表或者回复评论,请先登录 注册。