快速排序：

编程实现快速排序算法。

针对正序、逆序和随机三种不同类型的输入，分别采用选取左端作为轴值和随机选取轴值两种不同的轴值选取方法，测试快速排序的时间开销。

代码示例👇

//author:Mitchell
//date:5.25
#include<iostream>
#include<windows.h>
using namespace std;

template <class T>
void QuickSort1(T Array[], int left, int right);
template <class T>
void QuickSort2(T Array[], int left, int right);
template <class T>
int Partition(T Array[], int left, int right);
template <class T>
void swap(T Array[], int x, int y);
template <class T>
void InsertSort(T Array[], int size, int delta);


int main() {
	int size1000;
	cout << "数组大小：";
	cin >> size1000;
	int size = size1000 / 1000;
	int* test = new int[size];
	memset(test, 0, size * sizeof(int));
	for (int i = 0; i < size; i++) {
		//初始化正序数组
		test[i] = i;
		//初始化逆序数组
		//test[i] = size - 1 - i;
		//初始化随机数组
		//test[i] = rand() % size;
	}
	/*
	cout << "排序前：";
	for (int i = 0; i < size; i++) {
		cout << test[i] << " ";
	}*/

	float t1 = GetTickCount64();
	for (int i = 0; i < 1000; i++)
		QuickSort1(test, 0, size - 1);
	float t2 = GetTickCount64();
	cout << "正序情况下端点轴值的时间开销：" << t2 - t1 << "ms" << endl;

	for (int i = 0; i < size; i++) {
		//初始化正序数组
		test[i] = i;
	}
	t1 = GetTickCount64();
	for (int i = 0; i < 1000; i++)
		QuickSort2(test, 0, size - 1);
	t2 = GetTickCount64();
	cout << "正序情况下随机轴值的时间开销：" << t2 - t1 << "ms" << endl;

	for (int i = 0; i < size; i++) {
		//初始化逆序数组
		test[i] = size - 1 - i;
	}
	t1 = GetTickCount64();
	for (int i = 0; i < 1000; i++)
		QuickSort1(test, 0, size - 1);
	t2 = GetTickCount64();
	cout << "\n逆序情况下端点轴值的时间开销：" << t2 - t1 << "ms" << endl;
	
	for (int i = 0; i < size; i++) {
		//初始化逆序数组
		test[i] = size - 1 - i;
	}
	t1 = GetTickCount64();
	for (int i = 0; i < 1000; i++)
		QuickSort2(test, 0, size - 1);
	t2 = GetTickCount64();
	cout << "逆序情况下随机轴值的时间开销：" << t2 - t1 << "ms" << endl;

	for (int i = 0; i < size; i++) {
		//初始化随机数组
		test[i] = rand() % size;
	}
	t1 = GetTickCount64();
	for (int i = 0; i < 1000; i++)
		QuickSort1(test, 0, size - 1);
	t2 = GetTickCount64();
	cout << "\n随机情况下端点轴值的时间开销：" << t2 - t1 << "ms" << endl;

	for (int i = 0; i < size; i++) {
		//初始化随机数组
		test[i] = rand() % size;
	}
	t1 = GetTickCount64();
	for (int i = 0; i < 1000; i++)
		QuickSort2(test, 0, size - 1);
	t2 = GetTickCount64();
	cout << "随机情况下随机轴值的时间开销：" << t2 - t1 << "ms" << endl;

	/*
	cout << endl << "排序后：";
	for (int i = 0; i < size; i++) {
		cout << test[i] << " ";
	}*/
}


#define THRESHOLD 28
template <class T>
void QuickSort1(T Array[], int left, int right) {
	if (right <= left) {
		return;
	}
	if (right - left + 1 <= THRESHOLD) {
		InsertSort(Array, right - left + 1, 1);
		return;
	}
	int pivot = left;//取left为轴值
	swap(Array, pivot, right);//先将轴值放到数组末端
	pivot = Partition(Array, left, right);//分割后轴值达到正确位置
	QuickSort1(Array, left, pivot - 1);
	QuickSort1(Array, pivot + 1, right);
}

#define THRESHOLD 28
template <class T>
void QuickSort2(T Array[], int left, int right) {
	if (right <= left) {
		return;
	}
	if (right - left + 1 <= THRESHOLD) {
		InsertSort(Array, right - left + 1, 1);
		return;
	}
	int pivot = rand() % (right - left + 1);//随机轴值
	swap(Array, pivot, right);//先将轴值放到数组末端
	pivot = Partition(Array, left, right);//分割后轴值达到正确位置
	QuickSort2(Array, left, pivot - 1);
	QuickSort2(Array, pivot + 1, right);
}


template<class T>
int Partition(T Array[], int left, int right) {//分割函数
	int leftpoint = left;//左指针
	int rightpoint = right;//右指针
	T temp = Array[rightpoint];//将轴值存放到临时变量里
	while (leftpoint != rightpoint) {
		while (Array[leftpoint] <= temp && rightpoint > leftpoint) {
			leftpoint++;
		}//直到找到比轴值大的元素
		if (leftpoint < rightpoint) {
			Array[rightpoint] = Array[leftpoint];
			rightpoint--;
		}
		while (Array[rightpoint] >= temp && rightpoint > leftpoint) {
			rightpoint--;
		}//直到找到比轴值小的元素
		if (leftpoint < rightpoint) {
			Array[leftpoint] = Array[rightpoint];
			leftpoint++;
		}
	}
	Array[leftpoint] = temp;//轴值回填到正确位置
	return leftpoint;//返回轴值位置

}

template <class T>
void swap(T Array[], int x, int y) {
	int z = Array[x];
	Array[x] = Array[y];
	Array[y] = z;
}

template<class T>
void InsertSort(T Array[], int size, int delta) {
	for (int i = delta; i < size; i++) {
		for (int j = i; j >= delta; j -= delta) {
			if (Array[j] < Array[j - delta]) {
				int x = Array[j];
				Array[j] = Array[j - delta];
				Array[j - delta] = x;
			}
		}
	}
}

输出示例👇