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

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

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

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

实现步骤

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

C语言代码实现

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

#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;
}
}

示例说明

在上面的代码中：

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

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