堆排序，以及大顶堆构造过程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超过长度将初始化为0
        for (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