怎么学习网站建设,室内设计效果图 装修,最适合女生的专业排名,制作wordpress堆排序#xff08;Heap sort#xff09;是指利用堆#xff08;最大堆、最小堆#xff09;这种数据结构所设计的一种排序算法。堆是一个完全二叉树的结构#xff0c;并同时满足如下性质#xff1a;即子结点的键值或索引总是小于#xff08;或者大于#xff09;它的父节点… 堆排序Heap sort是指利用堆最大堆、最小堆这种数据结构所设计的一种排序算法。堆是一个完全二叉树的结构并同时满足如下性质即子结点的键值或索引总是小于或者大于它的父节点。 一、算法基本思想 1基本思想 堆排序的基本思想就是从最大小堆得顶部不断取走堆顶元素放到有序序列中直到堆的元素被全部取完。堆排序完全依赖于最大小堆的相关操作。 2运行过程 堆排序算法的运作如下 1、创建一个最大小堆H 2、把堆首和堆尾元素互换 3、把堆的大小减1重新构造一个最大小堆 4、重复步骤2、3直到堆的大小减少为1。 3示例 最大堆的构建 堆排序过程 二、算法实现核心代码 C实现 #include iostream
#include algorithm
using namespace std;void max_heapify(int arr[], int start, int end) {//建立父節點指標和子節點指標int dad start;int son dad * 2 1;while (son end) { //若子節點指標在範圍內才做比較if (son 1 end arr[son] arr[son 1]) //先比較兩個子節點大小選擇最大的son;if (arr[dad] arr[son]) //如果父節點大於子節點代表調整完畢直接跳出函數return;else { //否則交換父子內容再繼續子節點和孫節點比較swap(arr[dad], arr[son]);dad son;son dad * 2 1;}}
}void heap_sort(int arr[], int len) {//初始化i從最後一個父節點開始調整for (int i len / 2 - 1; i 0; i--)max_heapify(arr, i, len);//先將第一個元素和已排好元素前一位做交換再從新調整直到排序完畢for (int i len - 1; i 0; i--) {swap(arr[0], arr[i]);max_heapify(arr, 0, i);}
}int main() {int arr[] { 4, 1, 3, 2, 16, 9, 10, 14, 8, 7};int len (int) sizeof(arr) / sizeof(*arr);heap_sort(arr, len);for (int i 0; i len; i)cout arr[i] ;cout endl;return 0;
} 三、性能算法时间、空间复杂度、稳定性分析 堆排序的时间复杂度为O(nlogn)空间复杂度为O(1)是不稳定的排序算法。
