一，插入排序及其种类

二，直接插入排序

将未排序的元素与已排序的元素一一比较，来确定插入位置。

#include<iostream>
using namespace std;

void InsertSort(int arry[], int size)  //直接插入排序，size表示数组大小 
{
	for(int i=1; i<size; ++i)
	{
		if(arry[i]<arry[i-1])  //当前数据小于前一个数据 
		{
		    int j = i;
		    int x = arry[i];
			for(; x<arry[j-1]&&j>0; --j)
			{
				arry[j] = arry[j-1];
			}
			arry[j] = x;
		}
	}
}

int main()
{
	int a[] = {81,94,11,96,12,35,17,95,28,58,41,75,15};
	InsertSort(a,13);
	for(int i=0; i<13; ++i)
	{
		cout << a[i] << " ";
	}
}

三，二分插入排序

与直接插入排序基本相同，只是未排序元素要不断与插入范围的中间元素做比较来确定新的插入范围。

#include<iostream>
using namespace std;

void BInsertSort(int arry[], int size)  //二分插入排序，size表示数组大小 
{
	for(int i=1; i<size; ++i)
	{
		int x = arry[i];
		int high = i-1;
		int low = 0;
		int mid = (high+low)/2;   
		while(high>=low)   //不断确定新的插入范围 
		{
			if(x>arry[mid])
			{
				low = mid+1;
			}
			else
			{
				high = mid-1;
			}
			mid = (high+low)/2;
		}
		for(int j=i; j>=low+1; --j)  //确认插入位置后将该位置及之后的元素后移 
		{
			arry[j] = arry[j-1];
		}
		arry[low] = x; //将元素插入 
	}
}

int main()
{
	int a[] = {81,94,11,96,12,35,17,95,28,58,41,75,15};
	BInsertSort(a,13);
	for(int i=0; i<13; ++i)
	{
		cout << a[i] << " ";
	}
}

四，希尔排序

#include<iostream>
using namespace std;

ShellInsert(int arry[], int dk, int size)
{
	for(int i=dk; i<size; ++i)
	{
		for(int j=i; j<size; j=j+dk) //对间隔为dk的一组数据进行直接插入排序 
		{
			if(arry[j]<arry[j-dk])
			{
				int x = arry[j];
				int p = j;
				for(; x<arry[p-dk]&&p>i-dk; p=p-dk)
				{
					arry[p] = arry[p-dk];
				}
				arry[p] = x;
			}
		}
	}
}

void ShellSort(int arry[], int dk[], int size1, int size2) //希尔排序，size1为数组a的长度，size2为数组dk的长度 
{
	for(int i=0; i<size2; ++i)
	{
		ShellInsert(arry, dk[i], size1);
	}
}

int main()
{
	int b[] = {5,3,1};
	int a[] = {81,94,11,96,12,35,17,95,28,58,41,75,15};
	ShellSort(a,b,13,3);
	for(int i=0; i<13; ++i)
	{
		cout << a[i] << " ";
	}
}