下图以建大堆为例排一个升序序列
实现堆排序最重要的就是实现向下调整算法。以下是向下调整算法的代码以及解释
- //这里以建大堆为例
- void AdjustDown(int* a, int n, int root)
- {
- int child = root * 2 + 1;//找到根节点的左孩子
- while (child < n)//判断左孩子是否出界
- {
- if (child + 1 < n && a[child + 1] > a[child])
- //child + 1 < n判断右孩子是否出界,
- //a[child + 1] > a[child]判断左右孩子的大小,取左右孩子中大的那一个
- child++;
- if (a[child] > a[root])//入过孩子的值比父亲的值大,就交换孩子和父亲的位置
- Swap(&a[child], &a[root]);
- else//如果孩子的值不比父亲的值大,就证明大堆已经建好了(因为此时父亲的左右子树都是大堆),
- //直接break跳出循环。
- break;
- //没有break来到这里就顺着子树继续往下走
- root = child;
- child = root * 2 + 1;
- }
- }
以下是堆排序的代码实现以及解释
- void HeapSort(int* a, int n)
- {
- //向下调整建堆
- for (int i = (n - 1 - 1) / 2; i >= 0; i--)
- {
- //(n - 1 - 1) / 2找到第一个非叶子节点,从第一个非叶子结点开始向下建堆
- AdjustDown(a, n, i);
- }
- //堆建好了
- int end = n - 1;
- while (end > 0)
- {
- //假设是建大堆,将下标为0的元素和下标为end的元素交换,
- //最大的数就排到最后了,也就相当于最后的那个数已经排好了,不用再参与下面的向下建堆
- Swap(&a[0], &a[end]);
- AdjustDown(a, end, 0);//还没有排好的数向下建堆从0位置开始向下建堆
- end--;
- }
- }