算法4学习-2.1 初级排序算法(选择排序、插入排序、希尔排序)

这一章的内容开始多了，怎么说呢，代码都是见过的，但是书中的解析太迷人了。
粗略的看了这一章，粗略记录,理解不透的回顾的时候再补充。

排序算法类模板

排序类的算法都会使用两个方法操作数据:less()方法对元素进行比较，exch()方法将元素交换位置。将数据操作限制在这两个方法中使得代码的可读性和可移植性更好。

/**
 * Created by tuzhis on 2016年1月16日.
 */
public class SortTemplet {
    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);
    }
}

选择排序

首先找到数组中最小的元素,其次,将它和数组的第一个元素交换位置。

public static class Selection extends SortTemplet {
    // 选择排序
    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);
        }
    }
}

插入排序

当前索引左边的元素都是有序的，但他们最终位置还不确定，为了给更小的元素腾出空间，它们可能会被移动。但是当索引到达数组的右端时，数组的排序就完成了。

public static class Insertion extends SortTemplet {
    // 插入排序
    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);
        }
    }
}

希尔排序

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

public static class shell extends SortTemplet {
    // 希尔排序
    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...
        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;
        }
    }
}

FAQ

1.定义一个可比较的数据类型

package FAQ;
/**
 * Created by tuzhis on 2016年1月17日.
 */
public class Date implements Comparable<Date> {
    private final int day;
    private final int month;
    private final int year;

    public Date(int d, int m, int y) {
        day = d;
        month = m;
        year = y;
    }

    public int day() {
        return day;
    }

    public int month() {
        return month;
    }

    public int year() {
        return year;
    }

    @Override
    public int compareTo(Date that) {
        // TODO Auto-generated method stub
        if (this.year > that.year)
            return +1;
        if (this.year < that.year)
            return -1;
        if (this.month > that.month)
            return +1;
        if (this.month < that.month)
            return -1;
        if (this.day > that.day)
            return +1;
        if (this.day < that.day)
            return -1;
        return 0;
    }

    public String toString() {
        return month + "/" + day + "/" + year;
    }
}

2. 随机生成测试数据测试

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;

public static void main(String[] args) {
    int N = 200;                              //测试数据个数
    Integer a[] = new Integer[N];
    for (int i = 0; i < N; i++)
        a[i] = StdRandom.uniform(1, 100); //重载生成范围内整数
    // Selection.sort(a);
    Insertion.sort(a);
    assert isSorted(a);
    show(a);
}