[Day24]程序菜鸟自学C++资料结构演算法 – 选择排序法(Selection Sort)和谢尔排序法(Shell Sort)

前言：今天要来介绍的两个排序法，是基础排序的最後两个，让我们来看看它们的特点吧！

选择排序法：

也是相当直观简单的排序法，只要从一整个排序中选出键值最小的，然後和第一个键值做交换，接着从剩下的键值中选出第二小的和第二个交换键值，重复执行直到最後一个键值为止。

执行效率分析：和气泡排序一样，第一层回圈需要执行n-1次，n是全部排序键值的个数，第二层回圈依序为n-1、n-2、….2、1、0，总次数为n(n-1)/2，时间复杂度为O(n^2)。
不需要额外的记忆体，是一种不稳定的排序，因为元素在交换时可能会交换到相同键直的元素。

选择排序实作：

这样就完成罗！

谢尔排序法：

谢尔排序和上一篇讲到的插入排序原理非常相似，以插入排序的优点来提升排序效率，是插入排序的改良版。接着用图解说明一下操作概念。

执行效率分析：间隔的可以说是希尔排序最重要的一环，不同的间隔序列会造成不同的效率，常见的可分为三种间隔序列。

谢尔排序法不需要额外的记忆体空间，但是不具有稳定性，因为在排序时会进行分割，然後分别执行插入排序，所以有可能会交换到相同间值的元素。

谢尔排序实作：

第一行为间隔=5的排序，第二行为间隔=3的排序，第二行为间隔=1的排序，排序过程没有异常，而且效率非常高！

本日小结：今天包含前两篇文章就结束了基础排序法的部分，选择排序和希尔排序的难度都不高，相信大家一定能很快吸收，接下来的排序法会是复杂一点的分割资料的排序法，共有两种等着大家来攻略(^人^)

选择排序法

template <typename T>
void selection_sort(vector<T>& a) {
	for (int i = 0; i < a.size() - 1; i++) {
		auto minPos = i; //先假定最小直的位置在i
		for (int j = i + 1; j < a.size(); j++)
			if (a[j] < a[minPos])
				minPos = j;
		if (minPos != i)  //如果i已经是最小值则不交换，不等於就交换
			Swap(a[i], a[minPos]);
		print(a);
	}
}

谢尔排序法

template <typename T> //先撰写希尔排序完成一次的过程，方法和插入排序非类似
void shell_pass(vector<T>& a,const int d) { //d为希尔排序的间隔
	for (int i = d; i < a.size(); i++) {
		if (a[i] < a[i - d]) { 
			T t = a[i]; 
			a[i] = a[i - d];
			int j = i - 2*d; 
			for (; j >= 0 && t < a[j]; j--) { 
				a[j + d] = a[j]; 
			}
			a[j + d] = t; 
		}
	}
	print(a);
}
template <typename T> 
void shell_sort(vector<T>& a, const vector<int> &ds) {
	for (auto d : ds) //建立希尔排序的间隔数，并依照间隔排序
		shell_pass(a, d);
}