选择、插入、希尔排序及其分析

说明

• 本文当中的所有排序算法均以类的形式给出，这个类当中还定义了两个基础函数 less 和 exch ，前者用于判断两个数是否满足小于的关系，后者用于交换两个数

• 我们所有的算法的讨论基础为升序排列

• 在研究排序算法的成本时，对于会交换元素的算法，我们关注的是比较次数和交换次数，对于不交换元素的算法，我们关注的是数组的访问次数

​

选择排序

选择排序可以说是排序里面最朴素的一种想法了，它的基本思想如下：

选择数组当中最小的元素，将它与第一个元素交换。然后，在剩下的元素当中找到最小的，将它与第二个元素进行交换。如此这般，我们便可以将整个数组进行排序

代码如下：

class Selection
{
public:
	static bool less(int v, int w)
	{
		return v < w;
	}

	static void exch(vector<int>& a, int i, int j)
	{
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}

	static void sort(vector<int>& a)
	{
		int N = a.size();
		for (int i = 0; i < N; i++)
		{
			int min = i;
			for (int j = i + 1; j < N; j++)
				if (less(a[j], a[min]))
					min = j;
			exch(a, i, min);
		}
	}
};

​

分析

数组一共有 \(N\) 个元素，对于第 \(i\) 个元素而言，它需要一次交换和 \(N-1-i\) 次比较（内层循环从 \(i+1\) 开始遍历并且一共有 \(N\) 个数）

因此对于长度为 \(N\) 的数组，会有 \(N\) 次交换和 \((N-1)+(N-2)+\cdots+1=N(N-1)/2\ \sim\ N^2/2\) 次比较

​

插入排序

对于数组当中的任意一个元素 i ，它前面的元素是有序的。如果我需要让有序的范围扩大到 i ，那么我们需要将元素 i 插入到前面的 i-1 个元素中的适当位置。为了实现这种插入，我们需要将部分元素向右移动一位（准确来说是比 i 大的元素全部移动一位）

class Insertion
{
public:
	static bool less(int v, int w)
	{
		return v < w;
	}

	static void exch(vector<int>& a, int i, int j)
	{
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}

	static void sort(vector<int>& a)
	{
		int N = a.size();
		for (int i = 1; i < N; i++)//一开始从 1 开始
		{
			for (int j = i; j >= 0 && less(a[j], a[j - 1]); j--)
				exch(a, j, j - 1);
		}
	}
};

​

分析

由于比较是放在了 for 循环的判断部分，因此在最好的情况下，只需要 \(N-1\) 次比较和 \(0\) 次交换

由于每一次移动都会对应一次比较（反过来不行，后面会说明），因此在最坏的情况下需要 \(\sim N^2/2\) 次比较和 \(\sim N^2/2\) 次交换（这里的推导和上面一样，只不过对象是交换的次数，然后再从移动次数得出比较次数）

对于 \(N\) 个元素的数组，比较的总次数是交换次数加上一个额外的项，该项为 \(N\) 减去待插入元素正好是「当前已知最小元素的次数」。在最坏情况下（完全逆序），这一项为 0 ；在最好情况下（数组本身排好序），这一项为 \(N-1\)

我们解释一下什么叫「当前已知最小元素的次数」

我们知道一次交换必然对应一次比较，这里很容易理解

那我们思考一个问题，对于那些只需要比较而不需要交换的项，是什么情况

通过观察可以发现，如果想要进入内层循环，那么当前元素一定要小于前一个元素。反过来说，如果当前元素不是目前已知的最小元素，那么就只有比较的成本而没有交换的成本。那么，我们通过用 \(N\) 减去「待插入元素为当前已知最小元素的次数」，得到的就是所有只需要比较而不需要交换的成本

我们还有另外一种描述插入排序成本的方法

我们定义倒置指的是数组当中两个顺序颠倒的元素。那么插入排序的交换次数跟倒置的个数相同，比较次数大于等于倒置的数量，小于等于倒置的数量加上数组大小再减去 1 （这里的推导与上面的一致，不过多说明）

​

希尔排序

我们看到，在插入排序中，它只会比较相邻元素，因此元素只能一点点地移动，这种速度非常慢，那么有没有一种可以让元素可以快速移动的办法呢？

这便有了希尔排序

该算法的思想是使数组当中任意间隔为 \(h\) 的元素都是有序的，这样的数组被称为 \(h\) 有序数组。当 \(h\) 很大的时候，便可以实现将一个数快速移动使得它接近最终应该在的位置

我们通过不断减小 \(h\) 的大小，便可以使得数组逐渐变为有序

具体的，对于一个 \(N\) 个元素的数组，我们让 \(h\) 的大小从 \(N/3\) 不断减小到 1 （当然也可以用别的）

class Insertion
{
public:
	static bool less(int v, int w)
	{
		return v < w;
	}

	static void exch(vector<int>& a, int i, int j)
	{
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}

	static void sort(vector<int>& a)
	{
		int N = a.size();
		int h = 1;
		while (h < N / 3)
			h = 3 * h + 1;//1, 4, 13, 40, 121, 364, 1093
		while (h >= 1)
		{
			for (int i = 1; i < N; i++)
			{
				for (int j = i; j >= h && less(a[j], a[j - h]); j -= h)
					exch(a, j, j - h);//j必须大于等于h，不然会数组越界
			}
			h = h / 3;//h不断减小
		}
	}
};

​

分析

关于该算法的分析，目前并无法准确的给出其时间复杂度的数值，但可以确定的是一定比 \(N^2\) 小

其实对于中等大小的数组，希尔排序的时间是可以接受的，它还不需要额外的运行空间而且代码量很小。其实还有很多比希尔排序更快的算法，在 \(N\) 很大的时候，它们的速度也只可能会比希尔排序快两倍（有时还不一定能达到），并且那些算法还更复杂

总的来说，它的时间是可以接受的并且代码量也小，所有可以使用