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

﹏ヽ暗。殇╰゛Y 2022-05-31 12:57 229阅读 0赞

# 一、插入排序 #

## 1.算法思想 ##

要求在一个已经有序的数据序列中插入一个数据，并且插入次数据后数据序列依然有序，这时就需要用到一种新的排序方法——插入排序，其基本思想就是每步讲一个待排序的记录，按其关键码值的大小插入到前面已经排序的文件中适当的位置，直至全部插入完为止。

## 2.具体步骤 ##

1.  从第一个元素开始，该元素可以认为已经被排序
2.  取出下一个元素，在已经排序的元素序列中从后向前扫描
3.  如果已排序的元素大于新元素，将其移到下一位置
4.  重复步骤3，直至找到已排序的元素小于或者等于新元素的位置
5.  将新元素插入
6.  重复步骤2-5

## 3.算法复杂度 ##

时间复杂度：如果将n个元素升序排列，最好的情况是已经升序，这种情况下，只需要进行(n-1)此比较即可；最坏的情况是降序排列，此时需要比较n(n-1)/2次。平均时间复杂度为o(n^2)。

空间复杂度：o(1)

稳定性：在插入过程中，如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，是稳定的。

void InsertSort(int* arr, size_t size)
    {
    	if (NULL == arr || size == 1)
    		return;
    	for (size_t i = 1; i < size; i++)
    	{
    		int key = arr[i];
    		int end = i - 1;
    		while (key < arr[end] && end >= 0)
    		{
    			arr[end + 1] = arr[end];
    			end--;
    		}
    		arr[end + 1] = key;
    	}
    }

在插入数据过程中，比较次数可能会比较多，我们可以将直接查找的方改为折半查找，即可得到折半插入排序算法，相比于直接插入排序，有一定的优化。

void InsertSort_B(int* arr, size_t size)
    {
    	if (NULL == arr || size == 1)
    		return;
    	for (size_t i = 1; i < size; i++)
    	{
    		int key = arr[i];
    		int left = 0;
    		int right = i - 1;
    		int end = i - 1;
    		while (left <= right)
    		{
    			int mid = left + ((right - left) >> 1);
    			if (key < arr[mid])
    				right = mid - 1;
    			else
    				left = mid + 1;
    		}
    		while (left <= end)
    		{
    			arr[end + 1] = arr[end];
    			end--;
    		}
    		arr[end + 1] = key;
    	}
    }

# 二、希尔排序 #

## 1.算法思想 ##

希尔排序又称缩小增量法，是直接插入排序的一种改进。其基本思想是：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量 dt=1，即所有记录放在同一组中进行直接插入排序为止。

该方法实质上是一种分组插入的方法。

## 2.具体步骤 ##

假设有10个记录，其关键字分别是：7,5,3,1,9,4,6,2,0,8；取增量依次为3,2,1

![20180225191531175][]

## 3.算法分析 ##

希尔排序不需要大量的辅助空间，容易实现。相比于插入排序，效率上有所提高，其时间复杂度也有增量的选取有关。希尔排序没有快速排序快，对于规模非常大的数据排序不是最优的选择；但是希尔排序在最坏的情况下和平均情况下执行效率相差不是很大，快速排序则相差较大，因此，几乎任何排序工作在开始时都可以用希尔排序，若在实际中证明它不够快，再改成快速排序。此外，希尔排序是不稳定的。

void ShellSort(int* arr, size_t size)
    {
    	int gap = size;
    	while (gap > 1)
    	{
    		gap = gap / 4 + 1;
    		for (size_t i = gap; i < size; i++)
    		{
    			int key = arr[i];
    			int end = i - gap;
    			while (key < arr[end] && end >= 0)
    			{
    				arr[end + gap] = arr[end];
    				end -= gap;
    			}
    			arr[end + gap] = key;
    		}
    	}
    }

[20180225191531175]: /images/20220531/2ff1cf645d294129bef62fa43184c7df.png