缘魁网站建设,wordpress文章全显示,wordpress 双陈,杭州网站建设制作算法-堆排序 前置知识
堆#xff08;即将更新#xff09; 思路
我们现在有一个序列#xff0c;怎么对它排序#xff1f; 这是一个非常经典的问题#xff0c;这里我们使用一个借助数据结构的算法——堆排序解决。
这里有一个序列#xff0c;要对它升序排序 4 7 3 6 5 …算法-堆排序 前置知识
堆即将更新 思路
我们现在有一个序列怎么对它排序 这是一个非常经典的问题这里我们使用一个借助数据结构的算法——堆排序解决。
这里有一个序列要对它升序排序 4 7 3 6 5 1 2 8 \begin{array}{cc} 47365128 \end{array} 47365128 构建一个堆 将堆顶放入序列删除堆顶 重复该操作 直至堆为空。 获得的序列为 1 2 3 4 5 6 7 8 \begin{array}{cc} 12345678 \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 largesti,l2*i1,r2*i2;if (lna[l]a[largest])largestl;if (rna[r]a[largest])largestr;if (largest!i){swap(a[i],a[largest]);heapify(a,n,largest);}
}
void HeapSort(int a[],int n){//堆排序for (int in/2-1;i0;i--)heapify(a,n,i);for (int in-1;i0;i--){swap(a[0],a[i]);heapify(a,i,0);}
}练习
洛谷【模板】排序
