[数据结构与算法]排序算法-插入排序（直接插入排序、Shell排序）

一、直接插入排序

视频讲解

基本思想： 将第一个元素看成一个有序子序列，再依次从第二个元素起逐个插入这个有序的子序列中。

一般情况下，在第i步上，将elem[i]插入到由elem[0]~elem[i-1]构成的有序子序列中。

平均时间复杂度：O（n^2）

代码实现（C++）：

template <class ElemType>
void StraightInsertSort(ElemType elem[], int n)
//操作结果：对数组elem做直接插入排序
{
	for (int i = 1; i < n; i++)
	{
		//第i趟直接插入排序
		//暂存elem[i]
		ElemType e = elem[i];
		//临时变量
		int j = 0;
		for (j = i - 1; j >= 0 && e < elem[j]; j--)
		{
			//将比e大的元素都向后移
			//后移
			elem[j + i] = elem[j];
		}
		//j+1为插入位置
		elem[j + 1] = e;
	}
}

二、Shell排序（希尔排序）

视频讲解

基本思想： 先将整个待排序的元素序列分割成若干子序列，分别对各子序列进行直接插入排序，等整个序列中的元素“基本有序”时，再对全体元素进行一次直接插入排序。

代码实现（C++）：

template <class ElemType>
void ShellInsert(ElemType elem[], int n, int incr)
//操作结果：对数组elem做一趟增量为incr的Shell排序，
//对插入排序的修改是子序列中前后向量记录的增量为incr而不是1
{
	for (int i = incr; i < n; i++)
	{
		//第i-incr+1趟插入排序
		//暂存elem[i]
		ElemType e = elem[i];
		//临时变量
		int j = 0;
		for (j = i - incr; j >= 0 && e < elem[j]; j -= incr)
		{
			//将子序列中比e大的元素都后移
			//后移
			elem[j + incr] = elem[j];
		}
		//j+incr为插入位置
		elem[j + incr] = e;
	}
}

template <class ElemType>
void ShellSort(ElemType elem[], int n, int inc[], int t)
//操作结果：按增量序列inc[0...t-1]对数组elem做Shell排序
{
	for (int k = 0; k < t; k++)
	{
		//第k+1趟Shell排序
		ShellInsert(elem, n, inc[k]);
	}
}