排序学习

算法

排序就是将一组对象按照某种逻辑顺序重新排列的过程

游戏规则

排序算法模板API设计

排序算法模板类的实现

public class Example{
    public static void sort(Comparable[] a){
        //后面补充实现
    }
    private static boolean less(Comparable v ,Comparable w){
        return v.compareTo(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.readString();
        sort(a);
        assert isSorted(a); //确认排序后数组元素都是有序的
        show(a);
    }
}

选择排序

说明

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

命题A 对于长度为N的数组，选择排序需要大约$N^2$次比较和N次交换

选择排序具有两个鲜明的特点：运行时间和输入无关和数据移动是最少的

实现

public class Selection{
    public static void sort(Comparable[] a){
        //将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);
        }
    }
}

选择排序的轨迹

插入排序

说明

将每个元素插入到已有的有序的序列中

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

算法实现

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

插入排序的轨迹

命题C 插入排序所需要的交换操作和数组中倒置的数量相同，需要的比较次数大于等于倒置的数量，小于等于倒置的数量加上数组的大小再减一

插入排序对于部分有序的数组非常高效，也很适合小规模数组。

比较两种排序算法

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

针对给定输入，为本章中的一种排序算法计时

public static double time(String alg,Comparable[] a){
    Stopwatch timer = new Stopwatch();
    if(alg.equals("Insertion"))
        Insertion.sort(a);
    if(alg.equals("Selection"))
        Selection.sort(a);
    if(alg.equals("shell"))
        Shell.sort(a);
    if(alg.equals("Merge"))
        Merge.sort(a);
    if(alg.equals("Quick"))
        Quick.sort(a);
    if(alg.equals("Heap"))
        Heap.sort(a);
    return timer.elapsedTime();
}

比较两种排序算法

public class SortCompare{
    public static double time(String alg,Double[] a){
        //见上文
    }
    public static double timeRandomInput(String alg, int N ,int T){
        //使用算法alg将T个长度为N的数组排序
        double total = 0.0 ;
        Double[] a = new Double[N] ;
        for(int t = 0 ; t< T;t++){
            //进行一次测试，生成一个数组并排序
            for(int i = 0; i < N ; i++){
                a[i] = StdRandom.uniform();
            }
            total +=time(alg,a);
        }
        return total;
    }
    public static void main(String[] args){
        String alg1 = args[0];
        String alg2 = args[1];
        int N = Integer.parseInt(args[2]);
        int T = Integer.parseInt(args[3]);
        double t1 = timeRandomInput(alg1,N,T);//算法1的总时间
        double t2 = timeRandomInput(alg2,N,T);
        StdOut.printf("For %d random Doubles\n  %s is",N,alg1);
        StdOut.printf("%.0f times faster than %s\n",t2/t1,alg2);
    }
}

希尔排序

说明

希尔排序为了加快速度简单的改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组进行排序

实现

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;
            }
        }
    }
}

性质E 使用递增序列1,4,13,40,121,364...的希尔排序所需的比较次数不会超出N的若干乘以递增序列的长度。
希尔排序的运动轨迹

归并排序

说明

优点 它能保证将任意长度为N的数组排序所需时间和NlogN成正比；缺点它所需的额外空间和N成正比

原地归并的抽象方法

public static void merge(Comparable[] a , int lo ,int mid ,int hi){
    int i = lo ;
    int j = mid + 1 ;
    //将a[lo..hi]复制到aux[lo..hi]中
    for(int k = lo ;k <= hi ; k++){
        aux[k] = a[k];
    }
    for(int k = lo ; k<=hi ;k++){
        if(i>mid)
            a[k] = aux[j++];
        else if(j>hi)
            a[k] = aux[i++];
        else if(less(aux[j],aux[i]))
            a[k] = aux[j++];
        else
            a[k] = aux[i++];
    }
}

记起来实在太麻烦了，先将所有元素复制到aux[]中。然后进行四个条件的判断，如果左边用尽(取右半边元素)，右半边用尽(取左半边元素)、右半边元素小于左边元素（取右边元素）、右边元素大于左边元素（取左边元素）
原地归并的抽象方法的运动轨迹

自顶而下的归并排序

public class Merge{
    private static Comparable[] aux;
    public static void sort(Comparable[] a){
        aux = new Comparable[a.length];
        sort(a,0,a.length-1);
    }
    private static void sort(Comparable[] a, int lo ,int hi){
        if(hi <= lo) 
            return;
        int mid = lo + (hi - lo)/2;
        sort(a,lo,mid);//将左半边排序
        sort(a,mid+1,hi);//将右半边排序
        merge(a , lo ,mid ,hi)//归并结果
    }
}

自顶向下的归并排序中归并结果的轨迹

自顶向下的归并排序的调用轨迹

命题F对于长度为N的任意数组，自顶向下的归并排序需要1/2NlgN至NlgN次比较

命题G对于长度为N的任意数组，自顶向下的归并排序最多需要访问数组6NlgN次

快速排序

说明

特点是原地排序，且将长度为N的数组排序所需的时间和NlogN成正比,内循环比大多数排序算法都要短小

基本算法

public class Quick{
    public static void sort(Comparable[] a){
        StdRandom.shuffle(a); //消除对输入的依赖
        sort(a , 0 , a.length-1 );
    }
    private static void sort(Comparable[] a, int lo ,int hi){
        if(hi <= lo) return;
        int j = partition(a , lo ,hi );//切分
        sort(a,lo,j-1);
        sort(a,j+1,hi);
    }
}