[数据结构] 基于插入的排序 插入排序&希尔排序

标题：[数据结构] 排序#插入排序&希尔排序

@水墨不写bug

---

---

目录

（一）插入排序

实现思路：

插入排序实现： 

（二）希尔排序

希尔排序的基本思想： 

希尔排序的实现：

---

正文开始：

        排序是日常生活中常见的对数据的需求，排序有多重不同的方法，每一种方法都有各自的优缺点，本文来为你介绍两个思路类似的排序方法：插入排序和希尔排序。

（一）插入排序

       

        时间复杂度：O（N^2）

        空间复杂度：O（1）

        特点：元素越接近有序，插入排序的效率越高。

        稳定性：稳定

实现思路：

主要过程： 

        对于区间一个有序区间 [0,end] 将区间后的一个元素 nums[end+1] 插入到有序区间内。

由于nums[end+1]在移动元素时会被覆盖，需要一个临时变量tem暂时存储 nums[end+1]，具体来说，将tem与nums[end]进行比较，如果

tem < nums[end]

则将end处的数据后移：

nums[end+1] = nums[end]

并将end--，继续比较。

如果

tem>=nums[end]

说明已经到达要插入的位置，直接break。

在出循环之后，将tem插入正确的位置即可:

nums[end+gap] = tem

整体实现注意事项：

        1.在实现过程中，可以先写内层循环，完成内层逻辑，再写外层循环。

        2.对于内层循环，进行循环的条件是 end>=0 ,由于外层循环end从0开始，如果内层进行循环的条件是end>0,那么如果end = 0，就无法进入循环。

        3.如何确定外层循环的区间？

        左区间从零开始；对于最大的区间，由于要将最后一个元素（size-1位置）插入到前面的区间 [0,size-2]内，所以end最大可取  size-2 。

        则区间为：

                [0,size-2](两闭区间)或者[0,size-1)(左闭右开区间)。

插入排序实现： 

#include<iostream>
#include<vector>
using namespace std;
 
void InsertSort(vector<int>& nums)
{
    //外层循环，end从0开始遍历
	for (int i = 0; i < nums.size()-1; i++)
	{
		//[0,end] end+1
		int end = i;
		int tem = nums[end + 1];
		//内层循环，end>=0时要进入循环
        while (end >= 0)
		{
			if (nums[end] > tem)
			{
				nums[end + 1] = nums[end];
				--end;
			}
			else
				break;
		}
		nums[end + 1] = tem;
	}
}
void Print(vector<int> v)
{
	for (const auto& e : v)
		cout << e << " ";
	cout << endl;
}
int main()
{
	vector<int> nums = { 55,9,8,6,7,59,75,89,12,50 };
	Print(nums);
 
	InsertSort(nums);
	Print(nums);
	return 0;
}

---

（二）希尔排序

        希尔排序简单来说就是对插入排序的优化，它与插入排序的整体思路是一致的。想要写好希尔排序，就必须要讲究一个层次感，你需要明白希尔排序的几层循环到底是在干什么。

---

希尔排序的基本思想： 

分组：

        将数组中间距为gap的数据分为一组，如图所示：（gap == 3）

可以将一组数据分为gap组：

        我们将每一组数据看做是一个小组（group），对于每一个小组，想要将他们排序，自然需要移动，由于小组内部数据相距gap，所以移动的步幅也是gap。

希尔第一层次：

        也就是插入排序内层循环的逻辑，唯一不同的是将步幅从1改为gap。

实现的操作：

        将一个数据 nums[end+gap] 插入到已经有序的区间 [0,end] 内部，并在插入后使整个区间保持有序。

        由于nums[end+gap]在移动元素时会被覆盖，需要一个临时变量tem暂时存储 nums[end+gap]，具体来说，将tem与nums[end]进行比较，如果

tem < nums[end]

则将end处的数据后移：

nums[end+gap] = nums[end]

并将end-=gap，继续比较。

如果

tem>=nums[end]

说明已经到达要插入的位置，直接break。

在出循环之后，将tem插入正确的位置即可:

nums[end+gap] = tem

实现参考：

int end;
int tem = nums[end + gap];
while (end >= 0)
{
	if (tem < nums[end])
	{
		nums[end + gap] = nums[end];
		end -= gap;
	}
	else
		break;
}
nums[end + gap] = tem;

 希尔第二层次：

        也就是插入排序外层循环的逻辑。

实现的操作：

        由于随着插入的进行，区间不断扩大，第二层次作用是不断改变区间的右端，和定位并保存需要插入的元素 nums[end+gap] 。

实现参考：

for (int i = 0; i < n - gap; i += gap)
{
	int end = i;
	int tem = nums[end + gap];
	while (end >= 0)
	{
		if (tem < nums[end])
		{
			nums[end + gap] = nums[end];
			end -= gap;
		}
		else
			break;
	}
	nums[end + gap] = tem;
}

希尔第三层次：

        前两层次实现了对一个group的排序，第三层就是要实现对所有group的排序。

实现的操作：

        外层创造循环变量j，对区间起点 i 制造偏移量：

for (int j = 0; j < gap; j++)
{
	for (int i = j; i < n - gap; i += gap)
	{
		int end = i;
		int tem = nums[end + gap];
		while (end >= 0)
		{
			if (tem < nums[end])
			{
				nums[end + gap] = nums[end];
				end -= gap;
			}
			else
				break;
		}
		nums[end + gap] = tem;
	}
}

 希尔第四层次：

        前三层次完成了对某一特定gap下的预排序。第四层次就是要通过gap来逐渐让数组接近有序。

        gap的意义是让数据跳动的步幅增大，不同的大小的gap拥有不同的效果：

        如果gap较大，数据跳动的步幅更大，数据的移动更快，但是更不容易接近有序。

        对于较小的gap，数据步幅减小，数据移动的较慢，但是更容易接近有序；当gap取可取得的最小值1时，整个排序逻辑就会退化为插入排序。

实现的操作：

        通过特定的策略逐渐减小gap。

        经过研究，gap每次除三效果最好，但是为了避免gap小于1，于是在每次除三后再加上1，这样就是一种gap的取值策略。

 
void ShellSort(vector<int>& nums)
{
	int n = nums.size();
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
        //....
	}
}

希尔排序的实现：

 
void ShellSort(vector<int>& nums)
{
	int n = nums.size();
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int j = 0; j < gap; j++)
		{
			for (int i = j; i < n - gap; i += gap)
			{
				int end = i;
				int tem = nums[end + gap];
				while (end >= 0)
				{
					if (tem < nums[end])
					{
						nums[end + gap] = nums[end];
						end -= gap;
					}
					else
						break;
				}
				nums[end + gap] = tem;
			}
		}
	}
}

---

完~

未经作者同意禁止转载