【算法】堆排序

算法-堆排序

---

前置知识

• 堆（即将更新）

---

思路

我们现在有一个序列，怎么对它排序？
这是一个非常经典的问题，这里我们使用一个借助数据结构的算法——堆排序解决。

这里有一个序列，要对它升序排序
4 7 3 6 5 1 2 8

4​7​3​6​5​1​2​8​
构建一个堆：

将堆顶放入序列，删除堆顶

重复该操作






直至堆为空。
获得的序列为：
1 2 3 4 5 6 7 8

12345678" role="presentation" style="position: relative;">12345678$$\begin{array}{cccccccc}1& 2& 3& 4& 5& 6& 7& 8\end{array}$$

1​2​3​4​5​6​7​8​

---

算法参数

• 平均时间复杂度：$\Theta (n\log n)$
• 最好时间复杂度：$O(n\log n)$
• 最坏时间复杂度：$O(n\log n)$
• 空间复杂度：$\Theta (n)$
• 稳定性：不稳定

---

实现代码

• 手写堆版本

void heapify(int a[],int n,int i){//维护堆的性质
    int largest=i,l=2*i+1,r=2*i+2;
    if (l<n&&a[l]>a[largest])
        largest=l;
    if (r<n&&a[r]>a[largest])
        largest=r;
    if (largest!=i){
        swap(a[i],a[largest]);
        heapify(a,n,largest);
    }
}
void HeapSort(int a[],int n){//堆排序
    for (int i=n/2-1;i>=0;i--)
        heapify(a,n,i);
    for (int i=n-1;i>0;i--){
        swap(a[0],a[i]);
        heapify(a,i,0);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

练习

• 洛谷【模板】排序