排序入门—插入排序和希尔排序

目录

一.排序

二.排序的稳定性

三.直接插入排序

#插入排序的复杂度分析

四.希尔排序

#预排序

---

一.排序

排序是指按照关键字的递减或者递增顺序对一组记录重新进行排列的操作。

排序在生活中的应用场景很多，比如说在购物平台上我们筛选商品时常用的价格或者销量等等从低到高，从高到低，csdn上的排行榜等等本质上都是排序，所以学习排序是必要的。

二.排序的稳定性

当序列中的关键字各不相同时，那么排序的结果是唯一的。但是当序列中有相同的结果时，那么排序就有多种结果。举个例子，比如说有下面这一个数组：

int arr[] = {1, 3, 9, 3};

如果对这个数组排序结果毫无疑问是1，3，3，9. 但是这两个3哪个排在前哪个排在后呢？如果经过排序后这两个3按照原来的相对顺序排列，那么我们就称这种排序方法是稳定的，否则是不稳定的。稳定与不稳定并没有绝对的优劣之分，各有各的适用场合。

三.直接插入排序

插入排序的思想是每一趟将一个待排序的元素插入到一个有序序列中的适当位置上，使得插入后该序列仍然有序，直到将所有元素插入为止。

这个思想很像我们打扑克牌，我们每次抓到牌都会插入到合适的位置使得我们手上的牌是有序的，直到抓完所有牌。

 所以我们可以和斗地主一样，一次抓一张牌，然后插入到合适位置。依然拿上述数组(排成升序)举例：这个数组中的1就是我们抓的第一张牌，显而易见的是第一张牌不用排序，我们接着抓牌，抓到第二张牌是3，抓到后与1进行比较，3不比1小则排在后面，接着抓到9，9不比3小，排在后面，抓最后一张牌是3，3比9小则要进行比较：我们先拨开9这张牌，看到9的前面排着一个3，3不比3小，所以后面的这张3就放在前面那张3的后面，9的前面，那么抓牌就完毕了。这里因为篇幅问题所以把数组设置的简单一点，但是不管多复杂，过程都是这样的。

根据上面的思路我们可以这样想，将第一个数据想像成一个有序序列，然后将后一个元素插入到这个序列中，如果后一个元素比前一个元素小，那么就把前面一个元素往后挪动一个位置(拨开这张牌给后面的牌腾位置),继续向前比较，如果后一个元素比前一个元素大，那么就把后一个元素插入到前一个元素的后一个位置(把后一张3放到前一张3的后面，9的前面)，就生成了一个新的有序序列，再将下一个元素插入，以此类推，直到将最后一个元素插入就完成了排序。可以看看动图来理解一下过程。

 排序代码如下：

void Insert_sort(int* arr, int size)
{
	for (int i = 0; i < size - 1; i++)
	{
		int end = i;   //end记录有序序列的最后一个元素
		int tmp = arr[end + 1];//将要插入的元素记录下来，因为挪动元素可能会覆盖掉要插入的元素
		while (end >= 0)
		{
			if (tmp < arr[end])
			{
				arr[end + 1] = arr[end];
				--end;
			}
			else
			{
				break; //如果后面元素比前面元素大，就跳出循环，不用再比
			}
		}
		arr[end + 1] = tmp;  //将要插入元素赋给后一个位置上
	}
}

#插入排序的复杂度分析

 插入排序的时间复杂度： 最坏情况是逆序，这时候每个元素都要挪动，时间复杂度是O(n^2)。

空间复杂度：插入排序只需要开辟常数个变量，所以空间复杂度是O(1)。

四.希尔排序

对于插入排序，当序列本身比较有序时，这种排序的效率还是挺高的，但是如果处理的序列非常无序，时间效率则会极其低下。这时候有个叫希尔的人提出，可以先进行预排序，将序列变得有序些再进行插入排序。

所以希尔排序本质上仍是插入排序，其思路为：

1. 预排序

2. 插入排序

#预排序

采用分组插入的方法，将待排序序列分成几组，从而减少直接插入排序的数据量，对每组分别进行插入排序。注意对数据的分组并不是简单的“逐段分割”，而是将相隔某个增量的元素分成一组。

 以这段序列为例，假如设定增量为2，则分组如下，同色线相连元素为一组。

要注意的是增量为1时就是直接插入排序，也就是说当增量越小，这个序列会变得越有序。所以我们可以在分组插入之后将增量逐渐减小，到最后增量为1时就完全有序了。

对于1组中的一个数据，可以写出如下代码进行插入：

int end = 0;
int gap = 3;
int tmp = arr[end + gap];
while (end >= 0)
{
    if (arr[end] > tmp)
    {
        arr[end + gap] = arr[end];
        end -= gap;   
    }
    else
    {
        break;
    }
}

arr[end + gap] = tmp;

 对于一组数据，则要套上一个循环

		for (int i = 0; i < size - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}

解释：因为要访问end + gap位置的值，为了防止越界，所以i < size - gap。同时，用这层循环也可以走完所有的组，可以画图来感受一下，篇幅问题不加赘述。

控制gap的减少则需要再套上一层循环：

void Shellsort(int* arr, int size)
{

	int gap = size;   // 设置增量
	while (gap > 1)
	{
		gap = gap / 3 + 1; 
		for (int i = 0; i < size - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}

}

用下列数组进行测试：

	int arr[] = { 0,0,9,1,6,8056, 94656, 4568 };
	Shellsort(arr, sizeof(arr) / sizeof(int));

结果：

 #希尔排序的时间复杂度比较难计算，笔者还没学，等下篇博文再向大佬们请教请教吧