【排序篇1】插入排序、希尔排序-Toy模板网

这篇具有很好参考价值的文章主要介绍了【排序篇1】插入排序、希尔排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、插入排序

思路：
插入排序就像玩扑克牌，抽出一张牌作为比较的元素，与前面的牌依次进行比较，小于继续往前比较，大于等于停下插入到当前位置。

图示：
【排序篇1】插入排序、希尔排序,数据结构初阶,排序算法,算法,数据结构,开发语言,c++

void InsertSort(int* a, int n)
{
	//控制所有次排序
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;//记录临时下标
		int tmp = a[end + 1];//比较的元素
		//一趟排序
		while (end >= 0)
		{
			if (a[end] > tmp)//非升序
			{
				a[end + 1] = a[end];//前面的覆盖后面的
			}
			else
			{
				break;//是升序跳出本次循环
			}
			--end;//下标往前移动
		}
		a[end + 1] = tmp;//指向元素的下一个元素覆盖为tmp
	}
}

注意：总共的排序次数是n-1趟，即end最多只能到倒数第二个元素，因为如果end为最后一个元素，那么end+1的位置就是越界的。

特性总结：文章来源地址https://www.toymoban.com/news/detail-798069.html

数组的元素越接近有序，该排序的效率越高
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定

二、希尔排序

希尔排序与插入排序很像，单趟排序的思路基本相似，不同的是，插入排序的每次对比一个指向的元素是向前移动一个距离，希尔排序是移动gap个距离，从大到小，最后为1

【排序篇1】插入排序、希尔排序,数据结构初阶,排序算法,算法,数据结构,开发语言,c++

void ShellSort(int* a, int n)
{
	int gap = n;//先定义好初始距离
	while (gap > 1)//限定条件
	{
		gap = gap / 3 + 1;//距离缩小
		//类似插入排序，只是把1改成gap
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
				}
				else
				{
					break;
				}
				end -= gap;
			}
			a[end + gap] = tmp;
		}
	}
}