ps: 转载注明出处-//www.greatytc.com/p/1d5efc911e81
作者

排序

排序的模板方法，所有的排序算法都会用到，交换数据，比较大小，验证是否排序好

/**
 * Created by zcw on 2017/3/19.
 */
public class SortTemlateMethod {
    public static void exch(Comparable[] a, int i, int min) {
        Comparable t = a[i];
        a[i] = a[min];
        a[min] = t;
    }

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

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


}

选择排序

思想：首先，找到数组中最小的那个元素，其次，将他和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将他与数组的第二个元素交换位置。如此往复，知道整个数组排序。[不断选择剩余元素之中的最小者]

/**
 * Created by zcw on 2017/3/19.
 * 选择排序
 */
public class Selection {

    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 (SortTemlateMethod.less(a[j], a[min])) min = j;

            }
            SortTemlateMethod.exch(a, i, min);

        }
    }
}

插入排序(部分有序和小规模的数组)

思想：我们在整理扑克牌的顺序，将每一张牌插入到其他已经有序的牌中的适当位置。在计算机实现中，为了要给插入的元素腾出空间，我们需要将其余所有元素再插入之前都向右移动一位。
与选择排序一样，当索引左边的所有元素都是有序的，但是他们最终还不确定，为了给更小的元素腾出空间，他们可能会被移动。但是当索引到达数组的右端时，数组排序完成。

/**
 * Created by zcw on 2017/3/19.
 * 插入排序
 */
public class Insertion {
    public static void sort(Comparable[] a){
        int N = a.length;
        for (int i = 1; i < N; i++) {
            for (int j = i; j >0 && SortTemlateMethod.less(a[j],a[j-1]); j--) {
                SortTemlateMethod.exch(a,j,j-1);
            }
        }
    }
}

希尔排序

思想：使数组中任意间隔为h的元素都是有序的。
这样的数组称为h有序数组。（一个h有序数组就是h个互相独立的有序数组编织在一起组成的一个数组）
排序的时候，如果h很大，我们就能将元素移动到很远的地方，为实现更小的h有序创造方便。用这种方式，对于任意以1结尾的h序列，我们都能将数组排序。

PS: 如果你需要解决一个排序问题，有没有系统函数可用（例如直接接触硬件或是运行于嵌入式系统中的代码），可以先用希尔排序，然后在考虑是否值得将它替换为更加复杂的排序算法。

归并排序

思想：

/**
 * Created by zcw on 2017/3/27.
 *
 * 自顶向下的归并排序
 */
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);
    }


    public static void merge(Comparable[] a, int lo, int mid, int hi) {
        int i = lo;
        int j = mid + 1;

        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 (SortTemlateMethod.less(aux[j], aux[i])) a[k] = aux[j++];
            else a[k] = aux[i++];
        }
    }

    
}

快速排序（数组小的话切换到插入排序，根据业务而定）

思想：分治法，将一个数组分成两个子数组，将两部分独立排序。
（快排和归并排序是互补的：归并是将数组分成两个子数组分别排序，然后将有序的子数组归并已经整个数组排序，递归发生在处理整个数组之前，数组被等分）快速排序是当两个子数组都有序时整个数组自然就有序了，递归发生在处理整个数组之后，数组根据内容分组

/**
 * Created by zcw on 2017/3/27.
 */
public class QuickSort {

    public static int partition(Comparable[] a, int lo, int hi) {
        int i = lo, j = hi + 1;
        Comparable v = a[lo];
        while (true) {
            // 扫描左右检查是否结束并交换元素
            while (SortTemlateMethod.less(a[++i], v)) if (i == hi) break;
            while (SortTemlateMethod.less(v, a[--j])) if (j == lo) break;
            if (i >= j) break;
            SortTemlateMethod.exch(a, i, j);
        }
        SortTemlateMethod.exch(a, lo, j);
        return j;
    }


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

优先队列(对比java api -PriorityQueue)

操作思想：删除最大/最小元素，插入元素

查找

符号表

分类：有序符号表和无序符号表
符号表应用的共同特征：

混合使用查找和插入操作
大量的不同的键
查找操作比插入操作多得多
虽然不可以预测，但查找和插入操作的使用模式并非随机

算法

排序