@插入排序

• 1 排序的概念

• 2 插入排序

• 2.1 直接插入排序

• 2.2 希尔排序

排序

排序是一种非常重要的基础算法，在校招和工作中都非常的实用，它在日常生活中无处不在。本章将介绍八大基本排序。

1 排序的概念

所谓排序，就是将一串记录按照某种递增递减的关系，使该记录成为一个有序的序列。常见并实用的排序有如下八种。

//直接插排
void InsertSort(int* a, int n);
//希尔排序
void ShellSort(int* a, int n);
//直接选排
void SelectSort(int* a, int n);
//堆排序
void HeapSort(int* a, int n);
//冒泡排序
void BubbleSort(int* a, int n)
//快速排序
void QuickSort(int* a, int left, int right)
//归并排序 
void MergeSort(int* a, int n)
//计数排序
void CountSort(int* a, int n)

2 插入排序

2.1 直接插入排序

基本思想

直接插入排序是最简单的插入排序，例如摸扑克牌时，需要将摸到手的牌按照一定的顺序插入到已有的牌中，这里便是运用了直接插排的思想。

插入排序的定义：把待排的元素按规则逐个插入到一个有序序列中，直到所有元素插完为止，得到一个新的有序序列。

代码实现

首先有一个有序数组，此外有一个元素待插入到该数组中，这样只要不满足比较条件就将下标所指元素向后移动一位，直到满足比较条件或下标越界出数组时退出循环，将待插元素插入下标的下一个位置。

//1. 单趟排序 -- 针对一个元素的排序
void InsertSort(int* a, int n) {
	int end;
	int x;
	while (end >= 0) {
		if (a[end] > x) {
			a[end + 1] = a[end];
			end--;
		}
		else {
			break;
		}
	}
	a[end + 1] = x;
}

单趟排序“只能将一个元素有序”，即将  插入到  的有序区间。

排序是要将所有元素都按顺序排序，而想实现这样的排序，只能一个一个元素排。所以排序一般分为内外两层循环，内循环调整元素位置，而外循环决定调整哪个元素。

1. 首先将数组看成仅有一个元素的数组也就是第一个元素，然后将这样一个数组的尾部元素  的下一个元素看成待调整的元素  ，再将待调整的元素运用上述代码“插入”到数组中，这样便排完了头两个元素。
2. 将数组尾部的下标  向后挪一位，仍将其后的一个元素视为待调整的元素  再插入一次，这样就完成了第二趟排序。
3. 以此类推，直到标识数组尾部的下标  指向倒数第1个元素，也就完成了整个数组的排序。

故只要加一个外循环，控制标识数组尾部的下标  遍历区间为  ，这样便能完成对整个数组的排序。

void InsertSort(int* a, int n) {
	assert(a);
    //外循环 - 多趟排序
	for (int i = 0; i < n - 1; i++) {
		int end = i;
		int x = a[end + 1];
        //内循环 - 单趟排序
		while (end >= 0) {
			if (a[end] > x) {
				a[end + 1] = a[end];
				end--;
			}
			else {
				break;
			}
		}
		a[end + 1] = x;
	}
}

所以插入排序即每次将  插入数组头到标识数组尾部下标  所在区间  并完成排序。

将问题分解，可以更简单快速地解决问题。

复杂度分析

最好情况即数组顺序有序或接近有序但仍需遍历一边，时间复杂度为 ，最坏情况为数组逆序所有元素都要调整，时间复杂度为 。

外循环循环  次，内循环次数从1开始逐次增加，则循环次数为等差数列之和  ，故时间复杂度为  。

开辟空间常数次，故空间复杂度为  。

直接插排对于数组接近有序的情况显得非常的快，而在数组完全逆序的情况下显得非常慢。

2.2 希尔排序

