浅谈数据结构排序算法中的折半插入排序

2020-02-25

数据结构中的排序算法有：插入类排序、交换类排序、选择排序、堆排序、归并排序、桶排序。而插入类排序包括：直接插入排序、折半插入排序、希尔排序。

其中：折半插入排序（稳定的排序）

原理步骤：

1）首先，利用折半查找法确定插入的正确位置；

2）其次，再一次性对元素进行移动；

3）最后，执行插入指令

先讲讲折半查找法：

折半查找也叫二分查找，该方法要求必须是线性存储结构。其原理就是每次与当前有序序列中间下标的数组进行比较，如果此时要插入的值比该A[mid]大，那么我就进入这个有序序列的右半部分继续进行查找，否则就进入左半部分继续查找。直到找到合适位置（low=high时）。

注：下列两种方法都是从小到大排序

方法一：建立哨兵（A[0]为哨兵，类似于中介变量，用于暂存元素值）

#include <iostream>
using namespace std;
#define  ElemType int
int A[] = { 10,4,18,7,6 };//A[0]为哨兵，其值无效，即：只对A[1]-A[4]进行排序
int n = 4;//对除了A[0]元素以为的A[1]-A[4]进行排序

void InsertSort(ElemType A[], int n)//直接插入排序执行函数
{
	int i, j, low, high, mid;
	for (i = 2;i <= n;i++)//对元素逐个执行折半插入排序，插入到排好的有序序列中，默认A[1]已经排好了
	{
		A[0] = A[i];//把当前要插入的元素先暂存在哨兵A[0]
		low = 1;high = i - 1;//注：low为1。有序序列：A[1]-A[i-1]。不包括A[0]。取已经排完的有序序列数组的收尾下标，并赋值给low,high
		while (low <= high)//执行折半排序
		{
			mid = (low + high) / 2;//当前首尾下标折半并赋值给mid
			if (A[mid] > A[0])//判断当前中间下标数组的元素值与哨兵内元素值的大小
				high = mid - 1;
			else
				low = mid + 1;
		}
		for (j = i - 1;j >=low ;j--)//将该位置后的元素都向后挪动一位
			A[j + 1] = A[j];
		A[low] = A[0];//执行插入操作
	}
}

int main()
{
	cout << "哨兵为A[0]，其值无效，仅用于暂存数值，A[0]初值为：" << A[0] << endl;//该位置A[0]为哨兵，其内值无效，相当于是个中间变量，用于数值的暂时存放。
	InsertSort(A, n);//调用直接插入排序算法
	cout << "数组A[]的最终排序为：";
	for (int z = 1;z <= n;z++)//A[1]开始显示直到A[n]；A[]元素个数为n+1，其中A[0]无效
		cout << A[z] << "  ";//输出数组排序结果
}

时间复杂度：O($n^2$)

注：

折半插入排序分为三个操作：比较（折半查找）、移动（插入位置的元素向后统一挪动一格）、插入（将元素插入到合适的位置上）。其中比较操作的时间复杂度为：O($nlogn$)；移动操作的时间复杂度为：O($n^2$)；插入操作的时间复杂度为：O(1)。所以总时间复杂度为：O($nlogn$)+O($n^2$)+O(1)=O($n^2$)

空间复杂度：O(1) 注：哨兵A[0]（常数个空间）

方法二：设定一个中间变量temp（主流）

#include <iostream>
using namespace std;
#define  ElemType int
int A[] = { 10,3,11,7,6 };
int n = 5;//A[]中有5个元素，或者在主函数内写n=size(A);从而获取数组A[]的大小
void  InsertSort(ElemType A[], int n)
{
	int i, j, low, high, mid;
	ElemType temp;//定义中间变量temp，用于暂存数组元素的值
	for (i = 1;i < n;i++)//从A[1]开始进行循环，直到整个数组循环一遍，A[0]默认为已经排号了位置
	{
		temp = A[i];//把当前数组的元素值先暂存在temp中
		low = 0,high = i - 1;//注：low为0。对有序序列：A[0]-A[i-1]执行元素A[i]的插入排序。取已经排完的有序序列数组的收尾下标，并赋值给low,high
		while (low <= high)//执行折半排序
		{
			mid = (low + high) / 2;//当前首尾下标折半并赋值给mid
			if (A[mid]>temp)//判断当前中间下标数组的元素值与temp变量元素值的大小
				high = mid - 1;
			else
				low = mid + 1;
		}
		for (j = i - 1;j >= low;j--)//将该位置后的元素都向后挪动一位
			A[j + 1] = A[j];
		A[low] = temp;//执行插入操作
	}

}

int main()
{
	InsertSort(A, n);//调用直接插入排序算法
	cout << "数组A[]的最终排序为：";
	for(int x=0;x<n;x++)//显示A[0]-A[n-1]
		cout << A[x]<<"  ";//输出数组排序结果
}

时间复杂度：O($n^2$)

注：

空间复杂度：O(1) 注：中间变量temp（常数个空间）`