堆排序-c++实现

以下是C++实现堆排序的代码：

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

其中，heapify函数用于维护最大堆，heapSort函数用于排序整个数组。在heapSort函数中，首先利用heapify函数构建最大堆，然后每次将堆顶元素（即最大值）放到数组的末尾，并重新维护最大堆，直到数组被排完序。