其实在之前刷leetcode的链表的题目就碰到链表排序了，所以这里先记录做链表就碰到的两个排序。
插入排序：147. Insertion Sort List
快排：148. Sort List
148这题要求复杂度为nlogn所以就想到用快速排序做，将第一个节点作为partition，大于等于partition的放在一个链表中，小于的放在一个链表中，最后两者合并，网上看到有不改变链表，仅交换节点内的数据的说法，但是总觉得这样不好.....
在这里为了减少打印原数组和排序后数组的重复代码，用了动态代理，Java动态代理的使用如下JDK和cglib动态代理
1：基础排序
1.1：冒泡
虽然这个书上并没有，但是我觉得我还是得记录一下。大概思想就是每次遍历都找到最大的值放到数组最后面。
public void sort(Integer[] a) {
for(int i=0;i<a.length-1;i++) {
for(int j=0;j<a.length-1-i;j++) {
if (a[j]>a[j+1]) {
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
1.2插入排序，希尔排序
插入排序的思维和上面链表的一样：
i=[1,length-1]
j=[i,1]
if(a[i]<a[j]) a[j]=a[j-1]
a[j]=a[i];
希尔排序则是插入排序的变种，对数组任意间隔为h的元素进行插入排序。这是为了避免插入排序的极端情况：最小值为数组尽头时，数组移动N-1次。
//插入排序
public void sort(Integer[] a ) {
for(int i=1;i<a.length;i++) {
int temp = a[i];
int j;
//从i向前遍历，如果有比当前值大的，数组值向后移一位，当前值插入到该值的位置。
for(j=i;j>0 && temp<a[j-1];j--) {
a[j] = a[j-1];
}
a[j] = temp;
}
}
//希尔排序
public void sort(Integer[] a) {
Integer N = a.length;
Integer h=1;
while(h<N/3) h = h*3+1;
// 将数组分割为长度为h的一个个小数组，然后用插排将数组变为每隔h个值就有序。
while(h>=1) {
for(Integer i=h;i<N;i++) {
for(Integer j=i;j>=h&&a[j]<a[j-h];j-=h) {
Integer temp = a[j];
a[j] = a[j-h];
a[j-h] = temp;
}
}
h = h/3;
}
}
2:归并，快排，堆排序
2.1：归并排序
这个算是最好理解的排序了，首先递归将数组分割成多个数组，然后合并，在合并的时候加入判断确保顺序正确。个人感觉最大的问题是需要建立一个辅助数组用于存储源数据，看的挺膈应的。
public void sort(Integer[] a) {
aux = new Integer[a.length];
sort(a,0,a.length-1);
}
private void sort(Integer[] a,int low,int high) {
if (low>=high) {
return;
}
int mid = (high+low)/2;
//对数组进行分割
sort(a, low, mid);
sort(a, mid+1, high);
//合并子数组
merge(a,low,mid,high);
}
//合并[low,mid]和[mid+1,hi]两个子数组。
private void merge(Integer[] a,Integer low,Integer mid,Integer hi) {
Integer i = low;
Integer j = mid+1;
for(int n = low;n<=hi;n++) {
aux[n] = a[n];
}
Integer i = low;
Integer j = mid+1;
for(int n = low;n<=hi;n++) {
aux[n] = a[n];
}
int k=low;
while(k<=hi) {
if (i>mid) {
a[k++] = aux[j++];
}
else if (j>hi) {
a[k++] = aux[i++];
}
else if (aux[j]<=aux[i]) {
a[k++] = aux[j++];
}
else {
a[k++] = aux[i++];
}
}
}
2.2快速排序
快速排序的思想是选取一个值，然后切分数组，将数组分为大于这个值和小于这个值两部分。数组的实现一般是选取第一个数为切分值，然后向前遍历找到小于这个值的成员，同时向后遍历找到大于这个值的成员，然后交换两者，最后再将切分值插入遍历完成的数组的中间。
快速排序需要注意的一点是当扫面的时候发现有值相同的元素该如何处理。可以选择跳过相同元素，因为这样保证了排序的稳定，但是这种会导致快排在处理只有若干元素的数组时运行时间为平方级。
public class QuickSort{
public void sort(Integer[] a) {
quickSort(a, 0, a.length - 1);
}
private void quickSort(Integer[] a,Integer low,Integer high) {
if (high<=low) {
return;
}
Integer partition = partition(a, low, high);
quickSort(a, low, partition-1);
quickSort(a, partition+1, high);
}
private Integer partition(Integer[] a,Integer low,Integer high) {
Integer i=low,j=high+1;
Integer value = a[low];
while(true) {
while(a[++i]<value) {
if (i==high) {
break;
}
}
while(a[--j]>value) {
if (j==low) {
break;
}
}
if (i>=j) {
break;
}
Integer temp = a[i];
a[i] = a[j];
a[j] =temp;
}
Integer temp = a[low];
a[low] = a[j];
a[j] = temp;
return j;
}
}
2.3堆排序
感觉这里书上讲的很好啊...首先用数组形式的二叉堆实现了一个优先队列引出了二叉堆的两个重要的堆有序操作，上浮/下沉
//上浮，自下而上的操作
private void swim(int k){
while(k>1&&a[k/2]<a[k]){
exch(a[k/2],a[k]);
k = k/2;
}
}
//下沉，自上而下的操作
private void sink(int k){
while(k*2<=length){
int j = 2*k;
//选取子节点中大的那个
if(j<length && a[j]<a[j+1]){
j++;
}
if(a[k]>=a[j])break;
exch(a[k],a[j]);
k=j;
}
}
堆排序的思路是首先将数组转换为堆有序，然后将a[1]与a[length]交换，将最大值移到数组最后一位，然后再对剩余数组第一位进行一次sink()操作，保证第一位是最大值，然后再将a[1]和a[length-1]交换，以此类推。
其实个人觉得这玩意儿怪怪的，根据下标构建二叉堆的话第0位一般空着不会被访问到，这就对输入有特殊要求了呀..
最后书上对于堆排序不常用的说法是：堆排序很少与相邻的其他元素比较因此它无法利用缓存。
public void sort(Integer[] a) {
int N = a.length - 1;
//堆有序，最大值在最前面
for (int k = N / 2; k >= 1; k--)
sink(a, k, N);
//将最大值放到数组最后面，然后再通过sink操作保证第一个只一定是最大值。
while (N > 1) {
exch(a, 1, N--);
sink(a, 1, N);
}
}
private void sink(Integer[] a, int k, int N) {
while (2 * k <= N) {
int child = 2 * k;
if (child < N && a[child] < a[child + 1]) {
child++;
}
if (a[k] >= a[child]) {
break;
}
exch(a, k, child);
k = child;
}
}
