堆排序，以及大顶堆构造过程Java实现

import java.util.Arrays;public class Main {public static void main(String[] args) {int a[] = new int[] { 1, 1, 23, 456, 0 };// int a初始化方式int bb[] = { 1, 2, 3, 4 };// int c[5] = {1,2,34,5,6};//错误int d[] = new int[6]; // 初始为0// int e[] = new int[5]{1,2,34,52,2}; 错误int f[] = new int[] { 1, 2, 3, 4, 5, 6 };for (int i = 0; i != 6; ++i) {System.out.println("ay i=" + d + ",value=" + d[i]);}System.out.println("------------");// Arrays.fill(a, 0, 6, 1);Arrays.parallelSort(a, 0, 5);// 快速升序排序for (int i = 0; i != 5; ++i) {System.out.println("ay i=" + i + ",value=" + a[i]);}int[] b = Arrays.copyOfRange(a, 1, 7);// Array是copy，是浅copy,from需要小于长度，to超过长度将初始化为0for (int i = 0; i != 6; ++i) {System.out.println("by i=" + i + ",value=" + b[i]);}int heap_max[] = { 111, 2121, 222, 113, 11111114, 5111, 1, 3, 24, 1, 213, 123 };// maxHeap(heap_max, 5);int size = 12;while (size > 0) {maxHeap(heap_max, size);int last = heap_max[size - 1];heap_max[size - 1] = heap_max[0];heap_max[0] = last;size--;}}static void maxHeap(int a[], int size) {int last_index = size - 1;// 自下而上检测while (last_index > 0) {int root_index = last_index / 2;if (last_index % 2 == 0) {root_index = root_index - 1;} else {}int root = a[root_index];int left = a[root_index * 2 + 1];int right = 0;if (root_index * 2 + 2 < size) {right = a[root_index * 2 + 2];}if (root < left) {if (left < right) {int rc = root;a[root_index] = right;a[root_index * 2 + 2] = rc;} else {int rc = root;a[root_index] = left;a[root_index * 2 + 1] = rc;}} else {if (root < right) {int rc = root;a[root_index] = right;a[root_index * 2 + 2] = rc;}}last_index -= 2;// System.out.println(Arrays.toString(a));}// 自上而下检测所有根节点int index = 0;while (index < size) {int root_index = index;int root = a[root_index];int left_index = root_index * 2 + 1;int left = 0;if (left_index < size) {left = a[left_index];} else {left = -1;break;}int right_index = root_index * 2 + 2;int right = 0;if (right_index < size) {right = a[right_index];} else {right = -1;break;}if (root < left) {if (left < right) {int rc = root;a[root_index] = a[right_index];a[right_index] = rc;} else {int rc = root;a[root_index] = a[left_index];a[left_index] = rc;}} else {if (root < right) {int rc = root;a[root_index] = a[right_index];a[right_index] = rc;}}index++;// System.out.println(Arrays.toString(a));}System.out.println(Arrays.toString(a));}
}

先上代码，堆排序一直是稀里糊涂的。找了视频，一看就明白了，自己动手撸了一下。

一般用数组构建一种堆的关系。在数组中

每个根节点的下标

root_index = left_child_index/2

root_index = right_child_index/2 -1;

left_child_index = 2*root_index+1;

right_child_index = 2*root_index+2;

记住这个关系，然后按照i堆的构建顺序执行：

1.   构建2叉树，即按照上述位置关系构建

2.  自下而上检测：

         依次从最后一个节点开始，查找每个节点的根节点，然后根据根节点，继续找出左右子节点，在三个节点中取最大值和根节点交换位置

3.  自上而下检测

        依次从一个节点开始，查找每个节点的左右子节点，在三个节点中取最大值和根节点交换位置

记住这三条顺序，就行了。

Tips:

     具体编码建议，在第二步中，如果依次遍历，将会存在大量重复计算节点的操作。因为是从叶节点开始，那么每个节点有两个叶节点，就会找两次，所以每次找完，下标-2就行，直接进入下一个根节点

        第三步中，有可能找不到叶节点，当找不到左右节点时，直接跳出循环就行了，说明已经将所有的根节点找完了。根找完了，就说明调整完毕。

最后是打印的顺序。

[11111114, 2121, 5111, 113, 213, 222, 1, 3, 24, 1, 111, 123]
[5111, 2121, 222, 113, 213, 123, 1, 3, 24, 1, 111, 11111114]
[2121, 213, 222, 113, 111, 123, 1, 3, 24, 1, 5111, 11111114]
[222, 213, 123, 113, 111, 1, 1, 3, 24, 2121, 5111, 11111114]
[213, 113, 123, 24, 111, 1, 1, 3, 222, 2121, 5111, 11111114]
[123, 113, 3, 24, 111, 1, 1, 213, 222, 2121, 5111, 11111114]
[113, 111, 3, 24, 1, 1, 123, 213, 222, 2121, 5111, 11111114]
[111, 24, 3, 1, 1, 113, 123, 213, 222, 2121, 5111, 11111114]
[24, 1, 3, 1, 111, 113, 123, 213, 222, 2121, 5111, 11111114]
[3, 1, 1, 24, 111, 113, 123, 213, 222, 2121, 5111, 11111114]
[1, 1, 3, 24, 111, 113, 123, 213, 222, 2121, 5111, 11111114]
[1, 1, 3, 24, 111, 113, 123, 213, 222, 2121, 5111, 11111114]

堆排序的过程。

第一步：
    每次用数组中的[0，N)个元素构建堆。构建结束后，最大的数位于0下标位置。

第二步：将0下标和数组中最后一个元素交换位置。交换后，最大的数位于最后一个位置上

第三步：N=N-1 ，重复第一步，N=1跳出循环就行了

总结：

还是用java刷题爽，用C++没那么方便。后面干到200题去面MS