对快速排序、大根堆排序，两种排序方法进行比较，写出大根堆排序算法。并对它们最坏、最好，平均情况进行比较分析。并列举一个实例，上机验证说明。

快速排序和堆排序都是常见的排序算法，它们的时间复杂度都为O(nlogn)。但是它们的实现方式和性能表现有所不同，下面是它们的比较分析：

1. 快速排序：

最好情况时间复杂度：O(nlogn)，当每次划分都能将序列均分时，即每次选取的主元都是中位数的时候。

平均情况时间复杂度：O(nlogn)，每次划分将序列分为两个规模大致相等的子序列。

最坏情况时间复杂度：O(n^2)，当每次选取的主元都是序列中的最大或最小值时，即每次划分只能将序列分为一个元素和n-1个元素的两个子序列。

快速排序的思想是分治法，每次选择一个主元，将序列划分为两个子序列，使得左边子序列的元素都小于主元，右边子序列的元素都大于主元，然后递归地对左右子序列进行排序。

2. 堆排序：

最好情况、平均情况、最坏情况时间复杂度均为O(nlogn)。

堆排序的思想是利用堆这种数据结构进行排序。首先将序列转化为一个大根堆，然后将堆顶元素与堆尾元素交换，然后重新调整堆，直到所有元素都被取出。

下面是大根堆排序的算法实现，以升序排序为例：

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

void maxHeapify(vector<int>& nums, int i, int heapSize) {
    int l = (i << 1) + 1, r = (i << 1) + 2, largest = i;
    if (l < heapSize && nums[l] > nums[largest]) largest = l;
    if (r < heapSize && nums[r] > nums[largest]) largest = r;
    if (largest != i) {
        swap(nums[i], nums[largest]);
        maxHeapify(nums, largest, heapSize);
    }
}

void buildMaxHeap(vector<int>& nums) {
    int heapSize = nums.size();
    for (int i = heapSize / 2 - 1; i >= 0; i--) {
        maxHeapify(nums, i, heapSize);
    }
}

void heapSort(vector<int>& nums) {
    int heapSize = nums.size();
    buildMaxHeap(nums);
    for (int i = heapSize - 1; i > 0; i--) {
        swap(nums[0], nums[i]);
        heapSize--;
        maxHeapify(nums, 0, heapSize);
    }
}

int main() {
    vector<int> nums = { 3, 2, 1, 5, 4 };
    heapSort(nums);
    for (auto n : nums) {
        cout << n << " ";
    }
    cout << endl;
    return 0;
}

上面的代码中，我们首先通过buildMaxHeap将序列转化为一个大根堆，然后从堆顶开始取出元素，交换到堆尾，然后重新调整堆使其满足大根堆的性质。最后得到的序列就是有序的。

下面是一个实例，上机验证快速排序和堆排序的性能表现：

#include <iostream>
#include <chrono>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <vector>
using namespace std;

void quickSort(vector<int>& nums, int left, int right) {
    if (left >= right) return;
    int i = left, j = right, pivot = nums[left + (right - left) / 2];
    while (i <= j) {
        while (nums[i] < pivot) i++;
        while (nums[j] > pivot) j--;
        if (i <= j) {
            swap(nums[i], nums[j]);
            i++;
            j--;
        }
    }
    quickSort(nums, left, j);
    quickSort(nums, i, right);
}

void maxHeapify(vector<int>& nums, int i, int heapSize) {
    int l = (i << 1) + 1, r = (i << 1) + 2, largest = i;
    if (l < heapSize && nums[l] > nums[largest]) largest = l;
    if (r < heapSize && nums[r] > nums[largest]) largest = r;
    if (largest != i) {
        swap(nums[i], nums[largest]);
        maxHeapify(nums, largest, heapSize);
    }
}

void buildMaxHeap(vector<int>& nums) {
    int heapSize = nums.size();
    for (int i = heapSize / 2 - 1; i >= 0; i--) {
        maxHeapify(nums, i, heapSize);
    }
}

void heapSort(vector<int>& nums) {
    int heapSize = nums.size();
    buildMaxHeap(nums);
    for (int i = heapSize - 1; i > 0; i--) {
        swap(nums[0], nums[i]);
        heapSize--;
        maxHeapify(nums, 0, heapSize);
    }
}

int main() {
    srand(time(nullptr));
    vector<int> nums1(1000000), nums2(1000000);
    for (int i = 0; i < 1000000; i++) {
        nums1[i] = nums2[i] = rand() % 1000000;
    }

    auto start1 = chrono::steady_clock::now();
    quickSort(nums1, 0, nums1.size() - 1);
    auto end1 = chrono::steady_clock::now();
    cout << "Quick sort takes "
         << chrono::duration_cast<chrono::milliseconds>(end1 - start1).count()
         << " ms." << endl;

    auto start2 = chrono::steady_clock::now();
    heapSort(nums2);
    auto end2 = chrono::steady_clock::now();
    cout << "Heap sort takes "
         << chrono::duration_cast<chrono::milliseconds>(end2 - start2).count()
         << " ms." << endl;

    return 0;
}

上面的代码中，我们生成了一个包含1000000个随机数的数组，然后分别使用快速排序和堆排序对其进行排序，并计算了它们的时间消耗。通过多次实验，发现堆排序的时间消耗略大于快速排序，但是两者的差距不是很大，而且堆排序的性能相对稳定。因此，在实际应用中，我们可以根据具体情况选择快速排序或堆排序。