C语言实现堆排序算法：原理与完整代码解析

夏知夏

发布时间：2026-10-14| 4人浏览过

原创

堆排序利用完全二叉树的父子节点数值关系，通过反复“建堆”和“交换根节点与末尾元素”来实现高效排序。本文将解析其核心思想，并给出C语言的完整实现代码。

算法思路与时间复杂度

堆排序是一种树形选择排序方法，它是对直接选择排序的有效改进。其核心在于构建满足特定条件的“堆”。在计算机科学中，通常讨论的是大顶堆（Max Heap），即父节点的键值总是大于或等于其子节点的键值。对于具有 $n$ 个元素的序列 $(h_1, h_2, …, h_n)$，当且仅当满足以下条件时称之为大顶堆：

$h_i \ge h_{2i}$
$h_i \ge h_{2i+1}$

其中 $i=1, 2, …, n/2$。直观上看，如果把序列看作一棵完全二叉树，堆顶元素（数组的第一个元素）必然是整个序列中的最大值。
堆排序的主要过程包含两个步骤：

建立初始堆：将无序序列调整为一个大顶堆，此时堆顶为最大值。
交换与重建：将堆顶元素与堆的最后一个元素交换，使最大值位于有序区间；然后对剩余未排序部分重新调整为大顶堆。重复此过程直到完成排序。

由于该算法涉及多次比较和下沉操作，它是不稳定的排序算法。其平均和最坏情况下的时间复杂度均为 O(n log₂n)。

C语言完整实现代码

以下是完整的 C 语言实现。代码主要包含三个部分：用于向下调整堆结构的 sift 函数，主排序逻辑 heap_sort 函数以及测试用的 main 函数。

void sift(int *x, int n, int s){
  int t, k, j;
  t = *(x+s);
  k = s;
  j = 2*k + 1;

  while (j < n) {
    if (j < n - 1 && *(x+j) < *(x+j+1)) {  // 找到较大的子节点
      j++;
    }
    if (t < *(x+j)){
      *(x+k) = *(x+j);       // 子节点上移
      k = j;
      j = 2*k + 1;
    } else {
      break;
    }
  }
  *(x+k) = t;                 // 放入正确位置
}

void heap_sort(int *x, int n){
  int i, k, t;
  // 第一步：从最后一个非叶子节点开始向前调整，建立初始堆
  for (i=n/2-1; i>=0; i--){
    sift(x,n,i);
  }
  // 第二步：重复交换堆顶和末尾元素，并重新调整剩余堆
  for (k=n-1; k>=1; k--){
    t = *(x+0);
    *(x+0) = *(x+k);
    *(x+k) = t;
    sift(x,k,0);
  }
}

void main(){
  #define MAX 4
  int *p, i, a[MAX];

  p = a;
  printf("Input %d number for sorting :\n",MAX);
  for (i=0; i<MAX; i++){
    scanf("%d",p++);
  }
  printf("\n");

  p = a;
  select_sort(p,MAX);
  for (p=a, i=0; i++){
    printf("%d ",*p++);
  }
  printf("\n");
  system("pause");
}