插入排序和希尔排序：

插入排序

1. 算法思想：

由数组下标为1 开始的数值作为判断依据，与之前的数据从后往前比较
定义tmp 暂存判断的数值，若前面的数据大于tmp，则将前面的数据向后移动 : arr[j+1]=arr[j]
若对比的数据比tmp 大，则往后移，产生空位
若前面的数据小于判断数据tmp ，则返回break（在有序的基础上，若遇到一个小于tmp 的，则此数据以前都比当前数据小，无判断意义）
在循环外将tmp 放入空位置

2. 代码实现：

//直接插入排序
void InsertSort(int* arr, int len)//快速排序的输入格式
{
	//算法描述：
	//从下标为1 的开始，从后向前找，若前比后大，则交换位置
	for (int i = 1; i < len; i++)
	{
		int tmp = arr[i];
		int j;
		for (j = i - 1; j >= 0; j--)
		{
			if (tmp < arr[j])
			{
				arr[j+1] = arr[j];
			}
			else
				break;
		}
		arr[j + 1] = tmp;
	}
}

3. 插入排序特性：

时间复杂度：O(n*n)
空间复杂度：O(1)
特点：约有序越快—时间复杂度O(n)
具有稳定性

问题引入？为什莫不能从前往后判断

//直接插入排序
void InsertSort(int* arr, int len)//快速排序的输入格式
{
	//for (int i = 1; i < len; i++)
	//{
	//	for (int j = 0; j < i; j++)
	//	{
	//		if(arr[j]>arr[i])
	//		{
	//			int tmp = arr[j];
	//			arr[j] = arr[i];
	//			arr[i] = tmp;
	//		//	break;
	//		}
	//	}
	//}
}

希尔排序：

1. 希尔排序算法思想：

希尔排序是对直接插入排序的优化（由其越有顺序越快的特点！）

将排序数组间隔分组（分组用直接插入排序，组内有序）
缩小分组再次排序,直到组数为1

2. 代码实现：

//这是配置好的模板文件
#include <iostream>
#include <string>
using namespace std; 

void Shell(int* arr, int len, int d)
{
	for (int i = 0; i < len; i++)
	{
		int tmp = arr[i];
		int j;
		for (j = i - d; j >= 0; j -= d)
		{
			if (tmp < arr[j])
			{
				arr[j + d] = arr[j];
			}
			else
				break;
		}
		arr[j + d] = tmp;
	}
}
void Xier(int* arr, int len)
{
	int drr[] = { 5,3,1 };
	int lendrr = (sizeof(drr) / sizeof(drr[0]));
	for (int i = 0; i < lendrr; i++)
	{
		Shell(arr, len, drr[i]);//一趟希尔排序
	}
}
void Show(int* arr, int len)
{
	for (int i = 0; i < len; i++)
	{
		printf("%d  ", arr[i]);
	}
	printf("\n");
}
int main()
{
	int arr[] = { 6,0,1,15,7,8,5,11,20,40,35 };
	Show(arr, sizeof(arr) / sizeof(arr[0]));
	Xier(arr, sizeof(arr) / sizeof(arr[0]));
	Show(arr, sizeof(arr) / sizeof(arr[0]));
	return 0;
}