内容来自于《算法》(第4版)

排序成本模型。在研究排序算法时，我们需要计算比较和交换的数量。对于不交换元素的算法，我们会计算访问数组的次数。

排序算法的额外内存开销和运行时间是等同重要的。排序算法可以分为两类，除了函数调用所需的栈和固定数目的实例变量之外无需额外内存的原地排序算法，以及需要额外内存空间来存储另一组数组副本的其他排序算法。

选择排序

一种最简单的算法是这样的，首先，找到数组中最小的那个元素，其次，将它和数组中的第一个元素交换位置（如果第一个元素就是最小元那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，知道将整个数组排序。

对于长度为N的数组，选择排序需要大约N*N/2次比较和N次交换。

选择排序有两个鲜明的特点：

• 运行时间和输入无关。为了找出最小的元素而扫描一遍数组并不能为下一遍扫描提供什么信息。这种性质在某些情况下是缺点，一个已经有序的数组或是主键全部相等的数组和一个元素随机排列的数组所用的排序时间竟然一样长。
• 数据移动是最少的。每次交换都会改变两个数组元素的值，因此选择排序用了N次交换，交换次数和数组的大小是线性关系。

选择排序代码：

    public static void sort(Comparable[] a){
		// 将a[]按升序排列
		int N=a.length;
		for(int i=0;i<N;i++)
		{
			//将a[i]和a[i+1.N]中最小的元素交换
			int min=i;
			for(int j=i+1;j<N;j++)
				if(less(a[j],a[min])) min=j;
			exch(a,i,min);
		}
	}

插入排序

通常人们整理桥牌的方式是一张一张来，将每一张牌插入到其他已经有序的牌中的适当位置。 在计算机的实现中，为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都像右移动一位。这种算法叫做插入排序。

与选择排序一样，当前索引左边的所有元素都是有序的，但是他们的最终位置还不确定，为了给更小的元素腾出位置，它们可能会被移动。但是当索引到达数组的右端时，数组排序就完成了。

与选择排序不同的是，插入排序所需要的时间取决于输入中元素的初始位置。例如，对于一个很大且其中元素已经有序（或者接近有序）的数组进行排序将会比对随机顺序的数组或是逆序数组进行排序快的多。

对于随机排列的长度为N且主键不重复的数组，平均情况下插入排序需要~NN/4次比较以及~NN/4次交换。最坏情况下需要~NN/2次比较和~NN/2次交换。最好情况下需要N-1次比较和0次交换。

插入排序代码：

    public static void sort(Comparable[] a){
		// 将a[]按升序排列
		int N=a.length;
		for(int i=0;i<N;i++)
		{
			//将a[i]插入到a[i-1]、a[i-1]、a[i-3]...之中
			for (int j=i;j>0&&less(a[j],a[j-1]);j--)
				exch(a,j,j-1);
		}
	}

几种部分有序的数组：

• 数组中每个元素距离它的最终位置都不远；
• 一个有序的大数组接一个小数组；
• 数组中只有几个元素的位置不正确

插入排序需要的交换操作和数组中得到倒置的数量相同，需要的比较次数大于等于倒置的数量，小于等于倒置的数量加上数组的大小再减1。

要大幅提高插入排序的速度，可以在内循环中将较大的元素都向右移动而不总是交换两个元素。（这样访问数组的次数就能减半）

    	public static void sort(Comparable[] a){
		// 将a[]按升序排列
		int N=a.length;
		for(int i=1;i<N;i++)
		{
			
			//另一种实现
			Comparable temp=a[i];
			int j=i-1;//i-1即为有序组的最后一个元素
			while(j>=0&&less(temp,a[j])){
				a[j+1]=a[j];
				j--;
			}
			a[j+1]=temp;
			
		}
	}

总的来说，插入排序对于部分有序的数组十分高效，也很适合小规模数组。

对于随机排序的无重复主键的数组，插入排序和选择排序的运行时间是平方级别的，两者之比应该是一个较小的常数。