堆排序算法(选择排序改进)

堆排序算法是一种基于二叉堆的选择排序改进算法。它利用了二叉堆的特点，可以将排序时间降至O(nlogn)级别。下面我们来详细讲解它的完整攻略。

基本思路

1. 将待排序的序列构建成一个最大堆。
2. 将堆顶的元素（即当前最大元素）跟数组最后一个元素交换位置，然后将剩余的元素进行堆调整，使其满足最大堆的要求。
3. 重复步骤2，直至排序完成。

步骤详解

1. 构建最大堆

对于一个长度为n的待排序序列，其构建最大堆的过程可以详细分为以下几步：

1. 从最后一个非叶子节点开始（即n/2-1处），对每一个非叶子节点执行“下沉”操作，使其满足最大堆的性质。下沉操作的具体方式就是找到当前节点的两个子节点中较大的那个，如果当前节点比这个较大的子节点小，则将它与子节点交换位置并继续向下进行下沉操作。
2. 重复步骤1，直至将整个序列转换成了最大堆。

以下示例对长度为10的序列进行最大堆构建的过程进行了演示：

        4
     /     \
    2       7
   / \     / \
  1   3   8   9
 / \
5   6

After max-heapify(1):         
        4
     /     \
    6       7
   / \     / \
  1   3   8   9
 / \
5   2

After max-heapify(0): 
        7
     /     \
    6       4
   / \     / \
  1   3   8   9
 / \
5   2

max-heapify(2):     after swap 3&9    
        7
     /     \
    6       9
   / \     / \
  1   3   8   4    after swap 1&8
 / \
5   2

max-heapify(1): 
        9
     /     \
    6       8
   / \     / \
  1   3   7   4   after swap 6&7
 / \
5   2

max-heapify(0): 
        9
     /     \
    6       8
   / \     / \
  5   3   7   4   after swap 5&9
 / \
1   2

max-heapify(0): 
        8
     /     \
    6       7
   / \     / \
  5   3   1   4   after swap 1&8
 / \
2   9

after build-max-heap: 

        9
     /     \
    6       8
   / \     / \
  5   3   7   4
 / \
1   2

2. 排序

最大堆构建好后，算法的排序过程其实就是不断地将当前的最大元素放到序列的末尾，然后将未排序的序列（即除去末尾元素之外的元素）重新调整成一个最大堆。

以下示例对长度为10的序列进行了排序的过程进行了演示：

```
9
/ \
6 8
/ \ / \
5 3 7 4
/ \
1 2

After extract-max(9):

    8
 /     \
6       7

/ \ / \
5 3 2 4
/ \
1 9

After max-heapify(0):

    7
 /     \
6       2

/ \ / \
5 3 1 4
/ \
8 9

After extract-max(7):

    6
 /     \
5       2

/ \ / \
4 3 1 8
/ \
7 9

After max-heapify(0):

    5
 /     \
4       2

/ \ / \
1 3 6 8
/ \
7 9

......

After extract-max(1):

    2
 /     \
1       3

/ \ / \
4 7 6 8
/ \
5 9

After max-heapify(0):

    1
 /     \
4       3

/ \ / \
5 7 6 8
/ \
2 9

After extract-max(1):

    3
 /     \
4       6

/ \ / \
5 7 9 8
/ \
2 1

After max-heapify(0):

    2
 /     \
4       1

/ \ / \
5 7 9 8
/ \
3 6

After extract-max(2):

    1
 /     \
4       6

/ \ / \
5 7 9 8
/ \
2 3

After max-heapify(0):

    1
 /     \
5       6

/ \ / \
4 7 9 8
/ \
2 3

......

最终，序列就被排序完成了。

时间复杂度

由于在构建最大堆的过程中，每个节点都要下沉到各自的深度，则构建最大堆的时间复杂度为O(n)。排序过程中每次交换操作需要O(logn)的时间，因此总的时间复杂度为O(nlogn)。

参考文献

1. 《算法导论》

以上就是堆排序算法的完整攻略，如果还有不明白的地方，请随时联系我。