首页 > 代码库 > 排序算法——堆排序

排序算法——堆排序

  堆排序是将给定的序列看成完全二叉树的顺序存储结构来进行排序

  在学习堆排序之前,先了解一下完全二叉树的一个性质:

  给定一颗完全二叉树bt,采用顺序存储结构来进行存储,那么如何表示父结点与左右孩子结点之间的关系呢?

  下面分两种情况:

  (a).如果从下标为0的位置开始存储,那么对于下标为i的结点,其左孩子的下标为2i+1,右孩子的下标为2i+2,父结点的下标为(i-1)/2

  (b).如果从下标为1的位置开始存储,那么对于下标为i的结点,其左孩子的下标为2i,右孩子的下标为2i+1,父结点的下标为i/2

  为了满足我们从下标为0开始存储的习惯,这里采用第一种方式。由此,可以定义堆:给定一个序列K0、K1、...、Kn-1,如果满足K≤ K2i+1且K≤ K2i+2,

则称之为小根堆;如果满足K≥ K2i+1且K≥ K2i+2,则称之为大根堆

  上面所述为堆的基本概念和相关知识,现在我们讨论大根堆的排序

  对于一个大根堆而言,其根结点便是最大元素,选择出最大元素,将其与序列的最后一个元素进行交换,这样最大的元素便成功归位。但是此时堆的结构

遭到了破坏,需要重新调整元素的位置,使其再次满足堆的性质。所以,对于堆排序来说,堆的调整算法是其核心和本质

  堆的调整算法:

#include <stdio.h>
#include <stdlib.h>

void Adjustment(int A[], int s, int t)
{
    int i, j, temp;
    i = s;
    j = 2*i+1;                      // j为左孩子的下标
    temp = A[i];                    // 辅助变量temp保存父结点的值
    while(j <= t)
    {
        if(j < t && A[j] < A[j+1])
            j++;                    // 如果右孩子大于左孩子,则让j保存右孩子的下标
        if(temp < A[j])             // 如果父结点的值小于孩子结点的值
        {
            A[i] = A[j];            // 则将让孩子结点交换到父结点的位置
            i = j;
            j = 2*i + 1;
        }
        else
            break;                  // 满足大根堆的性质,跳出循环
    }
    A[i] = temp;                    // 将保存的原父结点的值插入到适当的位置
}

  在建立初始堆的时候,需要从最后一个非叶子结点开始由后向前进行调整,直到整个序列都满足堆的性质。此时,根结点为最大元素,将根结点与最后一个叶子结点

交换位置,使最大元素归位,但是破坏了堆的结构,因此需要在剩下的n-1个元素调用堆的调整算法进行调整,如此反复,直到元素都有序。

  堆排序算法实现如下:

void HeapSort(int A[], int n)
{
    int i, temp;
    for(i=n/2-1; i>=0; i--)         // 从最后一个非叶子结点开始调整,因此i初始为n/2-1
        Adjustment(A, i, n-1);      // 调用堆的调整算法
    for(i=n-1; i>=1; i--)           // 进行n-1趟排序
    {
        temp = A[0];                // 辅助变量temp用来保存根结点的值
        A[0] = A[i];                // 将根结点值与叶子结点交换
        A[i] = temp;
        Adjustment(A, 0, i-1);      // 此时最大元素归位,对剩下的n-1个元素调用堆的调整算法,重新调整为大根堆
    }
}

  堆排序的时间复杂度为O(nlog2n),空间复杂度为O(1),是一种不稳定的排序算法。

排序算法——堆排序