直接插排在接近有序时效率极高，但其他情况下的表现却不尽人意，故Shell想出希尔排序来优化直接插排。在直接插排的前面进行预排序使其性能得到质的飞跃。Shell在计算机中和Linus一样是个流芳百世的名字。

分组预排序

思想上对直接插排进行优化，既然直接插入排序在数组接近有序的情况下效率极高，那就让数组先预排序，使其变得接近有序再去直接插排。这就有点递归分治的思想，这预排序里面就包含了希尔伟大的思想。

1. 按 gap分组，对分组值进行插入排序；

假设gap为3，则每三个元素分成一组，将一组的元素看出一个数组，忽略原本数组中的其他元素。

4,5,2,0为一组，3,1,8为一组，6,7,9为一组。gap的值同时也是组的个数。

2. 对分出的gap组进行插入排序。

将每个所分的组看出一个数组，对每一个这样的数组进行直接插排，过程如图所示：

预排序所得结果虽不是完全有序，但相对于原数组确实是更加有序的。

• 由于直接插入排序对逆序数组的效果差，但若加上预排序的话效果相较于直接插排会非常好。
• 对于预排序来说， gap越大，效果越差，但时间消耗越小；而 gap越小，效果越好，但时间消耗就越大。

代码实现

void ShellSort(int* a, int n) {
	assert(a);
	int gap = n;
    //多次预排一次插排
	while (gap > 1) {
		gap /= 2;
		//排多组
		for (int j = 0; j < gap; j++) {
			//多趟排序
			for (int i = j; i < n - gap; i += gap) {
				int end = i;
				int x = a[end + gap];
				//单趟排序
				while (end >= 0) {
					if (a[end] > x) {
						a[end + gap] = a[end];
						end -= gap;
					}
					else {
						break;
					}
				}
				a[end + gap] = x;
			}
		}
	}
}

1. 首先完成一组的排序，此时就是将直接插排中所谓的下一个元素改成下“gap”个元素，对于边界的控制仍然满足 最大为倒数第二个元素的条件。
2. 外围再套一层循环，控制排序的起始位置 i，也就是控制了多组的排序。
3. 外围再套一层循环，控制 gap不断减小到1，执行多次预排序，最后gap=1时执行直接插排。

由于直接插排的复杂度特点，可能逐步减小的希排复杂度比一次直接插排的复杂度更低。

代码简化

void ShellSort1(int* a, int n) {
	assert(a);
	int gap = n;
	while (gap > 1) {
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++) {
			int end = i;
			int x = a[end + gap];
			while (end >= 0) {
				if (a[end] > x) {
					a[end + gap] = a[end];
					end -= gap;
				}
				else {
					break;
				}
			}
			a[end + gap] = x;
		}
	}
}

简化了控制多组的循环，仅用i控制下标end。从原来的一组一组排，变成了多组一起排，先排第一组的第一对元素，再排第二组的第一对，第三组的第一对；第一组的第二对，第二组的第二对，第三组的第二对，……，直到排完。

复杂度分析

希排的时间复杂度分析较为复杂，下面简单推理一下。实现间距为gap的多组预排，最好情况下仅遍历一遍数组，时间复杂度为 。

组内插排的复杂度

最坏情况下的复杂度分析较为复杂，简单推理一下：假设数组有  个元素分成  组，则每组大概有  个元素。每组的插入排序的复杂度大概为  ，总共gap组复杂度大概为  。

对于预排序来说，gap越大，效果越差，但时间消耗越小；而gap越小，效果越好，但时间消耗就越大，所以执行多次预排更合理。

多组预排的复杂度

在该循环中gap从n开始不停的除2最终到1，这个过程最外层控制预排次数的循环，大概要走  次，每次gap/=3时，大概预排  次。

而每次预排中的插入排序部分的gap不停的变化，导致复杂度较难计算，只能说约等于  ，大概为  。

虽然希尔排序用的都是直接插入排序，但希尔排序的精髓在于其思想非常的难得，这使得排序的复杂度得到质的优化。