排序篇：
冒泡排序：
原理
趟一趟的比，每一趟中，循环剩余的数，和后一个进行比较，若比它小则交换。这样一趟下来最小的在第一个，最大的在最后一个。总共比n-1趟。
/**
* 最简单的冒泡排序
* 原理：比较相邻两个元素，从第一对开始比较一直到最后一对，若顺序不对就交换（感觉就像冒泡一样）。
* 一趟比较后，最大（或最小）的会位于最后的位置，然后再以类似方式比较前面的元素。
*/
public class BubbleSort extends Sortable {
public BubbleSort(){
super.LABLE = "冒泡排序";
}
@Override
public void sort(int[] a) {
for(int i=0;i
for(int j=0;j
if(less(a[j+1],a[j])){
exch(a,j,j+1);
}
}
}
}
}
时间复杂度（n^2)
选择排序:
原理
选择排序可以说是最好理解的算法。就是每次遍历一趟，找出最小的数，放到最前端。（这里说的是最前，是指无序的队列中的最前
public void sort(int[] a) {
for(int i=0;i
int min=i;
for(int j=i+1;j
if(less(a[j],a[min])){
min = j;
}
}
exch(a,i,min);
}
插入排序
时间复杂度O(n²)。
遍历未排序序列。把未排序数列的第一个数和已排序数列的每一个数比较，若比它大则交换。经典的理解方式就是理解成摸牌时候理牌的顺序。我上面的实现是直接交互数字，若是把大的数直接往后移效率还会更高。
public void sort(int[] a) {
for(int i=1;i<a.length;i++){
for(int j=i;j>0;j--){
if(less(a[j],a[j-1])){
exch(a,j,j-1);
}
else break;
}
}
适合插入排序的数据
当你的数据是基本有序的时候且数据量小，利用插入排序的时候，效率会很高。若数据为逆序的话，效率很低。
希尔排序
可以看出是插入排序的一种优化，或者是预处理。希尔排序就是先进行h-sort，也就是让间隔为h的元素都是有序的。普通的插入排序就是1-sort。
原理
主要就是选定一个h的有序数组来进行预排序。这样最后进行插入排序的时候，能使数据局部有序。就算交换的话，交换的次数也不会很多。这样h序列称为递增序列。希尔的性能很大部分取决于递增序列.一般来说我们使用这个序列3x + 1.
public void sort(int[] a) {
int h=1;
while(h
h=3*h+1;
}
while(h>=1){
for(int i=h;i
for(int j=i;j>=h;j=j-h){
if(less(a[j],a[j-h])){
exch(a,j,j-h);
}
else break;
}
}
h=h/3;
}
}
性能
对于希尔排序的性能其实无法准确表示。介于O(nlogn)和O(n²)之间，大概在n的1.5次幂左右。
希尔排序对于中大型数据的排序效率是很高的，而且占用空间少，代码量短。而且就算是很大的数据，用类似快排这种高性能的排序方法，也仅仅只比希尔快两倍或者不到。
归并排序
复杂度O(nlogn).
核心思想就是采用分而治之的方法，递归的合并两个有序的数组。效率比较高，缺点是空间复杂度高，会用到额外的数组。
/**
* 归并排序
* @author anxpp.com
*
*/
public class MergeSort extends Sortable {
public MergeSort(){
super.LABLE = "归并排序";
}
int[] temp ;
private void merge(int[] a, int l, int m, int h){
for(int i=l;i<=h;i++){
temp[i]=a[i];
}
int i=l;
int j=m+1;
for(int k=l;k<=h;k++){
if(i>m) a[k]=temp[j++];
else if(j>h) a[k]=temp[i++];
else if(less(temp[i],temp[j])) a[k]=temp[i++];
else a[k] = temp[j++];
}
}
private void sort(int[] a,int l,int h) {
if(l
int mid = (l+h)/2;
sort(a,l,mid);
sort(a,mid+1,h);
if (!less(a[mid+1], a[mid])) return;
merge(a,l,mid,h);
}
}
@Override
public void sort(int[] a) {
temp = new int[a.length];
sort(a,0,a.length-1);
}
}
如果递归时判断已经有序则不用继续递归。也可以增加效率。
private void sort(int[] a,int l,int h) {
if(l
int mid = (l+h)/2;
sort(a,l,mid);
sort(a,mid+1,h);
if (!less(a[mid+1], a[mid])) return;
merge(a,l,mid,h);
}
}
另外在合并时交互两个数组的顺序，能节省复制数组到辅助数组的时间，但节省不了空间。
快速排序
传说中最快的排序算法，听说能裸写快排，月薪可上10k...
快排平均情况下时间复杂度O(nlogn)，最糟糕情况O(n²)。O(n²)主要是因为选定的主元是极端值造成的，比如说最大值，最小值。不过这种情况一般很少出现，所以在进行快排之前我们需要对数组进行乱序，尽量避免这种情况的发生。
第一步打乱数组。
然后也是分治法。归并是先分再合并。快排是先排序再分别排序两边。
排序过程核心思想是为了选出一个数，把数组分成左右两边，左边比主元小，右边比主元大。
选定第一个数作为主元。然后设定两个index指向数组首尾，比如i，j。接着从两边向中间扫描，分别用a[i]和a[j]和主元比较。若两边位置不对则交换a[i]和a[j]，比如说a[i]在扫描过程中遇到a[i]>主元，那么则停止扫描,因为我们需要左边的数小于主元,反正右边也一样等到a[j]也停下来,则交换a[i]和a[j]。
private void sort(int[] a,int low,int high){
//左
int l =low;
//右
int h = high;
//基准值
int k = a[low];
//判断一趟是否完成
while(l
//若顺序正确就比较下一个
while(l=k)
h--;
if(l
int temp = a[h];
a[h] = a[l];
a[l] = temp;
l++;
}
while(l
l++;
if(l
int temp = a[h];
a[h] = a[l];
a[l] = temp;
h--;
}
}
if(l>low) sort(a,low,l-1);
if(h
}
@Override
public void sort(int[] a) {
sort(a,0,a.length-1);
}
适用范围
虽然快速排序是不稳定的。但快速排序通常明显比其他Ο(nlogn)算法更快，因为它的内部循环很小。快速排序在对重复数据的排序时，会重复划分数据进行排序。虽然性能也还行，但这里可以进行改进，就是下面介绍的三向切分排序。
堆排序
时间复杂度O(nlogn)，堆排序主要用二叉堆实现，在讲堆排序之前我们可以要先了解下二叉堆。
所谓的二叉堆用一颗二叉树表示，也就是每一个节点都大于它的左右子节点。也就是说根节点是最大的。
二叉树用数组存储，可以用下标来表示节点。比如i这个节点的父节点为i/2，左儿子为2*i，右儿子为2*i+1.
堆的操作主要有两种上浮和下沉。主要对应两种情况，比如在数组末尾添加节点，此时需要上浮节点，保证二叉堆的特点。反之在替换根节点是则需要下沉操作。
分为两步。
把数组排成二叉堆的顺序
调换根节点和最后一个节点的位置，然后对根节点进行下沉操作。
适用范围
堆排序也是不稳定的。
堆排序在空间和时间上都是O(nlogn),且没有最糟情况，但在平均情况下比快排慢。
所以现在大部分应用都是用的快排，因为它的平均效率很高，几乎不会有最糟情况发生。
但如果你的应用非常非常重视性能的保证，比如一些医学上的监控之类的。
那么可以使用堆排序。还有一个堆排序的缺点，是它无法利用缓存，几乎很少和相邻元素的比较。
