【项目实战】排序算法之堆排序

绝地灬酷狼 2024-03-23 19:04 3阅读 0赞

## 一、堆是什么？ ##

堆是一种数据结构  
堆具有以下特性：是一个完全二叉树，且在一个最大堆的所有父节点的值都要大于或等于其子节点的值，最小堆的所有父节点的值都要小于或等于其子节点的值。

## 二、堆排序是什么？ ##

堆排序是一种高效的排序算法。  
堆排序是一种原地的、概率为O(nlogn)的排序算法。  
堆排序基于二叉堆的数据结构进行实现。

堆排序的基本思想是：通过不断地将最大堆或最小堆的堆顶元素与其子节点中的最大或最小元素交换，使得堆顶元素始终为最大或最小的，从而实现对数组的排序。

堆排序算法设计思想：利用堆数据结构，将一组数据按照一定的顺序排列，从而实现排序的目的。

## 三、堆排序的主要步骤 ##

以下是堆排序的基本步骤：

### 3.1 构建最大堆或最小堆 ###

将待排序的序列构造成一个最大堆，即每个节点都比其子节点大。

从数组的第一个元素开始，到达数组的末尾为止，将数组分为两个部分，其中第一个元素到第(k/2-1)个元素构成一个最大堆，第(k/2-1)个元素到数组的末尾构成一个最小堆。

### 3.2 交换堆顶元素（交换根节点） ###

将最大堆的堆顶元素与其子节点中的最大元素交换，将最小堆的堆顶元素与其子节点中的最小元素交换。

将最大堆的根节点（即最大值）与序列的最后一个元素交换位置。

### 3.3 重新构建最大堆 ###

将剩余的序列重新构造成一个最大堆。

### 3.4 递归地构建堆（重复步骤2和3） ###

对于剩余的堆部分，重复执行步骤2和3步骤，直到整个数组/序列都排序完毕。

## 四、用Java实现堆排序的例子 ##

import java.util.Arrays;
    
    public class HeapSort {
        
        public static void main(String[] args) {
        
            int[] nums = {
        8, 5, 3, 7, 1, 9, 6, 4};
            heapSort(nums);
            System.out.println(Arrays.toString(nums));
        }
    
        // 构建最大堆
        public static void buildMaxHeap(int[] nums, int left, int right) {
        
            int largest = left; // 最大堆的堆顶元素
            int parent = (left + right) / 2; // 父节点的位置
            for (int i = left + 1; i <= right; i++) {
        
                if (i > largest) {
        
                    break; // 已经找到了最大元素，退出循环
                }
                if (nums[i] > nums[largest]) {
        
                    largest = i; // 更新最大堆的堆顶元素
                }
                swap(nums[parent], nums[largest]); // 将最大堆的堆顶元素与其子节点中的最大元素交换
                parent = (left + right) / 2; // 更新父节点的位置
            }
        }
    
        // 交换堆顶元素
        public static void swap(int[] nums, int left, int right) {
        
            int temp = nums[left]; // 需要交换的元素
            nums[left] = nums[right]; // 将堆顶元素与其子节点中的最大元素交换
            nums[right] = temp; // 将需要交换的元素放到堆顶
        }
    
        // 堆排序
        public static void heapSort(int[] nums) {
        
            int n = nums.length;
            for (int i = n / 2 - 1; i >= 0; i--) {
        
                buildMaxHeap(nums, 0, i); // 交换堆顶元素
            }
            for (int i = n - 1; i >= 0; i--) {
        
                swap(nums[0], nums[i]); // 将堆顶元素与数组中的最后一个元素交换
                buildMaxHeap(nums, 0, i); // 递归地构建最大堆
            }
        }
    }

输出结果为：  
\[1, 3, 4, 5, 6, 7, 8, 9\]