2.1 Elementary Sorts

Rules of the game

In Java,the abstract notion of a key is captured in a built-in mechanism-the Comparable interface.There are two inportant method: less() and exch()

private static boolean less(Comparable v,Comparable w){
    return (v.compareTo(w) < 0);
}
private static void exch(Comparable[] a,int i,int j){
    Comparable swap = a[i];
    a[i] = a[j];
    a[j] = swap;
}
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;
} 

compareTo()实现了我们的主键抽象——它给出了实现Comparable接口的任意数据类型的对象的大小顺序的定义。

选择排序

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

特点：

1. 运行时间与输入无关
2. 数据移动是最少的

public class selection
{
    public static void sort(Comparable[] a)
    {
        int N = a.length;
        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);
        }
    }
}

插入排序

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

public class Insertion
{
    public static void sort(Comparable[] a)
    {
        int N = a.length;
        for(int i = 1;i < N;i++)
        {
            for(int j = 0;j>0 && less(a[j],a[j-1]); j--)
                exch(a,j,j-1);
        }
    }
}

适用范围：

1. 部分有序的数组
2. 小规模数组

希尔排序

希尔排序是一种基于插入排序的快速排序算法。
改进：交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。

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;
            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-1]); j -= h)
                        exch(a,j,j-h);
                }
                h = h/3;
            }
        }
    }

exercise

1. What is the maximum number of exchanges involving any particular item during selection sort? What is the average number of exchanges involving an item?
   Solution. The average number of exchanges is exactly 1 because there are exactly N exchanges and N items. The maximum number of exchanges is N, as in the following example.

2. Which method runs fastest for an array with all keys identical(主键相同), selection sort or insertion sort?
   Solution. Insertion sort runs in linear time when all keys are equal.

3. Show in the style of the example trace with shellsort, how shellsort sort sorts the array
   E A S Y S H E L L S O R T Q U E S T I O N
   Solution.
   

4. Transaction sort test client. Write a class SortTransactions.java that consists of a static method main() that reads a sequence of transactions from standard input, sorts them, and prints the result on standard output.

   public class SortTransactions{
       public static Transaction[] readTransaction(){}
       public static void main(String[] args){
           Transaction transaction = readTransaction();
           Shell.sort(transaction);
           for(Transaction t:transaction)
               StdOut.println(t);
       }
   }
   

   Experiments

---