堆排序Java实现（大堆）

阳光穿透心脏的1/2处 2023-07-07 03:41 121阅读 0赞

## Java实现堆排序（建立大堆的形式） ##

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。  
**堆中定义以下几种操作：**

**最大堆调整**：将堆的末端子节点作调整，使得子节点永远小于父节点。  
**创建最大堆**：将堆中的所有数据重新排序。  
**堆排序**：移除位在第一个数据的根节点，并做最大堆调整的递归运算。

**代码如下：**

import java.util.Arrays;
    public class HeapSort {
        
        public static void main(String[] args) {
        
            int[] arr = new int[]{
        6, 8, 3, 4, 1, 9, 0, 12, 7, 5};
            System.out.println(Arrays.toString(arr));
            heapSort(arr);
            System.out.println(Arrays.toString(arr));
        }
    //堆排序
        private static void heapSort(int[] arr) {
        
            if (arr.length <= 1 ) {
        
                return;
            }
            buildMaxHeap(arr);//建立大堆
            for (int i = arr.length - 1; i >= 1; i--) {
        
                swap(arr, 0, i);//进行交换
                maxHeap(arr, i, 0);//在进行建立大堆
            }
        }
    //建立大堆
        private static void buildMaxHeap(int[] arr) {
        
            int half = (arr.length-1)/2;
            for (int i = half; i >=0; i--) {
        
                maxHeap(arr,arr.length,i);
            }
        }
    //进行交换
        private static void swap(int[] arr, int i, int j) {
        
            int tmp = arr[j];
            arr[j] = arr[i];
            arr[i] = tmp;
        }
    //length 为 每次建立大堆的数组长度  i为从哪开始
        private static void maxHeap(int[] arr, int length, int i) {
        
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int max = i;
            if (left < length && arr[i] < arr[left]) {
        
                max = left;
            }
            if (right < length && arr[max] < arr[right]) {
        
                max = right;
            }
            if (max != i) {
        
                swap(arr, max, i);
                maxHeap(arr, length, max);
            }
        }
    
    }