【算法】堆排序
算法-堆排序
前置知识
- 堆（即将更新）
思路
我们现在有一个序列，怎么对它排序？
这是一个非常经典的问题，这里我们使用一个借助数据结构的算法——堆排序解决。
这里有一个序列，要对它升序排序
4
7
3
6
5
1
2
8
\begin{array}{cc} 4&7&3&6&5&1&2&8 \end{array}
47365128
构建一个堆：
将堆顶放入序列，删除堆顶
重复该操作
直至堆为空。
获得的序列为：
1
2
3
4
5
6
7
8
\begin{array}{cc} 1&2&3&4&5&6&7&8 \end{array}
12345678
算法参数
- 平均时间复杂度： Θ ( n log n ) \Theta(n\log n) Θ(nlogn)
- 最好时间复杂度： O ( n log n ) O(n\log n) O(nlogn)
- 最坏时间复杂度： O ( n log n ) O(n\log n) O(nlogn)
- 空间复杂度： Θ ( n ) \Theta(n) Θ(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);
}
}
练习
- 洛谷【模板】排序