四种排序：堆排序、基数排序、桶排序、计数排序
堆排序
堆构建
首先堆是一种完全二叉树，使用数组构建，那么可以很容易得出，节点i的左子节点为i2，右子节点为i2+1。
构建堆的算法描述：我们需要确保每个节点满足堆的定义即可，因为所有叶子节点自然满足，所以我们从最后一个有子节点的节点开始调整，对于该节点，我们找出该节点、左子节点、右子节点中的最小值，如果该节点不是最小值，则与最小值节点进行交换，之后由于进行了交换，子节点有可能不满足堆结构，所以我们递归的调整子节点；
算法实现：
public static void main(String[] args) {
int[] arr = new int[10];
for(int i = 0; i < arr.length; i ++){
arr[i] = (int)(Math.random() * 10);
}
printInt(arr);
//最后一个有子节点的节点
int lastNonleaf = arr.length/2 - 1;
//向前遍历所有节点，使之满足堆的定义
for(int i = lastNonleaf; i >= 0; i --){
heapModify(i, arr);
}
printInt(arr);
}
public static void printInt(int[] arr){
for (int j : arr) System.out.print(j + " ");
System.out.println();
}
public static void heapModify(int i, int[] arr){
int minIdx = i;
int leftIdx = (i + 1) * 2 - 1;
int rightIdx = (i + 1) * 2;
//先要确定子节点是否存在
if(leftIdx < arr.length)
if(arr[minIdx] > arr[leftIdx])
minIdx = leftIdx;
if(rightIdx < arr.length)
if(arr[minIdx] > arr[rightIdx])
minIdx = rightIdx;
if(minIdx != i){
int tmp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = tmp;
//递归的调整已交换的节点，因为交换可能导致堆结构改变；
heapModify(minIdx, arr);
}
}
堆排序
算法描述：我们将第一个元素（小根堆的最小值）与最后一个元素交换，同时令堆的长度减一，并将堆从上往下调整，使之保持堆的性质，重复以上动作，直至堆得长度变为零；
public static void heapsort(int[] arr){
for(int i = 0; i < arr.length; i ++){
int tmp = arr[0];
arr[0] = arr[arr.length - i - 1];
arr[arr.length - i - 1] = tmp;
headDown(arr, arr.length - i - 1);
}
}
private static void headDown(int[] arr, int length) {
int c = 0;
int lc = 1;
int rc = 2;
while(lc < length){
int minIdx = c;
if(arr[minIdx] > arr[lc])
minIdx = lc;
if(rc < length){
if(arr[minIdx] > arr[rc])
minIdx = rc;
}
//如果需要交换就继续向下调整，直至不需要交换或者到达叶子节点
if(minIdx != c){
int tmp = arr[c];
arr[c] = arr[minIdx];
arr[minIdx] = tmp;
c = minIdx;
lc = (c + 1) * 2 - 1;
rc = (c + 1) * 2;
//如果不用交换就直接退出向下调整
}else{
break;
}
}
基数排序
算法描述： 创建10个桶，桶的定义为存放当前位上值相同的元素；找到数组最大值，最大值的位数就是需要进行几次桶存取；
public class ridixSort {
public static void main(String[] args) {
int[] arr = new int[10];
for(int i = 0; i < arr.length; i ++){
arr[i] = (int) (Math.random() * 10000);
}
printInt(arr);
//找到数组最大值，判断需要进行几次基数桶排序
int maxInt = -1;
for(int i = 0; i < arr.length; i ++){
if(maxInt < arr[i])
maxInt = arr[i];
}
int maxSize = 0;
while(maxInt > 0){
maxSize ++;
maxInt = maxInt / 10;
}
//基数排序核心：按照当前位将所有元素放入桶中，再按0-9的顺序取出；重复进行maxSize次；
//需要注意，我们需要一个数组来记录每个桶中有多少个数
for(int i = 0, n = 1; i < maxSize; i ++, n *= 10){
int[][] que = new int[10][arr.length];
int[] queNum = new int[10];
for(int j = 0; j < arr.length; j ++){
int k = arr[j] / n % 10;
que[k][queNum[k]] = arr[j];
queNum[k] ++;
}
for(int j = 0, k = 0; j < 10; j ++){
for(int jj = 0; jj < queNum[j]; jj++){
arr[k++] = que[j][jj];
}
}
printInt(arr);
}
printInt(arr);
}
static void printInt(int[] arr){
for(int i = 0; i < arr.length; i ++)
System.out.print(arr[i] + " ");
System.out.println();
}
}
桶排序
算法描述： 按照数据的分布范围，创建几个桶，将在该桶分布的元素放进同一个桶，递归进行，或者使用其他排序算法对桶内元素排序；
计数排序
算法描述： 找到数组最大值，创建一个arr = new int[maxInt]的数组，将源数组存进改数组中，元素值变为Idx；arr[值]++；