算法笔记三

Sort

Introduction

• Goal.Sort any type of data.

How can sort() konw how to compare data of type Double,String,and java.io.File without any information about the type of an item’s key?

Callback = reference to executable 对可执行代码的应用.

• Client passes array of objects to sort() function.
• The sort() function calls back object’s compareTo() method as needed.

Implementing callbacks.

• Java : interfaces.
• C : function pointers.
• C++ : class-type functors.
• C# : delegates.
• python,Perl,ML,Javascript : first-class functions.

Two useful sorting abstractions

Helper functions. Refer to data through compares and exchanges.

Less. Is item v less than w ?

private static boolean less(Comparable v,Comparable w){
    return v.compareTo(w) < 0;
}

Exchange. Swap item in array a[] at index i with the one at index j.

private static void exch(Comparable[] a,int i,int j){
    Comparable swap = a[i];
    a[i] = a[j];
    a[j] = swap;
}

Goal.Test if an array is sorted.

private static boolean isSorted(Comparable[] a){
    for(int i=1;i<a.length;i++){
        if(less(a[i],a[i-1]))
            return false;
        return true;
    }
}

Q:If the sorting algorithm passes the test,did it correctly sort the array?
A:No.

Selection sort

• In iteration i, find index min of smallest remaining entry.
• Swap a[i] and a[min].

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);
        }
 }
    private static boolean less(Comparable v, Comparable w){
        /* as before */ }
    private static void exch(Comparable[] a, int i, int j){
        /* as before */ }
}

Insertion Sort

• In iteration i, swap a[i] with each larger entry to its left.

• 逆序对

public class Insertion{
    public static void main(Comparable[] a){
        int N = a.length;
        for(int i=0;i<N;i++){
            for(int j=i;j>0;j--){
                if(less(a[j],a[j-1])){
                    exch(a,j,j-1);
                }
                else break;
            }
        }
    }
    private static boolean less(Comparable v, Comparable w){
        /* as before */ }
    private static void exch(Comparable[] a, int i, int j){
        /* as before */ }
}

Shell Sort

public class Shell{
    public static void main(Comparable[] a){
        int N = a.length;

        int h = 1;
        while(h < N/3){
            h = 3 * h + 1;
        }

        while(h >= 1){
            for(int i = h; i < N; i++){
                for (int j = i; j >= h && less(a[j], a[j-h]); j -= h)
                    exch(a, j, j-h);
            }
            h = h/3;
        }
    }
    private static boolean less(Comparable v, Comparable w){
        /* as before */ }
    private static void exch(Comparable[] a, int i, int j){
        /* as before */ }
}

Shuffle

两种方法

• 第一种

  • Generate a random real number for each array entry.

  • Sort the array.

• Knuth shuffle