# 初级排序

初级算法虽然很简单，但是有三点好处：

可以通过初级算法熟悉排序算法的一些术语。
这些简单的算法在某些情况下会比复杂的算法更有效。
学习初级算法有助于帮助我们改进复杂算法的效率。

# 排序类算法模板

public class Example{
    public static void sort(Comparable[] a){}
    private static boolean less(Comparable v,Comparable w){
        return v.comparaTo(w) < 0;
    }
    private static void exch(Comparable[] a,int i,int j){
        // 交换数组元素
        comparable t=a[i]; 
        a[i]=a[j]; a
        [j]=t;    
    }
    private static void show(Comparable[] a){
        // 在单行中打印数组
        for(int i=0;i < a.length;i++){
            stdOut.print(a[i]+" ");
            stdOut.println();
        }
    }
    public static boolean isSorted(Comparable[] a){
        //测试数组元素是否有序
        for(int i=1;i < a.length;i++){
            if(less(a[i],a[i-1])) return false;
            return true;
        }
    }
    public static void main(String[] args){
        //从标准输入读取字符串，将它们排序并输出
        String[] a=In.readStrings();
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

# 选择排序

选择排序的基本思想如下：

找到数组中最小的元素。
和数组的第一个元素交换位置。（如果第一个元素就是最小元素那么就和自己交换）
在剩下的元素中找到最小的元素，和第二个元素进行交换。
重复3，每次交换的位置+1，直到整个数组排序完成。

# 算法特点

# 运行时间和输入无关

因为选择排序无论如何都要遍历整个数组并每次都要移动，为了找出最小的元素而扫描一遍数组并不能为下一遍扫描提供什么信息。这种性质在某些情况下是缺点，因为使用选择排序的人可能会惊讶的发现，一个已经有序的数组或是主键全部相等的数组和一个元素随机排列的数组所用的排序时间是一样长的。

# 数据移动是最少的

每次交换都会改变两个数组元素的值，因此选择排序用了N次交换，交换次数和数组大小是线性关系。

# 算法实现

public class Selection{
    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);
        }
}

# 插入排序

插入排序就像整理扑克牌，将每一张牌插入到其他已经有序的牌中的适当位置。在计算机的实现中，为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。这种算法叫插入排序。
插入排序的步骤很简单：

依次取数组中的一个元素
遍历当前元素左侧所有元素，找到一个位置，这个位置左侧元素小于这个元素，右侧元素大于这个元素。
将这个元素插入到这个位置，并将右侧所有元素右移一位。
重复前三步。

# 算法特点

和选择排序相同，当前索引左边的元素都是有序的，但它们的最终位置不确定，为了插入更小的元素，它们可能会向右移动。
与选择排序不同的是，插入排序的时间取决于元素的初始顺序，对于一个很大的其中的元素已经有序的数组进行排序会比随机顺序的数组或是逆序数组进行排序要快得多。

我们考虑更一般的情况是部分有序数组。倒置是指数组中的两个顺序颠倒的元素。（比如EXA中E-A,X-A）如果数组中倒置的数量小于数组大小的某个倍数，那么我们所这个数组是部分有序的。下面是几种典型的部分有序数组：

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

插入排序对这样的数组很有效，而选择排序则不然。实际上当倒置的情况很少时，插入排序额可能比其他任何排序都快。

# 算法实现

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

# 希尔排序

希尔排序的思想是使数组中任意间隔为h的元素是有序的。这样的数组称为h有序数组。进行排序时，如果h很大，我们就能将元素移动到很远的地方，为实现更小的h有序创造方便。
因此我们进行希尔排序的时候，先要创造一个任意以1结尾的h序列，这样就可以将数组进行排序，这就是希尔排序。
实际上我们就是用h替换掉了插入排序中每次指针+1或-1，改成了+h或-h。

# 算法特点

希尔排序比插入排序更高效，是因为在插入排序的基础上权衡了子数组的规模和有序性。排序之初，各个子数组都很短，排序之后子数组都是部分有序的。
不过透彻理解希尔排序的性能很难，实际上，h的选取也是多种多样的。

# 算法实现

这里我们使用了h=3*h+1的序列。

public class Shell{
    public static void sort(Comparable[] a){
        //将a[]按升序排列
        int N=a.length;
        int h=1;
        while(h < N/3) h=3*h+1; //1,4,13,40,121,364,1093, ...
        while(h >= 1){
            //将数组变为h有序
            for(int i=h; i < N; i++){
                //将a[i]插入到a[i-h],a[i-2*h],a[i-3*h]...之中
                for(int j=i;j >= h && less(a[j],a[j-h]); j-=h){
                    exch(a,j,j-h);
                }
            }
            h=h/3;
        }
    }
}