必做题：编程实现置换选择排序。 给定一组关键码序列，请模拟置换选择排序得到多个有序子序列。例如，关键码序列为(50、49、35、45、30、25、15、60、27)，欲对其进行从小到大进行排序。假设堆的大小最大为3，则经过置换选择排序可得到2个子序列，分别为 (35, 45, 49, 50)、(15, 25, 27, 30, 60)。 输入样例： 50 49 35 45 30 25 15 60 27（待排序关键码序列） 3（堆的大小） 输出样例： 35 45 49 50（第一个有序子序列） 15 25 27 30 60（第二个有序子序列）用c++实现上述内容

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

void heapify(vector<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) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

void replaceSelectionSort(vector<int>& arr, int heapSize) {
    int n = arr.size();
    int curHeapSize = heapSize;
    while (curHeapSize <= n) {
        heapSort(arr.begin(), arr.begin() + curHeapSize);
        for (int i = curHeapSize; i < n; i++) {
            if (arr[i] < arr[curHeapSize - 1]) {
                swap(arr[i], arr[curHeapSize - 1]);
                heapSort(arr.begin(), arr.begin() + curHeapSize);
            }
        }
        curHeapSize += heapSize;
    }
}

int main() {
    int n, heapSize;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cin >> heapSize;
    replaceSelectionSort(arr, heapSize);
    int curHeapSize = heapSize;
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
        if (i == curHeapSize - 1) {
            cout << endl;
            curHeapSize += heapSize;
        }
    }
    return 0;
}