【排序算法】直接插入排序 & 折半插入排序（二分法插入排序）

2018-07-29

写在前面

排序：就是将一组杂乱无章的数据按照一定的规律(升序或降序)组织起来。
数据表：待排序数据元素的有限集合。
排序码：通常数据元素有多个属性域，其中有一个属性域可用来区分元素，作为排序依据，该域即为排序码。

排序算法的性能评估：

一个算法执行时间是衡量算法好坏的重要参数。排序算法的时间开销可用算法中的数据交换次数，和数据移动次数来衡量。

直接插入排序算法

算法思想：

当插入第 i 个元素时，前面的 i-1 个元素已经有序。其实直接插入排序就是拿一个数，放到前面有序的数中就可以了。具体怎么放，不管是循环交换两个数的位置，还是先找到位置，再将该位置后面的数顺移，都没毛病的。

这里写图片描述

#####算法性质：

直接排序算法是稳定的，
算法的时间复杂度为O(n^2)，
最好是用于量小、接近有序的数据。

代码实现：

template<typename T>
void INsert_Sort(T *array, int len)
{
	int key = 0;
	int end = 0;

	for (int i = 1; i < len; i++)
	{
		key = array[i];
		for (end = i - 1; (end >= 0) && array[end] > key; end--)
		{
			array[end + 1] = array[end];
		}
		array[end + 1] = key;
	}
}

刚在前面直接插入排序算法性质中说最好用于数据量小且基本有序的的情况。当数据量比较大时，时间会大量的耗费在移动和比较元素上，导致性能降低。因此可以从元素比较和移动上来优化算法。

折半插入排序算法

折半插入排序又称二分法插入排序。和直接插入排序算法不同的是：在插入元素时，利用折半搜索法寻找插入位置。

算法思想：

过程同直接插入排序，仅仅是在找插入位置时，不是顺序遍历，而是二分法查找位置。因为：如果要找地 i 个元素的插入位置，那么第 i-1 个元素是已经有序的，可以用二分查找来寻找位置。

算法分析：

时间复杂度：折半插入排序仅仅是减少了比较元素的次数，约为O(nlogn)，而且该比较次数与待排序表的初始状态无关，仅取决于表中的元素个数n；而元素的移动次数没有改变，它依赖于待排序表的初始状态。因此，折半插入排序的时间复杂度仍然为O(n²)，但它的效果还是比直接插入排序要好。
空间复杂度：排序只需要一个位置来暂存元素，因此空间复杂度为O（1）。

代码实现：

void Bin_Insert_Sort(int* a, int n)

{

	int Low;
	int High;
	int Middle;
	for (int i = 1; i < n; ++i)
	{
		Low = 0;
		High = i - 1;
		// 求取插入位置
		while (Low <= High)
		{
			Middle = (Low + High) / 2;
			if (a[Middle] > a[i])
				High = Middle - 1;
			else
				Low = Middle + 1;
		}

		// 插入
		for (int j = i - 1; j > High; --j)
		{
			swap(a[j], a[j + 1]);     //这里也可以挨个移动元素后插入
		}
	}
}

本文链接： http://askunix.github.io/2018/07/29/插入排序/
版权声明：本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可，转载请注明出处！