【问题描述】对一含有n(n<=100)个整数的序列,使用堆排序将其由小到大(非降序)排序。 【输入形式】第一行为元素的个数n,第二行为n个整数(以空格隔开)。 【输出形式】分三行,分别输出这n个整数排序前、构造堆之后、堆排序后的序列(整数之间以逗号隔开)。 注意:构造堆需采用自底向上构造算法来构造最大堆。 【样例输入】 9 50 10 90 30 70 40 80 60 20 【样例输出】 50,10,90,30,70,40,80,60,20 90,70,80,60,10,40,50,30,20 10,20,30,40,50,60,70,80,90
时间: 2023-09-02 18:06:16 浏览: 27
好的,下面是 C 语言程序的代码实现:
```
#include <stdio.h>
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) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
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--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
int main() {
int n;
scanf("%d", &n);
int arr[n];
for(int i=0; i<n; i++) {
scanf("%d", &arr[i]);
}
printf("%d", arr[0]);
for(int i=1; i<n; i++) {
printf(",%d", arr[i]);
}
printf("\n");
heapSort(arr, n);
printf("%d", arr[0]);
for(int i=1; i<n; i++) {
printf(",%d", arr[i]);
}
printf("\n");
printf("%d", arr[n-1]);
for(int i=n-2; i>=0; i--) {
printf(",%d", arr[i]);
}
printf("\n");
return 0;
}
```
以上代码实现了堆排序算法,可以将输入的序列按照从小到大的顺序进行排序。在程序中,首先读取输入的序列并输出原始序列,接着使用堆排序算法对序列进行排序,并输出排序后的序列和逆序排列的序列。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)