堆排序（Heap Sort）是一种利用堆数据结构，实现的比较高效的排序算法，它的时间复杂度为O(nlogn)。堆排序的基本思想可以概括为下面三个步骤：

1. 构建初始堆：将待排序序列构造成一个堆，称为初始堆。在这里我们采用最大堆，也就是父节点的元素值大于或等于其子节点。

2. 对堆进行排序：取出当前堆的根节点(最大值)，并将其与堆的最后一个节点进行互换。移除最后一个节点，然后对剩余的堆进行调整，使其重新成为一个堆。重复此过程，直到堆中仅剩下根节点。

3. 得到有序序列：当堆中仅剩下根节点时，整个堆也变成了有序序列。

堆排序的过程可以看作是不断将最大的元素移到序列的末尾，因此称其为选择排序的一种。

堆排序需要实现两个基本操作：

从一个无序序列构建一个堆和在输出堆顶元素后，调整堆。

其中构建堆的时间复杂度为O(n)，而调整堆的时间复杂度为O(logn)。

因此，整个堆排序的时间复杂度为O(nlogn)。

堆排序的优点是:空间复杂度较好，只需要一个额外的空间来存储堆节点。同时，由于不需要递归和多余的赋值操作，其时间复杂度相对较稳定。

void HeapSort(int*a,int n)
{  
  //建堆，向上调整
  for(int i = 1; i < n; ++i) 
  {
    AdjustUP(a,i);
  }
  // 交换堆顶元素和最后一个元素，并调整堆
  int end = n - 1;
  while (end > 0) {
    Swap(&a[end], &a[0]);
    AdjustDown(a,end,0);
    --end;
  }
}

int  main() {
  int n;
  printf("请输入学生数：");
  scanf("%d", &n);
  int* arr = (int*)malloc(n * sizeof(int)); // 动态分配数组内存空间
  printf("请输入学生的分数：");
  for (int i = 0; i < n; i++) {
    scanf("%d ", &arr[i]);
  }
  //int a[10] = { 1,2,8,9,4,5,15,16,19,10 };
  //int n = sizeof(a) / sizeof(a[0]);
  HeapSort(arr, n);
  printf("分数结果是");
  for (int i = 0; i < n; ++i) {
    printf("%d ", arr[i]);
  }
  return 0;
}

 

这是一段 C 语言代码，实现了堆排序算法。堆排序是利用堆的数据结构设计的一种排序算法，在时间复杂度为O(nlogn)的同时，也具有很好的空间利用率。这段代码中，首先使用 AdjustUP 函数将原始数组构成一个最大堆（即父节点大于等于左右子节点），然后在每次交换堆顶元素和最后一个元素的位置时，利用 AdjustDown 函数调整堆的结构，使得堆保持最大堆的性质。

     该代码中从标准输入读取 n 和 n 个学生分数，然后对它们进行排序并输出结果。如果需要运行该代码，需要自己实现 AdjustUP 和 AdjustDown 两个函数，或者从其他文件中引用这些函数。

其中AdjustUP 和 AdjustDown 两个函数

// AdjustUP 函数：向上调整堆
void AdjustUP(int* a, int child) {
  int parent = (child - 1) / 2;
  while (child > 0 && a[child] > a[parent]) {
    Swap(&a[child], &a[parent]);
    child = parent;
    parent = (child - 1) / 2;
  }
}

// AdjustDown 函数：向下调整堆
void AdjustDown(int* a, int n, int parent) {
  int child = 2 * parent + 1; // 初始化为左子节点
  while (child < n) {
    // 找到左右子节点中较大的一个
    if (child + 1 < n && a[child + 1] > a[child]) {
      ++child;
    }
    // 如果父节点比子节点都大，则跳出循环
    if (a[parent] >= a[child]) {
      break;
    }
    // 否则交换父节点和子节点，并继续向下调整
    Swap(&a[parent], &a[child]);
    parent = child;
    child = 2 * parent + 1;
  }
}

其中，Swap 函数为交换两个变量的值的函数，应该在代码中进行定义。在 AdjustUP 函数中，首先根据子节点的位置计算出其父节点的位置，然后不断将子节点与其父节点进行比较，如果子节点较大则将它们交换位置，直到子节点比其父节点小或者到达堆的根节点。在 AdjustDown 函数中，首先从指定的父节点开始，计算出其左右子节点中较大的一个（如果有的话），然后比较该子节点与父节点的大小关系，如果父节点比子节点都大，则说明已经满足最大堆的性质，此时可以结束函数；否则将父节点和子节点交换位置，并以新的父节点继续向下调整。