对一含有n(n>=1)个整数的序列,使用堆排序算法将其排列为一个非递减序列。在这个有序序列的基础上求众数,如果该序列的众数不唯一,则将所有众数按从小到大的顺序输出。c语言
时间: 2024-05-01 19:23:16 浏览: 235
以下是C语言实现,其中包括堆排序算法和求众数的方法:
```c
#include <stdio.h>
#include <stdlib.h>
// 堆排序算法
void heap_sort(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);
}
}
// 堆化指定节点
void heapify(int arr[], int n, int i)
{
int largest = i;
int left_child = 2 * i + 1;
int right_child = 2 * i + 2;
// 找出最大的子节点
if (left_child < n && arr[left_child] > arr[largest])
largest = left_child;
if (right_child < n && arr[right_child] > arr[largest])
largest = right_child;
// 如果最大子节点不是当前节点,则交换它们并继续堆化
if (largest != i)
{
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
// 求众数
void find_mode(int arr[], int n)
{
int mode = arr[0];
int count = 1;
int max_count = 1;
// 扫描序列并更新众数
for (int i = 1; i < n; i++)
{
if (arr[i] == arr[i-1])
count++;
else
{
if (count > max_count)
{
max_count = count;
mode = arr[i-1];
}
count = 1;
}
}
// 处理最后一个元素
if (count > max_count)
mode = arr[n-1];
// 输出众数
printf("The mode(s) is: ");
count = 0;
for (int i = 0; i < n; i++)
{
if (arr[i] == mode)
{
printf("%d ", arr[i]);
count++;
}
}
if (count == 0)
printf("None");
}
int main()
{
int n;
printf("Enter the size of the array: ");
scanf("%d", &n);
int *arr = malloc(sizeof(int) * n);
printf("Enter the elements of the array:\n");
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
heap_sort(arr, n);
printf("The sorted array is: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
find_mode(arr, n);
free(arr);
return 0;
}
```
在这个程序中,我们首先使用堆排序算法对输入的整数序列进行排序。然后,我们使用一个扫描算法来查找众数。在扫描序列时,我们维护一个当前元素出现次数的计数器以及一个最大出现次数的计数器。如果当前元素与前一个元素相同,则增加计数器;否则,更新最大计数器并记录众数。在处理完最后一个元素后,我们输出所有众数。如果没有众数,则输出"None"。
阅读全文
相关推荐
















