堆排序算法的思路及C代码实现

1. 概念

堆排序（Heap Sort)是将待排序数组看成一颗完全二叉树的顺序存储，利用完全二叉树中双亲节点和孩子节点的关系，不断筛选其中的大（小）关键字不断上移的过程。

2. 代码思路（以大根堆为例）

  • 设计一个算法HeapAdjust：使传入要重建为堆的根节点（一号），检查比较其与子元素的大小关系。如果子元素（三号）较大就使其上移，子节点（三号）位置不能用根节点元素（一号）补上，因继续以子节点（三号）为根节点往下继续调整为大根堆，直至其为叶节点。
  • 设计一个算法CreateHeap：初始化无序树树为最大根堆。以i = n/2的第一个非叶节点开始，传入HeapAdjust进行局部重建大根堆，依次i--直到根节点。
  • 完整的算法HeapSort：
      1. 先初始化树为最大根堆
      1. 将最大节点（根节点）与尾节点交换位置
      1. 此时破坏了大根堆特性，重新以根节点开始，局部重建大根堆
      1. 重复步骤2，3 （n-1）次，即可得到升序排列的次序

3. 完整代码参考（C语言）

#include <stdlib.h>
#define MAXSIZE 10            // 静态顺序表最大长度

typedef int ElemType;         // 假设数据类型为int类
typedef struct {              // 静态顺序表数据元素
  ElemType data[MAXSIZE + 1]; // 数据项  [0]不放数据
  int length;
}SqList;

void initList(SqList* L) {      // 初始化顺序表
  L->length = MAXSIZE;
  for (int i = 1;i <= L->length;i++) {
    L->data[i] = rand();        // 随机初始化数据
  }
}

void printData(SqList* L) {
  for (int i = 1; i <= L->length; i++) {
    printf("%d ", L->data[i]);
  }
  puts();
}

void HeapAdjust(SqList* L, int k, int len) {     // 将以k为根节点的子树调整为大根堆
  L->data[0] = L->data[k];                       // 暂存子树的根节点
  for (int j = 2 * k;j <= len; j *= 2) {         // 沿着k较大的子节点往下筛选
    if (j < len && L->data[j] < L->data[j + 1])  // j<length 防止没有右节点
      j++;                                       // 将j指向节点较大的数组下标
    if (L->data[0] >= L->data[j]) break;         // 若根节点此时大于等于右节点，跳出循环
    else {
      L->data[k] = L->data[j];
      k = j;                                     // 将k重置为子树交换的节点，以便后续调整该节点为大根堆
    }
    L->data[k] = L->data[0];
  }
}

void CreateHeap(SqList* L) {            // 把无序列表建成大根堆
  int len = L->length;
  for (int i = len / 2;i > 0;i--) {     // n/2为二叉排序树中最接近的叶节点的元素，依次往上扫描
    HeapAdjust(L, i, len);
  }
}

void HeapSort(SqList* L) {              // 对顺序表进行堆排序
  CreateHeap(L);
  puts("第一次初始化大根堆：");
  printData(L);
  for (int i = L->length;i > 1;i--) {   // 进行n-1次交换和重建堆过程
    ElemType temp = L->data[i];         // 将最大(根元素）与表的最后一个元素交换
    L->data[i] = L->data[1];
    L->data[1] = temp;
    HeapAdjust(L, 1, i - 1);            // 重新把树整理为堆
    printf("第%d次整理大根堆：\n", L->length - i + 1);
    printData(L);
  }
}

void main() {
  SqList L;
  initList(&L);
  printData(&L);
  HeapSort(&L);
}

4. 后记

实现了这个算法花了我三小时差不多时间，其中对C代码也不是很熟，写惯了JavaScript里面调用函数直接传入字符串就行，c语言里面却行不通，想往函数里面传入字符串不知道怎么穿，有大佬看见希望评论教我一下。好久没写博客，今天先水一期。