堆排序的算法实现

堆排序是一种高效的比较排序算法，其时间复杂度为O(nlogn)，可用于排序大量数据。它的基本思想是将待排序序列构造成一个堆，然后利用堆的性质进行排序。

一、堆的定义

堆（Heap）是一种特殊的树形数据结构，它满足两个特性：

1.堆是一个完全二叉树。

2.堆中每个节点的值都大于等于（或小于等于）其子节点的值。这个性质被称为堆的特性。

二、堆的分类

堆分为大根堆和小根堆，大根堆的每个节点的值都大于等于其左右子节点的值，小根堆的每个节点的值都小于等于其左右子节点的值。

三、堆排序的过程

1.构建堆：从最后一个非叶子节点开始，依次向前调整节点位置，使之成为一个大根堆或者小根堆。

2.排序：每次将堆顶元素（最大或最小值）与末尾元素交换，即最大元素（或最小元素）移到已经排序好的序列的末尾，然后重新调整堆顶元素所在位置，使之满足堆的特性。

3.重复执行第2步，直到整个序列被排序。

四、堆排序的代码实现

以大根堆为例，堆排序的代码实现如下：

```

void heapify(int arr[], int n, int i) {

int largest = i; //初始化最大值为当前节点

int l = 2 * i + 1; //左子节点索引

int r = 2 * i + 2; //右子节点索引

//找到最大值

if (l < n && arr[l] > arr[largest]) {

largest = l;

}

if (r < n && arr[r] > arr[largest]) {

largest = r;

}

//如果最大值不是当前节点，交换当前节点和最大值所在位置的节点

if (largest != i) {

swap(arr[i], arr[largest]);

//递归调整子树

heapify(arr, n, largest);

}

}

void heapSort(int arr[], int n) {

//构建堆

for (int i = n / 2 - 1; i >= 0; i--) {

heapify(arr, n, i);

}

//每次将堆顶元素移到已经排序好的末尾

for (int i = n - 1; i >= 0; i--) {

swap(arr[0], arr[i]);

//调整剩余元素构成的堆

heapify(arr, i, 0);

}

}

```

五、堆排序的优缺点

1.优点：

（1）堆排序是一种原地排序算法，不需要额外的存储空间。

（2）堆排序的时间复杂度为O(nlogn)，比冒泡、插入、选择排序要快得多。

2.缺点：

（1）堆排序是一种不稳定的排序算法，可能会破坏相等元素之间的顺序。

（2）堆排序构建堆的过程比较耗时，因此在小规模数据的排序中并不适用。