QuickSort3way -- C++实现


实现代码

// QuickSort3way.h
#ifndef QUICKSORT3WAY_H
#define QUICKSORT3WAY_H

#include<iostream>
using namespace std;

#include "Component.h"

namespace jay{

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

		// input[left..lt-1] < v
		// input[lt..i-1] = v
		// input[gt+1..right] > v
		// input[i..gt] 未确定
		int lt = left;
		int gt = right;
		T v = input[left];
		int i = left + 1;
		while (i <= gt) 
		{
			if  (input[i] < v) 
				// 交换lt和i,i+1,lt+1
				ExchangeArrayElements(input, lt++, i++);
			else if (input[i] > v) 
				// 交换gt和i,i不变,gt-1
				ExchangeArrayElements(input, i, gt--);
			else              
				i++;
		}

		// 此时 input[left..lt-1] < v = input[lt..gt] < input[gt+1..right]. 

		// 对input[left] - input[lt-1]进行排序
		QuickSort3way(input, left, lt-1);

		// input[lt] - input[gt]是已序的都等于v

		// 对input[gt+1] - input[right]进行排序
		QuickSort3way(input, gt+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"
#include "QuickInsertionSort.h"
#include "QuickSort3way.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;
	QuickSort3way<int>(testarray,0,iCount-1);
	timec.PrintTimeInfo();
//	PrintArray<int>(testarray,iCount,"排序后:");

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

}

使用2份千万级别的数据对QuickSort3way和QuickSort算法进行测试

发现在含有大量重复数据的情况下,三向切分比普通的快速排序快了40%左右

但是在随机数据中,普通快速排序的性能比三向切分快速排序的2倍多

所以,除非明确需要针对非常多的重复数据排序才使用QuickSort3way,否则,一般应使用QuickSort

暂无评论

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