Java 排序（这里统一做从小到大排）
快速排序 ·
快速排序用分而治之的思想。对于要排序的数据，选取最左边的作为基准，然后将比基准大的数放到其右边，将比基准小的数放到其左边，然后以基准位子进行分割，对其左右做分治递归操作。
int[] data;//待排序数组
//快速排序java代码
public void quickSort(int[] data,int left,int right){
if(left<0||right>data.length) return;
if(left<right){
int i=left;
int j=right;
int base=data[i];
while(i<j){
while(i<j&&data[j]>base) j--;
if(i<j) data[i++]=data[j];
while(i<j&&data[i]<base) i++;
if(i<j) data[j--]=data[i];
}
data[i]=base;
quickSort(data,left,i-1);
quickSort(data,i+1,right);
}
}
快速排序可以理解成如下：
首先在最左边挖一个坑 base=data[i]
然后从最右边开始找一个比这个数小的值来填补这个坑data[i++]=data[j]
此时data[i] 这个坑被data[j] 填补了，现在坑变成了data[j]
然后从左边开始寻找一个比base大的数来填坑 data[j--]=data[i]
不断重复知道 i==j,此时跳出循环将最开始的base填入data[i] 中
这时候就形成了以位置i为分界点左边全部比base小，右边全部比base大的局面
最后递归这个过程就完成看排序
快速排序分析
快速排序复杂度 辅佐空间为O(1)
堆排序
堆排序的主要思想是不断维护一个堆，在这里谈从小到大排序的话就维护一个大顶堆，每次从堆顶取出一个元素（这个元素在堆中是最大的）,然后与堆尾交换，之后堆大小减小1，重新调整堆。
要点如下
1 构造 初始化大顶堆
2 从堆顶取出元素与堆尾交换，堆大小减一
3 重新调整被破坏的堆
重复步骤2 直到堆大小为0 此时数组已经被从小到大排序完毕
堆这个数据结构特点：
- 父节点一定比左右子节点要大
- 堆在存储时有数组存储，父节点ID=i,那么左右子节点ID分别为 2i+1和 2i+2
最开始构造堆时从最后一个非叶子节点开始调整，其ID最大为堆大小一半，调整过程中只需要比较父节点和左右子节点的大小，将最大的作为父节点，如果左右子节点被交换到父节点时，那么此时我们认为被交换的节点之下可能不满足堆的特性，需要对其进行调整，这是一个递归的操作。当所有非叶子节点被调整完毕，那么此时就完成了堆的初始化。
在每次取出对顶元素之后只需要堆从对顶开始调整堆即可。
int data[];
//调整堆
public void adjustHeap(int[] data,int sizeOfHeap,int index){
int left=2*index+1;
int right=2*index+2;
int largest=index;
if(left<sizeOfHeap&&data[left]>data[index]) largest = left;
if(right<sizeOfHeap&&data[right]>data[largest]) largest=right;
if(largest!=index){
int tmp=data[index];
data[index]=data[largest];
data[largest]=tmp;
adjustHeap(data,sizeOfHeap,largest);
}
}
//初始化堆
public void buildMaxHeap(int[] data){
int size=data.length;
for(int i=size/2;i>=0;i--){
adjustHeap(data,size,i);
}
}
//完全堆排序
public void sortHeap(int[] data){
for(int i=data.length-1;i>=0;i--){
int tmp=data[0];
data[0]=data[i];
data[i]=tmp;
adjustHeap(data,i,0);
}
}
同时根据堆的性质，在一个序列里面取出TopK个数据非常适合堆排序的方式来做到。
public void getTopK(int[] data){
int startN=data.length-1;
int endN=startN-k+1;
if(endN<0) return;
for(int i=startN;i>=endN;i--){
int tmp=data[0];
data[0]=data[i];
data[i]=tmp;
adjustHeap(data,i,0);
}
}
从数组尾部读取K个即可，当然这里是取得最大的K 个，如果需要最小的K个则可以使用小顶堆。
