【排序 - 选择排序优化版（利用堆排序）】
最编程
2024-07-11 09:29:03
...
#include <stdio.h>
// 函数：对数组的子树以根节点 i 进行堆化，n 是堆的大小
void heapify(int arr[], int n, int i) {
int smallest = i; // 初始化最小值索引为 i
int left = 2 * i + 1; // 左子节点索引为 2*i + 1
int right = 2 * i + 2; // 右子节点索引为 2*i + 2
// 如果左子节点比根节点小
if (left < n && arr[left] < arr[smallest])
smallest = left;
// 如果右子节点比当前最小值小
if (right < n && arr[right] < arr[smallest])
smallest = right;
// 如果最小值不是根节点
if (smallest != i) {
// 交换最小值和根节点
int temp = arr[i];
arr[i] = arr[smallest];
arr[smallest] = temp;
// 递归调整受影响的子树
heapify(arr, n, smallest);
}
}
// 函数：进行堆排序
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);
}
}
// 函数：利用堆排序原理执行选择排序
void selectionHeapSort(int arr[], int n) {
// 从数组构建最小堆
heapSort(arr, n);
// 现在 arr[0] 包含最小元素，将其移到末尾并重复
for (int i = 0; i < n; i++) {
// 交换 arr[0] 和 arr[i]
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 重建堆，排除已排序的最后一个元素
heapify(arr, i, 0);
}
}
// 函数：打印数组
void printArray(int arr[], int n) {
for (int i = 0; i < n; ++i)
printf("%d ", arr[i]);
printf("\n");
}
// 主函数：测试以上功能
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("原始数组:\n");
printArray(arr, n);
selectionHeapSort(arr, n);
printf("选择和堆排序结合后的排序数组:\n");
printArray(arr, n);
return 0;
}
}