选择排序

首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此以往，直到 将整个数组排序。

性能：算法的时间效率取决于比较的次数。对于长度为N的数组，选择排序需要大约N²/2次比较和N次交换。

特点：1.运行时间和输入无关：比如即使输入一个有序的数列，还是会和随机数列一样，进行比较、交换处理。

           2.数据移动是最少的：共N次交换，即交换次数和数组大小是线性关系。其他任何算法都不具备这个特征，大部分都是线性对数或是平方级别的。

函数实现如下：

public class Selection {	public static void sort(Comparable[] a) {		//将a[]按升序排列		int N=a.length;		for(int i=0;i

插入排序

就像通常人们整理桥牌的方法一样，一张一张来，将每一张牌插入到其他已经有序的牌中的适当的位置。

在计算机中的实现中，为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。这种算法叫做插入排序。

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

性能（长度为N且主键不重复）：平均情况——N²/4次比较和N²/4次交换

                                                    最坏情况——N²/2次比较和N²/2次交换

                                                    最好情况——N-1次比较和0次交换

函数实现如下：

public class Insertion {	public static void sort(Comparable[] a) {		//将a[]按升序排列		int N=a.length;		for(int i=0;i
    
     0&&less(a[j],a[j-1]);j--)			exch(a,i,j-1);		}	}}
    

因为是从头至尾循环每个元素，所以当循环到某个元素（设为a）时，它左边已经是有序数列，右边是无序数列，只需将a元素依次向右和每个元素比较，当找到它大于某个元素（设为b）时，只需将a插入到b之后即可。

部分有序：如果数组中倒置的数量小于数组大小的某个倍数，那么我们说这个数组是部分有序的。

插入排序对部分有序的数组很有效，而选择排序不然（因速度与输入无关）。

插入排序的改进：希尔排序

对于大规模乱序数组插入排序慢，因为他只会交换相邻的元素（见插入排序实现代码），因此元素只能一点一点地从数组的一段移动到另一端。例如，如果主键最小的元素正好在数组的尽头，要将它挪到正确的位置就需要N-1次移动。希尔排序为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。

希尔排序的思想是使数组中任意间隔为h的元素都是有序对的。这样的数组被称为h有序数组。

在这里在实现时，先将h具体化为一个h序列，如：1,4,13，40,121,364，1093...

实现：我们先将随机数列变成364（假设此序列最大h可取364）有序数列，实现数组中间隔为364的元素都是有序对；再将数列变成121有序数列；……直到h变为1，实现我们所求的有序数列。

通过这种方式，对于任意以1为结尾的h序列，我们都能将数组排序，这就是希尔排序。

函数实现如下：

public class Shell {	public static void sort(Comparable[] a) {		//将a[]按升序排列		int N=a.length;		int h=1;		while(h
    
     1) {//每次循环都将数组变为h有序数组			for(int i=h;i
     
      =h&&less(a[j],a[j-h]);j-=h;)					exch(a,j,j-h);			}			h=h/3;		}	}}
     
    

性能：希尔排序的性能很难论证，但是仅针对上述代码的性能，在最坏的情况下，它的比较次数和N（3/2）次方成正比。由插入排序到希尔排序，一个小小的改变，就突破了平方级别的运行屏障。

对于中等大小的数组希尔排序的运行时间是可以接受的，它的代码量很小，且不需要使用额外的内存空间。之后我们学习的更加高效的算法，但除了对于很大的N，他们可能只会比希尔排序快两倍，而且更复杂。