6.插入排序.md

插入排序

实验简介

学习了前面一章的查找，我们知道二分查找需要先对数据进行排序，那么这章开始我们就来讲解一下几种经典的排序算法。

一、直接插入排序

首先我们来讲直接插入排序，它的做法是：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程，如下图所示。

直接插入排序的代码实现：

#include <stdio.h>
#include <stdlib.h>

int n;

/*
 * 直接插入排序
 */
void InsertSort(int *array)
{
	int i, j;
	for (i = 2; i <= n; i++)
	{
		if (array[i] < array[i - 1])
		{
			array[0] = array[i];
			array[i] = array[i - 1];
			for (j = i - 2; array[0] < array[j]; j--)
			{
				array[j + 1] = array[j];
			}
			array[j + 1] = array[0];
		}
	}
}

int main()
{
	int i;
	int *array;
	printf("请输入数组的大小：");
	scanf("%d", &n);
	array = (int*) malloc(sizeof(int) * (n + 1));
	printf("请输入数据（用空格分隔）：");
	for (i = 1; i <= n; i++)
	{
		scanf("%d", &array[i]);
	}
	InsertSort(array);
	printf("排序后为：");
	for (i = 1; i <= n; i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");
}

二、希尔排序

希尔排序也是插入排序的一种，但它在效率上要比上面的直接插入排序高，它是对直接插入排序的改进，它的基本思想是先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2< d1重复上述的分组和排序，直至所取的增量dt=1(dt<…< d2< d1)，即所有记录放在同一组中进行直接插入排序为止，增量序列尤为关键，一般的初次取序列的一半为增量，以后每次减半，直到增量为1，大致过程如下图所示。

希尔排序的代码实现：

#include <stdio.h>
#include <stdlib.h>

int n;

/*
 * 希尔排序
 */
void ShellSort(int *array)
{
	int k = n / 2; //增量序列（仅作举例）
	while (k > 0)
	{
		int i, j;
		for (i = k + 1; i <=n; i++)
		{
			if (array[i] < array[i - k])
			{
				array[0] = array[i];
				for (j = i - k; j > 0 && array[0] < array[j]; j -= k)
				{
					array[j + k] = array[j];
				}
				array[j + k] = array[0];
			}
		}
		k = k / 2;
	}
}

int main()
{
	int i;
	int *array;
	printf("请输入数组的大小：");
	scanf("%d", &n);
	array = (int*) malloc(sizeof(int) * (n + 1));
	printf("请输入数据（用空格分隔）：");
	for (i = 1; i <= n; i++)
	{
		scanf("%d", &array[i]);
	}
	ShellSort(array);
	printf("排序后为：");
	for (i = 1; i <= n; i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");
}

三、小结

这一章讲了插入排序中的两个经典算法，直接插入排序和希尔排序。直接插入排序的主要思想是每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序，它属于稳定的排序，最坏时间复杂性为O(n^2)，空间复杂度为O(1)。希尔排序的主要思想是分组插入，它是不稳定的排序，它的时间复杂度跟增量序列有关，在取增量序列时要保证其中的值没有除1之外的公因子，并且最后一个增量值必为1。

作业

结合这章讲的插入排序实现二分查找。

实验中有任何问题欢迎到实验楼问答提问。