给出一个记录序列，用堆排序的方法将其进行升序排列，输出结果，输出时要求有文字说明。 请C++编写程序实现上述算法，并分析其算法复杂度。

堆排序是一种基于堆的排序算法，它的时间复杂度为O(nlogn)，空间复杂度为O(1)。堆排序分为两个步骤：建堆和排序。

建堆的过程是将无序的记录序列构建成一个堆。堆排序使用的是大根堆，即父节点的值大于等于其子节点的值。建堆的过程可以使用自底向上的方法，从最后一个非叶子节点开始，将其与其子节点比较并交换位置，直到整个序列都满足大根堆的性质。

排序的过程是将堆顶元素（最大值）与堆尾元素（未排序部分的最后一个元素）交换位置，并将堆的规模减1，然后将堆顶元素下沉到合适位置，使得剩余部分仍然满足大根堆的性质。重复以上步骤，直到整个序列都有序。

下面是C语言的堆排序实现：

#include <stdio.h>

void adjustHeap(int arr[], int i, int len) {
    int temp = arr[i];
    for (int k = i * 2 + 1; k < len; k = k * 2 + 1) {
        if (k + 1 < len && arr[k] < arr[k + 1]) {
            k++;
        }
        if (arr[k] > temp) {
            arr[i] = arr[k];
            i = k;
        } else {
            break;
        }
    }
    arr[i] = temp;
}

void heapSort(int arr[], int len) {
    for (int i = len / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, i, len);
    }
    for (int i = len - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        adjustHeap(arr, 0, i);
    }
}

int main() {
    int arr[] = {4, 1, 6, 8, 2, 5, 7, 3};
    int len = sizeof(arr) / sizeof(int);
    heapSort(arr, len);
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

以上代码中，adjustHeap函数用于调整堆，heapSort函数用于排序。在主函数中，我们定义一个记录序列arr，并将其传入heapSort函数进行排序。最后输出排序后的结果。

对于输入序列为{4, 1, 6, 8, 2, 5, 7, 3}的情况，排序后的结果为{1, 2, 3, 4, 5, 6, 7, 8}。

堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)。其中，建堆的时间复杂度为O(n)，排序的时间复杂度为O(nlogn)。由于堆排序的时间复杂度较稳定，因此在实际应用中比较常见。