Please enable Javascript to view the contents

排序算法之堆排序

 ·  ☕ 2 分钟

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法:

  1. 大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列;
  2. 小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列;

一、排序步骤

  1. 构造初始堆。将给定无序序列构造成一个大顶堆(一般升序采用大顶堆,降序采用小顶堆);
  2. 将堆顶元素与末尾元素进行交换,使末尾元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换,得到第二大元素。如此反复进行交换、重建、交换;

二、动画演示

heap_sort

三、代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package com.whoismy8023.learning.sort;

import java.util.Arrays;

/**
 * Created by SPPan on 2019/9/9.
 */
public class HeapSortLearning {

    public static void main(String[] args) {
        int[] arr = {1, 9, 2, 8, 3, 6, 5, 4};
        System.out.printf("排序前:%s \n", Arrays.toString(arr));
        heapSort(arr);
        System.out.printf("排序后:%s \n", Arrays.toString(arr));
    }

    //堆排序
    private static void heapSort(int[] arr) {
        // 堆创建,第一个元素是最大的
        buildMaxHeap(arr);
        for (int i = arr.length - 1; i > 0; i--) {
            // 将堆顶元素和堆底元素进行交换
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            adjustDownToTop(arr, 0, i);
        }
    }

    // 创建大根堆
    private static int[] buildMaxHeap(int[] arr) {
        // 从最后一个父结点开始
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustDownToTop(arr, i, arr.length);
        }
        return arr;
    }

    private static void adjustDownToTop(int[] arr, int k, int length) {
        // 提取该父结点的值存入temp中
        int temp = arr[k];
        // 初始化k结点的左孩子结点为i
        for (int i = 2 * k + 1; i <= length - 1; i = 2 * i + 1) {
            // 选取值最大的子结点的下标(注意该结点可能没有右子结点,所以判断条件为i+1<length.不能等于)
            if (i + 1 < length && arr[i] < arr[i + 1]) {
                // 如果右结点值大于左结点
                i++;
            }
            // 如果比父结点大,和父结点交换位置
            if (arr[i] <= temp) {
                break;
            } else {
                arr[k] = arr[i];
                //用于最后的赋值
                k = i;
            }
        }
        arr[k] = temp;
    }
}

四、代码演示结果

1
2
排序前:[1, 9, 2, 8, 3, 6, 5, 4] 
排序后:[1, 2, 3, 4, 5, 6, 8, 9] 
目录