[TOC]

algorithm 4th笔记(2.1)

两个object可以比较的前提

1. object实现Comparable。
2. 提供Comparator ，此处还说明了Comparator的第二和用法。

排序用到的方法less 判断两object的大小关系 exch交换两个object,注意对象需要实现Comparable接口，才能使用。

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

排序算法类的模板,用到的时候，只需要填写排序算法即可

/**
 * Created by admin on 2016/11/20.
 */
public class SortExample {
    //排序算法具体实现
    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++){
            System.out.print(a[i]+" ");
        }
        System.out.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);
//    }
    private static String[] readDataFromFile(String fileName) throws Exception{
        /*
         *从data.in中读取数据，然后把数据转换成Integer(包装了有Comparable接口)
         */
        URL url = SortExample.class.getClassLoader().getResource(fileName);
        File file = new File(url.getPath());
        Scanner sc=new Scanner(file);

        String str= sc.nextLine();
        return str.split(" ");
    }
    public static void main(String[] args) throws Exception{
        //设计成从文件读入数据，然后把数据(maven下，数据放在resources目录)
        String[] ss=readDataFromFile("ch02/data.in");

        int N=ss.length;
        Integer[] arr=new Integer[N];
        for(int i=0;i<N;i++){
            arr[i]=new Integer(Integer.parseInt(ss[i]));
        }

        sort(arr);
        assert isSorted(arr);
        show(arr);
    }
}

Select排序

[0 ... idx ... len - 1]
每次从(idx,len-1]之间选择一个最小的与idx处的值交换。

// 只能对实现Comparable接口的数据类型排序
private static void sort(Comparable[] a) {
    int len = a.length;
    for (int i = 0; i < len; ++i) {
        int min = i;
        for (int j = i + 1; j < len; ++j) {
            if (less(a[j], a[min])) {
                min = j;
            }
        }
        assert isSorted(a, 0, i);
        exch(a, i, min);
    }
    assert isSorted(a);
}

Insert排序

[0 ... idx ... len - 1]
从idx开始，把idx处的值插入到已经排序后的[0,idx)中适当的位置。

// 只能对实现Comparable接口的数据类型排序
private static void sort(Comparable[] a) {
    int n = a.length;
    for (int i = 1; i < n; ++i) {
        for(int j = i; j > 0; --j){
            if(less(a[j],a[j-1])){
                exch(a,j,j-1);
            }
        }
        assert isSorted(a,0,i);
    }
    assert isSorted(a);
}

Shell排序

可以看作Insert排序的改进版本。把一个数组中的所有元素分成几部分来排序；先把几个小部分的元素排序好，让元素大概有个顺序，最后再全面使用插入排序。一般最后一次排序都是和上面的插入排序一样的；

// 只能对实现Comparable接口的数据类型排序
private static void sort(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);
            }
        }
        assert isSorted(a);
        h /= 3;
    }
    assert isSorted(a);
}

注意： 最差情况下：shell排序的时间复杂度为O(n^2);
最佳情况下，Shell排序的时间复杂度为O(n^1.3) --> 具体推理上不做说明。
以前一直以为Shell排序的时间复杂度为O(nlog(n))。