[Day23]程序菜鸟自学C++资料结构演算法 – 插入排序法(Insertion Sort)

前言：上一篇讲完了排序的基本定义和最普遍的气泡排序，接着要继续介绍更多新的排序。

插入排序法：

和气泡排序一样也是分常简单直观的一种排序，如果有已经排序好的资料要加资料时，就适合使用插入排序，只要按照键值从小排到大就可以了。这样的过程很像我们在玩扑克牌时整理手牌的过程，在发牌时，每一次拿到新的牌就会放到它适合的位子(由小到大)，这样的做法就是插入排序喔！

执行效率分析：
插入排序在排序n个资料时，第一层回圈需要执行n-1次插入n-1个键值，第二层回圈在最差的情况下需要执行1、2、3、…n-2、n-1次，所以合计次数为n(n-1)/2，执行效率为O(n^2)。

如果资料室已经排序好的情况下，只需插入资料(没有搬移动作)，那只须执行外层回圈的n-1次，执行效率为O(n)。

插入排序和气泡排序一样都不需要额外的记忆体，属於稳定性的排序法，因为在资料搬移时，原位置的资料一定要比插入的元素大才会往後移，所以不会交换到相同键直的元素。

直接插入排序实作：依照搜寻插入的位置还能再细分直接插入排序和二分插入排序，就让我们用时做来看看这两者的差异吧。

这样就完成了

也可以查看排序过程和次数喔！

二分插入排序实作：算是插入排序比直接插入排序有效率一些，刚刚实作的直接插入排序是顺着资料查询要放在哪，二分插入排序是用二分法来查询元素插入位置的过程。

具体要怎麽做？直接来实作看看吧！

主要是l、h、m三个变数要如何交换或更改指标才是困难的点。

结果也与直接插入排序一样，这样程序就顺利完成了

本日小结：今天讲了两种插入排序，如果二分插入排序很难理解的话，可以先把直接插入排序先弄懂就好，基础还是比较重要。明天也要来讲解谢尔排序和选择排序v(=∩_∩=)

直接插入排序

template <typename T>
void insert_sort(vector<T>& a) {
	int i = 0;
	for (i = 1; i < a.size(); i++) {
		if (a[i] < a[i - 1]) { //若要插入的元素比前一个元素小
			T t = a[i]; //则交换两元素的位置
			a[i] = a[i - 1];
			int j = i - 2; //宣告j为i-1的前一个值
			for (; j >= 0 && t < a[j]; j--) { //若j大於0且t仍然小於j的值；j指向前一个
				a[j + 1] = a[j]; //则将a[j]移到a[j+1]
			}
			a[j + 1] = t; //我们要查的元素
		}
		print(a);
		std::cout << "排序第" << i << "次\n";
	}
}

二分插入排序

template <typename T>
void binary_insert_sort(vector<T>& a) {
	int i = 0;
	for (i = 1; i < a.size(); i++) {
		if (a[i] < a[i - 1]) { //若要插入的元素比前一个元素小
			T t = a[i]; //则交换两元素的位置
			int l = 0, h = i - 1;
			while (l <= h) {
				auto m = (l + h) / 2;
				if (t < a[m])
					h = m - 1;
				else l = m + 1;
			}
			for (int j = i - 1; j >= h + 1; j--)
				a[i] = a[i - 1];
			a[h + 1] = t;
		};
		print(a);
		std::cout << "排序第" << i << "次\n";
	}
}