春蚕到死丝方尽，蜡炬成灰泪始干
——无题
这里介绍两个比较难的算法：
1、堆排序
2、分治并归排序
先说堆。
这里请大家先自行了解完全二叉树的数据结构。
堆是完全二叉树。大顶堆是在堆中，任意双亲值都大于（或等于）其孩子值，就称其为大顶堆。
堆排序的步骤：
1、把数组想象成一个堆。数组的index+1就是其对应在堆中的序号
2、调堆中各值的顺序，得到大顶堆
3、将堆首位值与堆末尾值交换，最大值排序完毕
4、将堆得大小减1，重复步骤2和步骤3，直到堆中只剩下一个元素。排序完毕
上代码：
public class HeapSort {
public static void heapSort(int[] arr){
//建立完全二叉树，从最后一个双亲开始调整双亲值，直到根，调整完毕后大顶堆建立完成
for (int i = arr.length >> ; i > ; i --) {
heapAdjust(arr, i, arr.length);//调用堆要从1到length才符合堆的定义
}
//堆顶和堆低交换,获取最大值,然后调整大顶堆
for (int i = arr.length - ; i > ; i--) {
arr[i] = arr[i]^arr[];
arr[] = arr[i]^arr[];
arr[i] = arr[i]^arr[];
heapAdjust(arr, , i);//因为堆计数要从1开始,所以size = endIndex + 1
}
}
//调整大顶堆.先找左子,然后和右子比,取值大的,在和双亲自己比,自己比儿子大,break,否则交换.注意:根要从1开始才能找到左子
public static void heapAdjust(int[] arr, int parents, int size){
int j;//孩子们的标记是j,索引全部-1
int i = parents;//双亲是i,索引全部-1
while (i << <= size) {
j = i << ;//左子
if (j + <= size) {//有右子
if (arr[j - ] < arr[j + -])
j ++;
}
if (arr[i - ] > arr[j - ])
break;
arr[i-] = arr[i-]^arr[j-];
arr[j-] = arr[i-]^arr[j-];
arr[i-] = arr[i-]^arr[j-];
i = j;//儿子变为父亲,这里不知道是左子还是右子,所以不能直接通过for循环的迭代步骤<<i调整i值,如果是右子的话就错了(右子<<1+1)
}
}
}
再说分治并归排序
这里先要了解什么是递归
public class MergingTest {
public static void main(String[] args) {
mSort(, );
}
private static void mSort(int left, int right) {
int m = (left + right)/;
if (left == right) {
System.out.println(left);
return;
}
mSort(left, m);
mSort(m+, right);
}
}
这几行代码是并归算法的核心。运行代码将输出0123456789，虽然看上去很简单，但是如果真能明白，说明你已经完全理解递归的思想了，写出并归算法也就不在话下了。
为什么会输出0123呢？
代码执行的走向：1→2→4→2→5→2→1→3→6→3→7→3→1→return
能领悟这个东西就好办了，上代码:
public class MergingSort {
public static void mergingSort(int[] arr) {
int[] temp = new int[arr.length];
//temp是相当于一张牌，通过left,m,right在逻辑上分成两个数组，进行分治排序,arr是原数组，对数组排序不传数组怎么行？！
mSort(arr, temp, , arr.length-);
}
private static void mSort(int[] arr, int[] temp, int left, int right) {
//这里的分组逻辑没有使用到temp和arr，而是把它们作为参数传入merge方法
int m = (left+right)/ ;
if (left == right) {
return;
}
mSort(arr, temp, left, m);
mSort(arr, temp, m+, right);
merge(arr,temp,left,m,right);
}
private static void merge(int[]arr, int[] temp, int left, int m, int right) {
//分治排序极其简单，已知两个有序数组，要把他们合并成一个有序数组，用什么方法都不用说，大家一想就知道了。
for (int c = ;c < arr.length;c++){
temp[c] = arr[c];
}
for (int p = ; p < temp.length; p++) {
System.out.println("temp["+p+"] = " + temp[p]);
}
int i = left;
int j = m + ;
int k = left;
while (i<=m && j<=right) {
//使用分支结构，把每摞牌最小的那个挑出来给arr
if (temp[i] < temp[j]) {
arr[k++] = temp[i++];
}
if (temp[j] < temp[i]) {
arr[k++] = temp[j++];
}
}
//使用分支结构，把剩下的那摞牌都塞给arr
if (i > m) {
while (j <= right) {
arr[k++] = temp[j++];
}
}
if (j > right) {
while (i <= m) {
arr[k++] = temp[i++];
}
}
}
}