用堆排序算法按关键字递减的顺序排序。 输入:待排序记录数(整数)和待排序记录(整数序列); 输出:建堆结果和建堆后第一、第二次筛选结果。(注:待排序记录数大于等于3)
时间: 2023-04-29 22:00:44 浏览: 85
堆排序算法是一种基于完全二叉树的排序算法,可以按照关键字递增或递减的顺序进行排序。具体实现过程如下:
1. 建堆:将待排序记录构建成一个大根堆或小根堆。以递减排序为例,建立大根堆。从最后一个非叶子节点开始,依次向上调整,使得每个节点的值都大于其子节点的值。
2. 第一次筛选:将堆顶元素(即最大值)与堆底元素交换,然后将堆底元素下沉到合适的位置,重新构建大根堆。
3. 第二次筛选:重复第一次筛选的过程,直到所有元素都排好序。
下面是按关键字递减的顺序排序的堆排序算法的实现代码:
```
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);
}
// 第二次筛选
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);
}
}
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);
}
}
```
其中,heapify函数用于调整堆,使得以i为根节点的子树成为一个大根堆。在heapSort函数中,先建堆,然后进行两次筛选,最终得到按关键字递减的顺序排序的结果。