基本思想

堆排序是不稳定的排序算法。常见的不稳定排序算法有四种：快速排序、希尔排序、选择排序、堆排序。
堆是具有以下性质的完全二叉树：每个结点的值都大于其左右孩子结点的值，称为大根堆；或者每个结点的值都小于其左右孩子结点的值，称为小根堆。两者对左右孩子的大小关系不做任何要求。
堆排序算法步骤:

假设结果要递增有序。
首先用前n个元素的无序序列，构建成大顶堆；
构建大顶堆时，从最后一个非叶节点n/2-1的位置开始检查节点与其孩子值是否满足大顶堆的要求，不满足则需要调整该元素与其孩子节点元素的位置，如果有调整，则调整过的孩子节点（子树）也要递归调用调整子树中的元素值位置，保证子树也是大顶堆。然后按照层次遍历的顺序依次往前调整所有非叶节点的值，最后根节点的值就是最大值。
得到大顶堆后将根节点与数组待排序部分的最后一个元素交换位置，即将最大元素”沉”到数组末端；
交换过后待排序数组长度减一，再对新长度的待排序数组重复上述过程，直到整个数组排序完成。如果我们要数组整体递增有序，则每次构建的是大顶堆；如果我们要数组整体递减有序，则每次构建的是小顶堆。
C/C++实现
`cpp
include
include

using namespace std;

class Solution {
public:
void swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}

void adjust_heap(vector<int> &nums, int node_index, int n) {
    //n为数组长度
    int left_child = 2 * node_index + 1, right_child = 2 * node_index + 2;
    int max_idx = node_index;
    //如果非叶节点左孩子存在,且左孩子值更大,记录值最大的节点的编号为max_idx
    if (left_child < n && nums[max_idx] < nums[left_child])
        max_idx = left_child;
    //如果非叶节点右孩子存在,且右孩子值更大,记录值最大的节点的编号为max_idx
    if (right_child < n && nums[max_idx] < nums[right_child])
        max_idx = right_child;
    //如果最大值不在非叶节点而是在它的孩子节点上,则需要交换值,并对交换了值的子树递归调用函数adjust_heap以保证子树也是大顶堆
    if (max_idx != node_index) {
        swap(nums[node_index], nums[max_idx]);
        adjust_heap(nums, max_idx, n);
    }
}

void heap_sort(vector<int> &nums, int n) {
    //n为数组长度
    //堆排序形成的树是完全二叉树,其最后一个非叶节点编号为k=(n-2)/2,n为层次遍历的最后一个节点的编号
    //任意一个非叶节点其左孩子编号为2*k+1,右孩子编号为2*k+2
    for (int i = (n - 2) / 2; i >= 0; i--)
        //对所有非叶节点进行节点值调整,使其变为大顶堆
        adjust_heap(nums, i, n);
    // 上面的for循环完成后得到一个大顶堆,将确定的堆顶元素(最大值)与数组待排序部分的最后一个元素交换,这样最终得到的是递增序列
    swap(nums[0], nums[n - 1]);
    // 下面循环的n代表数组长度,待排序数组长度减一,然后递归调用heap_sort重复上述过程
    for (int i = n - 1; i >= 1; i--) {
        heap_sort(nums, i);
    }
}

};

int main() {
vector a = {5, 2, 3, 4, 7, 5, 1, 6};
Solution s;
int n = a.size();
s.heap_sort(a, n);
for (int i:a)
cout << i << “ “;
return 0;
}

# Python3实现
```python
class Solution(object):
    def adjust_heap(self, nums, index, n):
        left_child, right_child = 2 * index + 1, 2 * index + 2
        max_idx = index
        if left_child < n and nums[max_idx] < nums[left_child]:
            max_idx = left_child
        if right_child < n and nums[max_idx] < nums[right_child]:
            max_idx = right_child
        if max_idx != index:
            nums[index], nums[max_idx] = nums[max_idx], nums[index]
            self.adjust_heap(nums, max_idx, n)

    def heap_sort(self, nums, n):
        for i in range(int(n / 2), -1, -1):
            self.adjust_heap(nums, i, n)
        nums[0], nums[n - 1] = nums[n - 1], nums[0]
        for j in range(n - 1, 0, -1):
            self.heap_sort(nums, j)


a = [5, 2, 3, 4, 7, 5, 1, 6]
s = Solution()
s.heap_sort(a, len(a))
print(a)

赏