(精华)2020年8月28日 数据结构与算法解析(选择排序-堆排序)

1、堆排序（Heap Sort）

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

1.1 算法描述

• 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
• 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
• 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

1.2 动图演示

1.3 代码实现

/// <summary>
/// 堆排序
/// </summary>
public class Program {

    public static void Main(string[] args) {
        int[] array = { 43, 69, 11, 72, 28, 21, 56, 80, 48, 94, 32, 8 };

        HeapSort(array);
        ShowSord(array);

        Console.ReadKey();
    }

    private static void ShowSord(int[] array) {
        foreach (var num in array) {
            Console.Write($"{num} ");
        }
        Console.WriteLine();
    }

    private static void HeapSort(int[] array) {
        MaxHeap(array);
        for (int i = array.Length - 1; i > 0; i--) {
            Swap(ref array[0], ref array[i]);
            Heapify(array, 0, i);
        }
    }

    private static void MaxHeap(int[] array) {
        for (int i = array.Length / 2 - 1; i >= 0; i--) {
            Heapify(array, i, array.Length);
        }
    }

    private static void Heapify(int[] array, int index, int size) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int large = index;

        if (left < size && array[left] > array[large]) {
            large = left;
        }
        if (right < size && array[right] > array[large]) {
            large = right;
        }
        if (index != large) {
            Swap(ref array[index], ref array[large]);
            Heapify(array, large, size);
        }
    }

    private static void Swap(ref int first, ref int second) {
        int t = first;
        first = second;
        second = t;
    }

}

  

 

  
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
 

堆排序算法的时间复杂度不难证明为： O(n*logn) 。

文章来源: codeboy.blog.csdn.net，作者：愚公搬代码，版权归原作者所有，如需转载，请联系作者。

原文链接：codeboy.blog.csdn.net/article/details/108203717