直接插入排序/希尔排序

八大排序：直接插入排序，希尔排序，冒泡排序，选择排序，堆排序，二路归并排序，快速排序，基数排序。

我们这篇文章主要讲直接插入排序和希尔排序，其实懂了直接插入排序，希尔排序也就懂了，所以先来说直接插入排序。

直接插入排序（可以想象成我们打牌时接扑克牌一样）。

我们先给出原始数据：12,2,9,8,18,7。

加下划线是已经排序好的（有序队列），没加是未排序的，第一趟排序可以省略。

调整规则：将待插入的值（也就是有序队列最后一位的下一位）和有序队列的所有值挨个比较（从右到左），找到一个小于或者等于自己的值，则停止下来，插入到当前位置的下一个位置，到底了也停下来。

代码如下：

//直接插入排序  时间复杂度O（n^2）  空间复杂度O（1）   稳定性：稳定的
void InsertSort(int *arr, int len)
{
	//assert arr!=NULL

	for(int i=1; i<len; i++)//一共跑了多少趟  //01234   12345  
	{
		int tmp = arr[i];//待插入的值  
		//j 指向 这一趟开始的时候的已排序好的队列中最后一个值的下标
		int j;
		for(j=i-1; j>=0; j--)//这里控制待插入的值和 已排序队列的挨着比较（从右向左比较）
		{
			if(arr[j] <= tmp)
			{
				break;//这时应该停下来
			}
			else
			{
				arr[j+1] = arr[j];
			}
		}
		arr[j+1] = tmp;//插入到当前位置的下一个位置
	}

}

希尔排序：（对直接插入排序的优化）

 d=5时，48和13用直接插入排序比较，38和27用直接插入排序比较，依此类推，得到一趟排序的结果，d=3时，13,53,38,76用直接插入排序比较，27,04,65也同样。最后d只能等于1，再总体用直接插入排序比较一次。

代码如下：

void Shell(int arr[], int len, int gap)//一趟希尔排序
{
	for(int i=gap; i<len; i++)//i++  不是i=i+gap;
	{
		int tmp = arr[i];//待插入的值  
		//j 指向 这一趟开始的时候的已排序好的队列中最后一个值的下标
		int j;
		for(j=i-gap; j>=0; j=j-gap)//这里控制待插入的值和 已排序队列的挨着比较（从右向左比较）
		{
			if(arr[j] <= tmp)
			{
				break;//这时应该停下来
			}
			else
			{
				arr[j+gap] = arr[j];
			}
		}
		arr[j+gap] = tmp;
	}
}

//希尔排序：不稳定   时间复杂度O（n^1.3 ~ 1.7）  空间复杂度O（1）
void ShellSort(int arr[], int len)
{
	int gap[] = {5, 3, 1};//
	int gap_len = sizeof(gap)/sizeof(gap[0]); 
	for(int i=0; i<gap_len; i++)
	{
		Shell(arr, len, gap[i]);
	}
}