直接插入排序

原理

每次从待排序队列中取一个值，放到已排序好的队列，再次保持有序，重复这样的动作，直到把待排序队列中的值全部取完。

其实和玩扑克牌一样；
比如你揭的几张牌是顺子，但到底是不是，你要给他们排个序
示例：

第二次揭牌结果：

继续揭牌：

结果：

按照这样的方式，最终结果为：

代码实现(C语言)

void Insert_Sort(int* arr, int len)
{
	assert(arr != NULL);
	int tmp = 0;
	int i = 0, j = 0;

	for (i = 1; i < len; ++i)
	{
		tmp = arr[i];
		for (j = i - 1; j >= 0; --j)
		{
			if (arr[j] > tmp)
			{
				arr[j + 1] = arr[j];
			}
			else
			{
				break;
			}
		}
		arr[j + 1] = tmp;
	}
}

运行示例：

void Show(const int* arr, int len)
{
	assert(arr != NULL);
	for (int i = 0; i < len; ++i)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
int main(void)
{
	int ar[] = { 9,6,5,4,2,3,1,7,8,0 };
	int len = sizeof(ar) / sizeof(ar[0]);
	Show(ar, len);
	Insert_Sort(ar, len);
	Show(ar, len);

	return 0;
}

运行结果：

评价

时间复杂度：O（n^2）
空间复杂度：O（1）
稳定性： 稳定的

适用场景

1. 当问题规模很小时（n很小），则 n^ 2不会很大。
2. 待排序队列越有序，越优解。

希尔排序

原理

希尔排序是D.L.Shell在对直接插入排序改进后的算法。

采取跳跃分割的策略: 将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。 即缩小增量。

增量要求：

1. 增量一般是以{ 5， 3， 1}来分。
2. 一定以一结尾。
3. 尽可能互素。

图示

以五为增量给数据分组

然后每组按照直接插入排序的方法来排序。

第一组：

按照直接插入排序，把13保存到tmp中，往前比较，13比6大，就把tmp放到6后面；再把12保存到tmp中，往前比较，比13小，就把13往后覆盖，再和前面6比较，比6大，则放到6的后面。。。。
这时候数据变成了：

第二组：

原始数据变为：

以此方法，把图示的五组数据进行直接插入排序后，得到的结果为：

以3为增量给数据分组：

也是按照直接插入排序来做：

以此类推，最终数据为：

可以看出，相较于初始数据，经过两次缩小增量排序后，数据变得比较有序了，再执行最后一次，以 1 为增量，就是执行一遍直接插入排序，因为数据比较有序，所以交换次数会少很多。

以1为增量结果：

这样就完全有序了

代码实现（C语言）

static void Shell(int* arr, int len, int gap)
{
	int tmp;
	int i = 0, j = 0;

	for (int i = gap; i < len; i++)//每次从待排序队列中取的值
	{
		tmp = arr[i];//用tmp保存待插入的值
		for (j = i - gap; j >= 0; j = j - gap)//从右向左找不比tmp大的值
		{
			if (arr[j] > tmp)//如果比tmp大  则向右放一格
			{
				arr[j + gap] = arr[j];
			}
			else//如果不比tmp大
			{
				break;
			}
		}

		arr[j + gap] = tmp;
	}
}

void ShellSort(int* arr, int len)
{
	assert(arr != NULL);

	int gap[] = { 5, 3, 1 };
	int lengap = sizeof(gap) / sizeof(gap[0]);
	for (int i = 0; i < lengap; i++)
	{
		Shell(arr, len, gap[i]);//5 3 1
	}
}

示例：

void Show(int* ar, int len)
{
	for (int i = 0; i < len; ++i)
	{
		printf("%d ", ar[i]);
	}
	printf("\n");
}

int main(void)
{
	int ar[] = { 3, 6, 14, 9, 11, 8, 5, 2, 13, 15, 1, 7, 4, 12, 10 };
	int len = sizeof(ar) / sizeof(ar[0]);

	Shell_Sort(ar, len);
	Show(ar, len);

	return 0;
}

运行结果：

评价

1. 希尔排序的时间复杂度为O (N^ 1.3~1.5)。
2. 空间复杂度为 0(1)。
3. 稳定性： 不稳定。