你好！堆排序【JAVA】

目录

1.简单介绍

2.大小顶堆?

?3.基本思想

4.基本思路

4.代码实现数组转化堆

5.代码排序

6.总代码+测试

---

1.简单介绍

堆排序是一种基于堆数据结构的排序算法，其核心思路是利用堆这种特殊的数据结构来对数据进行排序。堆是一种完全二叉树，并且满足父节点的值大于等于（或小于等于）其子节点的值。

2.大小顶堆?

?

• 大顶堆：当前节点的值大于其左子节点和右子节点的值
• 大顶堆特点:arr[i]>=arr[2*i+1] && arr[i]>=arr[2*i+2]
• 小顶堆：当前节点的值小于其左子节点和右子节点的值
• 小顶堆特点:arr[i]<=arr[2*i+1] && arr[i]<=arr[2*i+2]

注：升序采用大顶堆，降序采用小顶堆

?3.基本思想

• 1.建堆：首先将待排序的数组看作一棵完全二叉树，然后对树中每个非叶子节点进行堆化，即将其和其子节点的值进行比较，将较大（或较小）的值放到父节点上，然后递归地对子节点进行堆化，直到整个树变为一个堆。
• 2.排序：排序的过程就是不断将堆顶的元素（最大值或最小值）取出并放到已经排好序的数组的末尾，然后将堆进行调整，保证堆的性质不变。不断取出堆顶元素并进行调整，直到堆为空，排序完成。

4.基本思路

• 1.将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆；
• 2.将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;
• 3.重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤，直到整个序列有序。

4.代码实现数组转化堆

1.建堆

    /**
     * 将数组，调整一个大顶堆
     *
     * @param array:待调整的数组
     * @param i：非叶子节点在数组中的索引
     * @param length：表示对多少个元素进行调整，length逐减
     */
    public static void adjustHeapSort(int[] array, int i, int length) {
        int temp = array[i];//定义临时变量，保存当前值
        //调整
        //1.k=i*2+1:表示i节点的左子节点
        for (int k = i * 2 + 1; k < length; k = i * 2 + 1) {
            if (k + 1 < length && array[k] < array[k + 1]) {//说明左子节点小于右子节点
                k++;//k指向右子节点
            }
            if (array[k] > temp) {//子节点大于父节点，进行交换
                array[i] = array[k];//子节点赋给父节点
                i = k;
            } else {
                break;
            }
        }
        //结束for循环，已经将以i为父节点的树的最大值，放在了最顶端
        array[i] = temp;//将temp放到最后调整的位置
    }

5.代码排序

2.排序

        for (int j = array.length - 1; j > 0; j--) {
            int temp = array[j];
            array[j] = array[0];
            array[0] = temp;
            adjustHeapSort(array, 0, j);
        }

6.总代码+测试

 public static void main(String[] args) {
        int[] array = new int[]{4, 6, 8, 5, 9, 10, 7, -2};
        heapSort(array);
    }

    public static void heapSort(int[] array) {
        System.out.println("============分步代码============");
        adjustHeapSort(array, 1, array.length);
        System.out.println("第一次:" + Arrays.toString(array));
        adjustHeapSort(array, 0, array.length);
        System.out.println("第二次:" + Arrays.toString(array));

        //数组转化大顶堆
        System.out.println("============总代码=============");
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            adjustHeapSort(array, i, array.length);
        }
        System.out.println("转换后大顶堆:" + Arrays.toString(array));

        for (int j = array.length - 1; j > 0; j--) {
            int temp = array[j];
            array[j] = array[0];
            array[0] = temp;
            adjustHeapSort(array, 0, j);
        }

        System.out.println("==========从小到大排序===========");
        System.out.println("从小到大:" + Arrays.toString(array));
    }

    /**
     * 将数组，调整一个大顶堆
     *
     * @param array:待调整的数组
     * @param i：非叶子节点在数组中的索引
     * @param length：表示对多少个元素进行调整，length逐减
     */
    public static void adjustHeapSort(int[] array, int i, int length) {
        int temp = array[i];//定义临时变量，保存当前值
        //调整
        //1.k=i*2+1:表示i节点的左子节点
        for (int k = i * 2 + 1; k < length; k = i * 2 + 1) {
            if (k + 1 < length && array[k] < array[k + 1]) {//说明左子节点小于右子节点
                k++;//k指向右子节点
            }
            if (array[k] > temp) {//子节点大于父节点，进行交换
                array[i] = array[k];//子节点赋给父节点
                i = k;
            } else {
                break;
            }
        }
        //结束for循环，已经将以i为父节点的树的最大值，放在了最顶端
        array[i] = temp;//将temp放到最后调整的位置
    }