ps: 转载注明出处-http://www.jianshu.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)
操作思想：删除最大/最小元素，插入元素
查找
符号表
分类： 有序符号表和无序符号表
符号表应用的共同特征：
- 混合使用查找和插入操作
- 大量的不同的键
- 查找操作比插入操作多得多
- 虽然不可以预测，但查找和插入操作的使用模式并非随机
