首页 > 编程语言 >数据结构与算法分析(Java语言描述)(13)—— 原地堆排序

数据结构与算法分析(Java语言描述)(13)—— 原地堆排序

时间:2023-06-06 22:07:17浏览次数:51  
标签:13 Java int 堆排序 arr System println 节点 out


package com.algorithm.sort;

public class HeapSortInPlace {
    private HeapSortInPlace() {
    }

    public static void sort(Integer[] arr) {
        int n = arr.length;

        // 注意:我们堆的索引是从0开始的
        // 从(最后一个元素的索引-1)/2 开始
        // 最后一个元素的索引为 n-1

        // 将数组原地 shiftDown 变为 最大堆
        for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
            shiftDown(arr, n, i);
        }
        // 交换数组的第一个元素(最大元素)与数组末尾的元素(i)
        // 使整个数组从后向前依次有序
        // 对剩余的数组进行 shiftDown 操作,使其变为 最大堆
        for (int i = n - 1; i > 0; i--) {
            SortTestHelper.swap(arr, 0, i);
            shiftDown(arr, i, 0);
        }
    }

    private static void shiftDown(Integer[] arr, int n, int k) {
        // 当存在 左子节点 时
        while (2 * k + 1 < n) {

            // j 为 左子节点
            int j = 2 * k + 1;

            // 右子节点(j+1)存在,且 右子节点 > 左子节点
            if (j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0) {
                // j 移动到 右子节点处
                j++;
            }

            // 父节点(k) > 子节点中较大者, break
            if (arr[k].compareTo(arr[j]) >= 0) break;

            // 父节点(k) 与 子节点中较大者进行交换
            SortTestHelper.swap(arr, j, k);

            // k 移动到 子节点中 较大者 的位置(j)
            k = j;
        }
    }

    public static void main(String[] args) {
        int N = 100000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);

        System.out.println("排序前的数组为:");
        SortTestHelper.printArray(arr);
        Long start = System.currentTimeMillis();
        HeapSortInPlace.sort(arr);
        Long end = System.currentTimeMillis();
        System.out.println("-------------------------------------------");

        System.out.println("排序后的数组为:");
        SortTestHelper.printArray(arr);
        System.out.println("-------------------------------------------");

        System.out.println("排序后的数组是否有序:");
        if (SortTestHelper.isSorted(arr)) {
            System.out.println("数组有序~");
        } else {
            System.out.println("数组无序!");
        }
        System.out.println("-------------------------------------------");

        System.out.println("排序算法的运行时间为" + " : " + (end - start) + "ms");
    }

}

数据结构与算法分析(Java语言描述)(13)—— 原地堆排序_算法

数据结构与算法分析(Java语言描述)(13)—— 原地堆排序_堆排序_02

数据结构与算法分析(Java语言描述)(13)—— 原地堆排序_算法_03

数据结构与算法分析(Java语言描述)(13)—— 原地堆排序_数据结构_04


标签:13,Java,int,堆排序,arr,System,println,节点,out
From: https://blog.51cto.com/u_16152603/6428501

相关文章