堆排序

发表于   |   分类于 ， ，

The heapsort algorithm involves preparing the list by first turning it into a max heap. The algorithm then repeatedly swaps the first value of the list with the last value, decreasing the range of values considered in the heap operation by one, and sifting the new first value into its position in the heap. This repeats until the range of considered values is one value in length. - - - - wikipedia

The steps are:

  1. Call the buildMaxHeap() function on the list. Also referred to as heapify(), this builds a heap from a list in $O(n)$ operations.
  2. Swap the first element of the list with the final element. Decrease the considered range of the list by one.
  3. Call the siftDown() function on the list to sift the new first element to its appropriate index in the heap.
  4. Go to step (2) unless the considered range of the list is one element.

The buildMaxHeap() operation is run once, and is $O(n)$ in performance. The siftDown() function is $O(log(n))$, and is called $n$ times. Therefore, the performance of this algorithm is $O(n + n * log(n))$ which evaluates to $O(n log n)$.

分析

首先将列表变为大根堆，之后将根节点和最后一个叶子节点进行交换，堆大小减一，再维护堆，重复操作，直至大根堆为空，此时列表已经有序

这里建堆采用 siftDown() 的方式，从后（最后一个非叶子节点）往前（根节点）遍历，这过程中，使得每一个子堆都满足要求，直至整个堆满足要求

特点

  • 基于完全二叉树
  • 不稳定的排序
  • 时间复杂度（最佳）： $O(n log(n))$
  • 时间复杂度（平均）： $O(n log(n))$
  • 时间复杂度（最差）： $O(n log(n))$
  • 空间复杂度（最差）： $O(1)$ auxiliary

代码

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
62
63
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);

        int n = input.nextInt();
        int[] nums = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            nums[i] = input.nextInt();
        }

        heapSort(nums, nums.length - 1);

        for (int i = 1; i <= n; i++) {
            System.out.print(nums[i] + " ");
        }
    }

    public static void siftDown(int nums[], int i, int len) {

        int left = 2 * i;
        int right = left + 1;

        if (left <= len) {
            int max = i;
            if (nums[left] > nums[max]) {
                max = left;
            }
            if (right <= len && nums[right] > nums[max]) {
                max = right;
            }
            if (max != i) {
                int t = nums[i];
                nums[i] = nums[max];
                nums[max] = t;
                siftDown(nums, max, len);
            }
        }
    }

    public static void buildMaxHeap(int nums[], int len) {

        for (int i = len / 2; i >= 1; i--) {   // 从最后一个非叶子结点开始遍历
            siftDown(nums, i, len);
        }
    }

    public static void heapSort(int nums[], int len) {

        buildMaxHeap(nums, len);

        for (int i = len; i >= 1; i--) {
            int t = nums[i];
            nums[i] = nums[1];
            nums[1] = t;
            siftDown(nums, 1, i - 1);
        }
    }
}