前言
曾经把常用的算法都写过，但是回想起来却想不起实现的细节，于是我就再次回顾了一下。
有幸看到这篇博客http://blog.csdn.net/hsuxu/article/details/9157925，于是决定尝试一下自己写。
快速排序
快速排序的最直观思想就是：找一个基数，把比基数小的放到基数的左边，比基数大的放到右边，这样就有了一个简单的顺序。
首先按照直观思想实现代码如下：
@SuppressWarnings("unchecked")
public static List<Integer> sort(List<Integer> array){
if(array.size() <= 1)
return array;
int index = rand.nextInt(array.size());
int value = array.get(index);
List<Integer> left = new ArrayList<Integer>();
List<Integer> right = new ArrayList<Integer>();
List<Integer> current = new ArrayList<Integer>();
for(int val : array){
if(val < value){
left.add(val);
}else if(val > value){
right.add(val);
}else{
current.add(value);
}
}
return contains(sort(left) ,current ,sort(right));
}
public static List<Integer> contains(List<Integer>... lists){
List<Integer> result = new ArrayList<Integer>();
for(List<Integer> l: lists){
result.addAll(l);
}
return result;
}
这个代码的性能和效率都是很差的，浪费了很多内存，实际运用中不会用这样的代码。
换一种思路，确定一个基数然后，给这个基数找到了正确的位置，不停的重复，最后每个数都会在正确的位置。
以下面这组数据为例：9，5， 4， 7， 23， 2， 21
首先找到key=9，扫描对比 ，这里要从最右边开始，因为key里面的存的数是重复的，如果key是存左边的数，那么左边的数是可以被替换的，从右开始扫描，反之key存的是右边的数的时候，从左边开始扫描。
key=9，下标L记为0，下标R记为6（数组长度-1），从右到左开始扫描R--，确保右边都是不比它小的数，（大于或等于）当扫描到元素2（R=5），不符合的期望，把L和R位置的数进行交换：2，5，4，7，23，9，21 ，同时L++，因为交换来的数是比key小的
切换扫描的方向L++，因为key里面的数交换到右边来了，确保左边都是不比它大的数，当扫描到元素23（L=4）时再次交换：
2，5，4，7，9，23，21，同时R++
扫描时要保证L<R，此时R==L，所以退出。这样得到的顺序保证了key的左边都是比key小，右边都是比key大。key最终的位置是K=4
接下来对0到K-1的数据和K+1到最后的数据进行排序操作。
上面过程就是给选定的数找到正确的位置，从右开始比它小的交换，比它小的必须放到左边，然后从左开始比它大的交换，比它大的必须放到右边。
原地分区版代码如下：
public static void sort(Integer[] array, int left, int right){
int l = left;
int r = right;
int temp = array[left];
while(left < right){
while(left < right && array[right] >= temp){
right--;
}
if(array[right] < temp){
array[left] = array[right];
left++;
}
while(left < right && array[left] <= temp){
left++;
}
if(array[left] > temp){
array[right] = array[left];
right--;
}
array[left] = temp;
}
if(left > l) sort(array ,l,left - 1);
if(left < r)sort(array, left + 1 ,r);
}
堆排序
堆排序有两个过程：1：构建堆，2：利用堆的特性重复取出数据调整堆这一过程。
堆分大根堆和小根堆，是完全的二叉树，大根堆的每个父节点不小于它的孩子节点，根结点就是最大的结点。
那么构建堆的过程就很明显：循环所有的父节点，保证父节点是三个节点（父节点和它两个孩子节点）中最大的节点，从最后一个父节点开始。
过程如下：
/**
* 创建堆
* @param array
*/
public static void buildHeap(int[] array){
int len = array.length;
int start = len / 2 - 1; //排在最后面的一个父节点
for(int i = start; i >= 0; i--){
adjustHeap(array, len, i);
}
}
/**
* 调整堆
* @param array
* @param len
* @param index
*/
public static void adjustHeap(int [] array, int len, int index){
int max = index;
int left = leftChild(index);
int right = rightChild(index);
while(left < len || right < len){
if(left < len && array[left] > array[max])
max = left;
if(right < len && array[right] > array[max])
max = right;
if(max == index) //不用调整
break;
int temp = array[index]; //父节点和最大节点交换
array[index] = array[max];
array[max] = temp;
index = max;
//可能会影响的后续节点
left = leftChild(index);
right = rightChild(index);
}
}
private static int rightChild(int index) {
return (index << 1) + 2;
}
private static int leftChild(int index) {
return (index << 1) + 1;
}
堆构建好以后，我们可以利用最大节点是根节点的特性把根节点放到数组的最后面，那么这个元素的位置是正确的。因为在最后面，我们只要把len--就可以排除了，这样在调整堆找到新的根结点的过程中，这个元素是不可见的。
代码如下
public static void heapSort(int[] array){
buildHeap(array);
int len = array.length;
int temp = 0;
while(len > 1){
temp = array[len -1];
//交换第一个节点和最后节点
array[len -1] = array[0];
array[0] = temp;
len--;
//排除排好序的元素
adjustHeap(array, len, 0);
//从新的根节点开始调整堆
}
}