#include <iostream> #include <vector> // 调整堆 void heapify(std::vector<int>& arr, int n, int i) { int largest = i; // 最大元素的索引 int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) largest = left; if (right < n && arr[right] > arr[largest]) largest = right; if (largest != i) { std::swap(arr[i], arr[largest]); heapify(arr, n, largest); } } // 堆排序 void heapSort(std::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--) { std::swap(arr[0], arr[i]); heapify(arr, i, 0); } } // 数组倒序 void reverseArray(std::vector<int>& arr) { int start = 0; int end = arr.size() - 1; while (start < end) { std::swap(arr[start], arr[end]); start++; end--; } } int main() { std::vector<int> arr = {}; // 堆排序 heapSort(arr); std::cout << "堆排序后的数组："; for (int num : arr) { std::cout << num << " "; } std::cout << std::endl; // 数组倒序 reverseArray(arr); std::cout << "数组倒序结果："; for (int num : arr) { std::cout << num << " "; } std::cout << std::endl; return 0; }注释

这是一个包含堆排序和数组倒序功能的程序。它使用了两个函数：heapify和heapSort。

heapify函数用于调整堆。它接受一个整数向量arr，以及堆的大小n和当前节点的索引i。在该函数中，先将当前节点设为最大元素的索引，然后比较当前节点与左右子节点的大小，如果子节点中存在比当前节点更大的元素，则将最大元素的索引更新为子节点的索引。最后，如果最大元素的索引不等于当前节点的索引，则交换这两个元素，并递归地调用heapify函数。

heapSort函数用于对数组进行堆排序。它接受一个整数向量arr，并按照以下步骤进行排序：首先，通过调用heapify函数，将数组构建成最大堆；然后，从最后一个元素开始，依次将根节点（最大值）与当前元素交换，并调用heapify函数对剩余元素进行调整；重复这个过程，直到所有元素都排好序。

reverseArray函数用于将数组倒序。它接受一个整数向量arr，并使用两个指针start和end来交换元素，以实现数组的倒序。

在主函数中，程序首先定义了一个空的整数向量arr。然后，它调用heapSort函数对arr进行排序，并输出排序后的结果。接着，它调用reverseArray函数对arr进行倒序，并输出倒序后的结果。

最后，程序返回0表示正常运行结束。

如果你对这段代码有任何疑问，请随时提问。

相关问题

必做题：编程实现置换选择排序。 给定一组关键码序列，请模拟置换选择排序得到多个有序子序列。例如，关键码序列为(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;
}

插入排序、堆排序、快速排序、冒泡排序，请用c++语言实现上述排序，写在同一个程序里，头文件里不包括vector、algorithm

以下是使用C++语言实现的四种排序算法：

#include <iostream>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

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

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--) {
        std::swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - i - 1; j++)
            if (arr[j] > arr[j + 1])
                std::swap(arr[j], arr[j + 1]);
}

int main() {
    const int len = 10;
    int arr[len] = {5, 7, 1, 3, 9, 2, 8, 4, 6, 0};

    insertionSort(arr, len);
    std::cout << "Insertion Sort: ";
    for (int i = 0; i < len; i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;

    heapSort(arr, len);
    std::cout << "Heap Sort: ";
    for (int i = 0; i < len; i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;

    quickSort(arr, 0, len - 1);
    std::cout << "Quick Sort: ";
    for (int i = 0; i < len; i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;

    bubbleSort(arr, len);
    std::cout << "Bubble Sort: ";
    for (int i = 0; i < len; i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;

    return 0;
}