【数据结构与算法】插入排序和希尔排序-Toy模板网

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

【数据结构与算法】插入排序和希尔排序

文章来源地址https://www.toymoban.com/news/detail-417131.html

一.插入排序 InsertSort

基本思想

动图演示

特性总结

二.希尔排序 ShellSort

基本思想

图例

特性总结

一.插入排序 InsertSort

基本思想

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

当插入第i(i>=1)个元素时，前面的arr[0],arr[1],…,arr[i-1]已经排好序，此时用arr[i]的排序码与arr[i-1],arr[i-2],…的排序码顺序进行比较，找到插入位置即将arr[i]插入，原来位置上的元素顺序后移。

动图演示

【数据结构与算法】插入排序和希尔排序

特性总结

1. 元素集合越接近有序，直接插入排序算法的时间效率越高；
2. 时间复杂度：

a.最坏情况下是O(N^2)；

b.最好情况下，也就是说数据是有序的，这时是O(N)；
3. 空间复杂度：O(1)，它是一种稳定的排序算法；
4. 稳定性：稳定；

void InsertSort(Sdatatype* arr, int n)
{
	int end = 0, tmp = 0;
	int i = 0;
	for (i = 1; i < n; i++)
	{
		end = i - 1;
		tmp = arr[i];
		while (end >= 0)
		{
			if (tmp < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
				break;
		}
		arr[end + 1] = tmp;
	}

	
}

二.希尔排序 ShellSort

基本思想

希尔排序分为预排序（即分组插排，让数组接近有序）和直接插入排序；

希尔排序是把数据分成gap组，每隔gap距离的属于一组数据，对每一组内的数据进行插入排序，这样就可以让整体数据更接近有序状态，这样其内部的插入排序的时间复杂度就接近于O(N)；

假设要排升序：

gap越大，跳的越快，循环的次数越少，大的数据能更快的到后面去；

gap越小，跳的越慢，循环的次数越多。

那这个gap取多少合适呢？

我们可以采用动态的gap，当一组gap跑完时，让gap/2，以此类推，因为是/2，所以gap最后的值一定是1，gap==1时就是直接插入排序了。

我们既可以采用一组一组排的方式，也可以采用多组同时进行的方式。

图例

特性总结

1. 希尔排序是对直接插入排序的优化；
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比；
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定：但是我们一般认为是O(N^1.3)；

4.稳定性：不稳定。

void ShellSort(Sdatatype* arr, int n)
{
	int i = 0, j = 0;
	int end = 0, tmp = 0;
	int gap = n;
	//一组一组地排
	/*while (gap > 1)
	{
		gap /= 2;
		for (j = 0; j < gap; j++)
		{
			for (i = 0; i < n - gap; i += gap)
			{
				end = i;
				tmp = arr[end + gap];
				while (end >= 0)
				{
					if (tmp < arr[end])
					{
						arr[end + gap] = arr[end];
						end -= gap;
					}
					else
						break;
				}
				arr[end + gap] = tmp;
			}
		}
	}*/

	//同时进行排序
	while (gap > 1)
	{
		gap /= 2;
		for (i = 0; i < n-gap; i++)
		{
			end = i;
			tmp = arr[end + gap];
			while (end >= 0)
			{
				if (tmp < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
					break;
			}

			arr[end + gap] = tmp;
		}
	}
}