数据结与算法之排序-插入排序（直接插入/折半插入/希尔）

文章目录

1. 目录

   ---

前言

理解三种排序，并将三种排序用C++实现，借鉴了王卓老师和没有难学的知识的图例

提示：以下是本篇文章正文内容，下面案例可供参考

一、什么是插入排序

        插入排序是简单直观的排序方法，其思想是每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列，直到全部记录插入完成。用我的话翻译过来就是：一组数据有一部分是已经排好序的，只需要将混乱的部分按照排列好的大小顺序挨个插入到前面已经排好顺序序列里面，使全部数据按顺序排列。类似与整理扑克牌的大小顺序。

1.直接插入排序

    方法1：默认第一个数是已经排好序的，从第二个数开始，与前一位作比较，找到适合插入的有序位置后，将有序位置及其后面的位置的数值都往后移一位，空出要插入的有序位置，把待排序的的数再复制给该位置即可，往后依次相同做法。

插入位置有以下3种：

 举个例子更好地理解：

 （1）  a数组中，0-3的位置是已经从小到大排好序的，那么从第4个位置开始排，也就是第i位，j是第i位的前一位，用来记录有序位的。

 （2）复制插入元素，将要进行插入排序的数复制给x:

  (3)记录后移，查找插入位置，将7与前一位16相比，7<16,应该在16的前面，16往后移，往前继续找，j-1;

      将7与10相比，7<10,应该在10的前面，16往后移，往前继续找，j-1；

     7和5相比，7>5，所以该在5的后面，所以要插入的有序位是j+1;

 代码如下（示例）：

#include<iostream>
using namespace std;
const int N = 100001;
int arr[N];
int main()
{
	int n = 5;
	int x;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i]; //输入数据
	}
	for (int i = 1; i < n; i++) //除了第一个数不用管，要排n-1次序
	{

		if (arr[i] < arr[i - 1]) //如果待排序数（指：将要进行排序的数，注意连读嗷） 比前一位小，进行后移和插入操作；否则，不变，开始下一位待排数
		{
            int j;
			x = arr[i];  //用一个中间变量来暂时存放待排序数
			for (int j = i - 1; j >= 0 && x < arr[j]; j--) //后移操作：从后位开始往后移，所以从j=i-1开始,依次往前j--
			{
				arr[j + 1] = arr[j];  //后移核心：把前一位的值复制给后一位
			}
			arr[j + 1] = x; //插入
		}
	}
	for (int i = 0; i < n; i++) cout << arr[i] << ' ';
	return 0;
}

这个方法中每次循环都要比较两次条件，运行起来耗时过多，而且每次都要判断下标是否越界，下面的方法可以避免边界问题。

方法2：和方法1差不多，存数据时，从下标为1开始，下标为0的位置作为哨兵，上面第（2）步里的复制转变为：把插入排序的数赋值给哨兵。

（1）将下标为0的位置作为哨兵，当第i位的数小于i-1位的数时，把第i位的数存放在哨兵上

 （2）记录后移，查找插入位置，将哨兵的值与前一位16相比，7<16,应该在16的前面，16往后移，往前继续找，j-1;

     将7与10相比，7<10,应该在10的前面，16往后移，往前继续找，j-1；

 7和5相比，7>5，所以该在5的后面，所以要插入的有序位是j+1;

代码如下（示例）：

#include<iostream>
using namespace std;
const int N = 100001;
int arr[N];
int main()
{
	int n = 12;
	for (int i = 1; i <= n; i++)
		cin>>arr[i];   
	int i, j;
	for ( int i = 2; i <= n; i++)  //第0位的是哨兵位，假设第一位是有序的，从第二位开始比较大小，直到最后一位
	{
		if (arr[i] < arr[i - 1])
		{
			arr[0] = arr[i];      //如果第二位的数比第一位大，就把第二位的数值赋给哨兵位0位
			for (j = i - 1; arr[0]< arr[j]; j--)  //j是要待排序的前一位，当前一位比待排序位的值大，那么j--,继续向前找待排序位的值小的
			{
				arr[j + 1] = arr[j];
			}
			arr[j + 1] = arr[0];  //找到之后，在比待排序位小的那位后面插入待排序位，也就是哨兵位
		}
	}
	for (int i = 1; i <= n; i++)  //输出
		cout << arr[i] << ' ';
	return 0;
}

