高攀不起的希尔排序，直接插入排序

因为期末考试断更了这么久不好意思，从今天起平均每天输出一篇高质量文章供大家享用！！！

First：

直接插入排序：InsertSort

整体思想： 

完整代码实现：

//直接插入排序
void InsertSort(int* arr, int len)
{
	for (int i = 0; i < len - 1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)
		{
			if (tmp < arr[end])
			{
				arr[end + 1] = arr[end];
				--end;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}
void PrintSort(int* arr, int len)
{
	for (int i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}
}
int main()
{
	int arr[] = { 3,1,2,4,9,5,6};
	int len = sizeof(arr) / sizeof(arr[0]);
	InsertSort(arr, len);	
	PrintSort(arr, len);
}

下面介绍的是曾经你对他爱答不理，现在你高攀不起的希尔排序

希尔排序是对直接插入排序的优化

整体思想：

 1、预排序---将数据变成快要排序好的数据  

步骤：先分小组gap，然后再进行排序

 当gap到达1的时候就排序好了

是不是很神奇

总结希尔排序特点： 

 完整代码实现：
 

//希尔排序
void ShellSort(int* arr, int len)
{
	int gap = len;
	while (gap > 1)
	{
		gap = gap / 3 + 1;//保证最后一个数是1
		for (int i = 0; i < len - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (tmp < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
}
void PrintSort(int* arr, int len)
{
	for (int i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}
}
int main()
{
	int arr[] = { 3,1,2,4,9,5,6};
	int len = sizeof(arr) / sizeof(arr[0]);
	ShellSort(arr, len);	
	PrintSort(arr, len);
}

小伙伴们快点上机操作一下吧！！！

如有错误，请多多指教！