【排序 - 选择排序优化版（利用堆排序）】

结合选择排序和堆排序的思路，可以通过利用堆数据结构来优化选择排序的过程，使得排序算法更加高效。在这种结合中，我们利用堆的特性来快速定位和选择未排序部分的最小元素，避免了选择排序中每次线性搜索的开销。

选择排序和堆排序结合的思路

选择排序的基本思想是每次从未排序的部分选择最小（或最大）的元素，放到已排序部分的末尾。结合堆排序的思路，我们可以利用最小堆来维护未排序部分的元素，每次从堆顶取出最小元素，放入已排序部分，然后调整堆，以保持堆的性质。

实现步骤

1. 建立最小堆：将待排序的数组建立成一个最小堆。
2. 选择最小元素：从堆顶（最小值）开始选择，将其放入已排序部分。
3. 维护堆的性质：每次选择操作后，需要调整堆，使得剩余的元素依然构成最小堆。
4. 重复以上步骤：直到所有元素都被排序。

C语言代码实现

下面是利用C语言实现结合选择排序和堆排序思路的示例代码：

#include <stdio.h>// 函数：对数组的子树以根节点 i 进行堆化，n 是堆的大小
void heapify(int arr[], int n, int i) {int smallest = i;  // 初始化最小值索引为 iint left = 2 * i + 1;  // 左子节点索引为 2*i + 1int 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;
}
}

示例说明

在上面的代码中：

• heapify() 函数用于维护堆的性质。
• heapSort() 函数用于对数组进行堆排序。
• selectionHeapSort() 函数结合了选择排序和堆排序的思路，通过建立最小堆和每次选择操作来实现排序。
• main() 函数中展示了如何使用 selectionHeapSort() 函数对数组进行排序，并输出排序后的结果。

这种结合选择排序和堆排序的方法利用了堆的优势，使得选择过程更高效，从而提升了整体排序算法的性能。