2.折半插入排序

在已经排好序的部分中去插入待排序的数，有点二分查找那意思，把待插入排序的数和排好序的中间位置的数作比较，就可以在原来一半的范围里继续比较，再缩小一半的范围…直到找到插入的有序位。                                                                                                                                                   （1）从第i位插入，下标为0的是哨兵，低位left是下标位1的位置，高位right是待排序的位前一位i-1，中间位是mid=(left+right)/2=（1+4）/ 2=2,7>mid,7在mid的右半边找插入位置

 （2）此时低位变为left=mid+1=3,中间位相应改变mid=(left+right)/2=(3+4)/2=3,7<mid,7在mid的左半边找插入位置

 （3）此时高位变为right=mid-1=2,left>right，那么7应该在下标为3处，即第right+1位

（4） 找到插入位置后，开始后移步骤，把第right+1位及其后面的位向后移，空出right+1，将哨兵的值给right+1,就这样排到最后一位。

 代码如下（示例）：

#include<iostream>
using namespace std;
const int N = 10010;
int arr[N];
int main()
{
	int n;
	cin >> n; //n个数
	for (int i = 1; i <= n; i++) //输入要排列的数据
		cin>>arr[i];
	
	for (int i=2;i<=n;i++)       //从第2的数开始排列，直到最后一个
	{
		int j;
		arr[0] = arr[i];        //把待排列的数给哨兵位arr[0]
		int left = 1, right = i - 1; //二分的三个位置，左边：第1位，右边待排序前的一位，中间位
		while (left <= right) 
		{
			int mid = (left + right) / 2;   //注意：该语句写while外面的话，while里面将会一直循环
			if (arr[0] <  arr[mid]) left = mid + 1;
			else right = mid - 1;
		}
		//待排序的数最后的位置一定是在right+1上，所以要把right+1这个位置空出来，就要把right+1及其后面的位置上的数据往后移
		for (int j = i - 1; j >= right + 1; j--) 
			arr[j + 1] = arr[j];
		arr[right+1] = arr[0];         //最后将哨兵位置上的数赋值到right+1位置上
	}
	for (int i = 1; i <= n; i++)
		cout << arr[i] << ' ';
	return 0;
	
}

3.希尔排序

        基本思想:先将整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。简言之，缩小增量，多遍插入排序，增量下一次是上一次的一半，增量是来表示分组的数量，最后一次增量必须为1

（1）第一次，以8/2=4为增量grap，分为4组，将7和2  3和0 5和8 9和6这四组分别进行插入排序

（2） 排好后，增量grap变为4/2=2, 分为2和5和7和8、0和6和3和9这两组分别进行插入排序

 （3）排好后，grap=2/2=1,即全部进行插入排序

        最后得到运行代码直接插入逻辑相同，再多一个增量变换的循环，别的几处值与增量有关

代码如下（示例）：

#include<iostream>
using namespace std;
const int N = 10010;
int arr[N];
int main()
{
	int n = 10;
	for (int i = 1; i <= n; i++)
		cin >> arr[i]; //输入10个数
	 
	for (int gap=n/2;gap>0;gap=gap/2)  //增量
	{
		for (int i = gap + 1; i <= n; i++)  //从相隔步长数的作比较 比如：下标1和下标6之间相隔5
		{
			
			if (arr[i] < arr[i - gap])     //第i位比相差增量位的数小的话
			{
				int j;
				arr[0] = arr[i];         //，就把值给哨兵
				for ( j = i - gap; j > 0 && arr[0] < arr[j]; j -= gap)  //这里多一个j>0的条件，保证每次比较都是在边界内的值
					arr[j + gap] = arr[j];  //往后移
				arr[j + gap] = arr[0];      //找到合适的插入有序位就把哨兵的数给第j+dk位
			}
		}
	}
	for (int i = 1; i <= n; i++)
		cout << arr[i]<<' ';      //输出
	return 0;
}

总结

从上可得，插入排序的要点：1.存：把待排序的数暂存到一个新的位置，也可以是哨兵；2.找：找插入位置；3.移：把插入位置及其后面的位置上的数往后移一位 以上就是今天要讲的内容，随后还会更新排序的相关内容，希望可以帮助到你~