[数据结构与算法]插入排序及希尔排序

插入排序：插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法??。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动?。

????????基本思想：插入排序就好比如有一副杂乱的扑克牌，当你抓牌的时候，就是要将相同的摆在一起，并将牌从小到大（从大到小）的顺序排列。

????????核心操作：扑克牌的抓牌顺序就好比一个序列的顺序，插入的过程就好比一个一个比较的过程。

????????例如，原序列为5,2,4,6,1,3，则插入排序的过程如下:

?核心代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	int arr[10001];
	cin>>n;
	for(int i=0;i<n;i++)cin>>arr[i];
	for(int i=0;i<n;i++){//遍历要插入的数字 
		int value=arr[i];//将当前准备插入的数记录下来 
		int j;
		for(j=i;j>=0;j--){//循环从后往前遍历数，看在哪插入 
			if(arr[j-1]>value){//如果前一个数比当前插入的value还大，就继续向前找，一直找到比value小的值 
				arr[j]=arr[j-1];
			}
			else break;//否则结束 
		}
		arr[j]=value;//插入 
	}
	for(int i=0;i<n;i++)cout<<arr[i]<<" ";	
	return 0;
} 

希尔排序：在插入排序中，当数据在最坏的时候，例如我要把5,4,3,2,1从小到大的排序，如果是这样的话，我们计算机的所做的运算量很大，所以，我们把插入排序改进了一下，这就成了希尔排序。

百度百科上是这样描述希尔排序的：

希尔排序是根据插入排序的以下两点性质而提出改进方法的：

1.插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。

2.但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

????????基本思想：引入概念，增量。增量的意思为：如果存在一个语句i=i+1；其中1位增量。这里开始的增量gap一般为n/2,也是分成n/2组，其中j%gap所得到的值相等的成一组。然后每一组进行插排。增量gap每次除以2，重复步骤直置gap为1时结束。

如果觉的很懵，我们来举个栗子：

例如：5,2,4,6,1,3序列，gap=n/2=3。

分组得下图：

组内插入排序接下图：

即得序列5,1,3,6,2,4。

重复步骤，其中gap=gap/2=1；依次分组，然后插排,这里的组数为1，即为一组

即如下图：

然后插排得到序列1,2,3,4,5,6

????????代码：代码其实仅仅只要加上一个for循环来表示gap的变化。这里的分组插排，i可以从gap开始，到n-1，其中i来依次向前减gap来寻找组内元素。

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	int arr[10001];
	cin>>n;
	for(int i=0;i<n;i++)cin>>arr[i];
	for(int gap=n/2;;gap=gap/2){ //依次进行增量的缩减 
		for(int i=gap;i<n;i++){ //遍历要插入的数字 
			int j;
			int value=arr[i];//将当前准备插入的数记录下来
			for(j=i;j-gap>=0;j-=gap){//循环从后往前在组内遍历数，看在哪插入,
				if(arr[j-gap]>value){//如果前一个数比当前插入的value还大，就继续向前找，一直找到比value小的值 
					arr[j]=arr[j-gap]; 
				}
				else break;//否则结束 
			}
			arr[j]=value;//插入 
		}
		if(gap==1)break;
	}
	for(int i=0;i<n;i++)cout<<arr[i]<<" ";	
	return 0;
} 

总结：希尔排序仅仅是优化了插入排序，但是时间复杂度仍然是O()。