[Day25]程序菜鸟自学C++资料结构演算法 – 快速排序法(Quick Sort)

前言：讲解完了基础的排序法後，接着要来讲解比较高等的排序法，今天和明天要介绍的都是始於分割资料的排序法，就先从快速排序开始讲起。

分割资料的排序法：这类型的排序法，主要是用**「各个击破」(Divide-and-Conquer)的分治演算法**，这种演算法是将排序问题分割成多个小问题，在使用递回的方式逐一解决各个子问题後所完成的排序法。

快速排序法：

是目前公认最佳的排序法，虽然和基础的气泡排序一样，都是采用交换的方式进行排序，但是透过分割的技巧，使得快速排序的执行效率远大於气泡排序。
分割资料的方式是选择一个键值作为分割标准，将键值分成两半的两个集合，一半是比标准值还要大的键值集合，另一半是较小或相等的集合。
接着每一半的键值使用相同的分割法，直到无法继续分割，此时所有的键值以排序完成。

如何挑选基准值？常用的分式可以取乱数或是取数列的最左或最右边，也可以用比较进阶的方式，取数列的第一、中间和最後一个数，取第二大的当基准值也可以。

因为快速排序需要使用递回函式，所以要有额外的记忆体空间来处理递回方法。属於不稳定的排序法，因为排序元素会进行分割和交换，所以有可能会交换到相同键值的元素。

快速排序实作：

这样就完成了！

本日小结：快速排序虽然是很有效率的排序法，不过很显而易见的并没有像基础排序法那样的直观简单好理解，而且如果遇到最糟的情况下会慢上很多，但快速排序依旧是非常重要的，还是学起来会比较好，明天要介绍同样为分割排序「合并排序法」Ꮚ^ꈊ^Ꮚ

template <typename T>
int Partition(vector<T>& a, int L, int H) { //编写快速排序的划分
	T t = a[L]; //把最左边的元素当作基准值
	while (L < H) {
		print(a);
		//H向左，直到遇见比基准值小的
		while (L < H && !(a[H] < t))
			H--;
		a[L] = a[H];
		//L向右，直到遇见比基准值大的
		while (L < H && a[L] < t)
			L++;
		a[H] = a[L];
	}
	a[L] = t;
	return L;
}

template <typename T>
void quick_sort(vector<T>& a, int L, int H) { //编写快速排序的过程
	if (L < H) { //待排序数列长度需大於1
		int pivotloc = Partition(a, L, H);
		//对左子集进行快速排序
		quick_sort(a, L, pivotloc - 1);
		//对右子集进行快速排序
		quick_sort(a, pivotloc + 1, H);
	}
}