堆排序- 维基百科，自由的百科全书

堆排序（英語：Heapsort）是指利用堆這種数据結構所設計的一種排序算法。

堆是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子節點的键值或索引總是小於（或者 ... 堆排序 维基百科，自由的百科全书 跳到导航 跳到搜索 堆排序堆排序算法的演示。

首先，将元素进行重排，以符合堆的条件。

图中排序过程之前简单地绘出了堆树的结构。

概况類別排序算法資料結構陣列复杂度平均時間複雜度 Θ ( n log ⁡ n ) {\displaystyle\Theta(n\logn)} 最坏时间复杂度 O ( n log ⁡ n ) {\displaystyleO(n\logn)} 最优时间复杂度 O ( n log ⁡ n ) {\displaystyleO(n\logn)} [1]空間複雜度 O ( n ) {\displaystyleO(n)} total, O ( 1 ) {\displaystyleO(1)} auxiliary最佳解不是相关变量的定义 堆排序（英語：Heapsort）是指利用堆這種数据結構所設計的一種排序算法。

堆是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子節點的键值或索引總是小於（或者大於）它的父節點。

目录 1概述 2堆節點的訪問 3堆的操作 4實作範例 4.1C语言 4.2C++ 4.3Java 4.4Python 4.5JavaScript 4.6PHP 4.7Go 4.8julia 4.9Rust 4.10原地堆排序 5平均复杂度 6參考 7外部連結 概述[编辑] 若以升序排序說明，把陣列轉換成最大堆積（Max-HeapHeap），這是一種滿足最大堆積性質（Max-HeapProperty）的二元樹：對於除了根之外的每個节点i,A[parent(i)]≥A[i]。

重複從最大堆積取出數值最大的结点（把根结点和最后一个结点交換，把交換後的最后一个结点移出堆），並讓殘餘的堆積維持最大堆積性質。

堆節點的訪問[编辑] 通常堆是通過一維数组來實現的。

在陣列起始位置為0的情形中： 父節點i的左子節點在位置 ( 2 i + 1 ) {\displaystyle(2i+1)} ; 父節點i的右子節點在位置 ( 2 i + 2 ) {\displaystyle(2i+2)} ; {\displaystyle} 子節點i的父節點在位置 ⌊ ( i − 1 ) / 2 ⌋ {\displaystyle\lfloor(i-1)/2\rfloor} ; 堆的操作[编辑] 在堆的資料結構中，堆中的最大值總是位於根節點（在优先队列中使用堆的话堆中的最小值位于根节点）。

堆中定義以下幾種操作： 最大堆調整（MaxHeapify）：將堆的末端子節點作調整，使得子節點永遠小於父節點 建立最大堆（BuildMaxHeap）：將堆中的所有數據重新排序 堆排序（HeapSort）：移除位在第一個數據的根節點，並做最大堆調整的遞迴運算 實作範例[编辑] C语言[编辑] #include #include voidswap(int*a,int*b){ inttemp=*b; *b=*a; *a=temp; } voidmax_heapify(intarr[],intstart,intend){ //建立父節點指標和子節點指標 intdad=start; intson=dad*2+1; while(son<=end){//若子節點指標在範圍內才做比較 if(son+1<=end&&arr[son]arr[son])//如果父節點大於子節點代表調整完畢，直接跳出函數 return; else{//否則交換父子內容再繼續子節點和孫節點比较 swap(&arr[dad],&arr[son]); dad=son; son=dad*2+1; } } } voidheap_sort(intarr[],intlen){ inti; //初始化，i從最後一個父節點開始調整 for(i=len/2-1;i>=0;i--) max_heapify(arr,i,len-1); //先將第一個元素和已排好元素前一位做交換，再重新調整，直到排序完畢 for(i=len-1;i>0;i--){ swap(&arr[0],&arr[i]); max_heapify(arr,0,i-1); } } intmain(){ intarr[]={3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2,6}; intlen=(int)sizeof(arr)/sizeof(*arr); heap_sort(arr,len); inti; for(i=0;i #include usingnamespacestd; voidmax_heapify(intarr[],intstart,intend){ //建立父節點指標和子節點指標 intdad=start; intson=dad*2+1; while(son<=end){//若子節點指標在範圍內才做比較 if(son+1<=end&&arr[son]arr[son])//如果父節點大於子節點代表調整完畢，直接跳出函數 return; else{//否則交換父子內容再繼續子節點和孫節點比較 swap(arr[dad],arr[son]); dad=son; son=dad*2+1; } } } voidheap_sort(intarr[],intlen){ //初始化，i從最後一個父節點開始調整 for(inti=len/2-1;i>=0;i--) max_heapify(arr,i,len-1); //先將第一個元素和已经排好的元素前一位做交換，再從新調整(刚调整的元素之前的元素)，直到排序完畢 for(inti=len-1;i>0;i--){ swap(arr[0],arr[i]); max_heapify(arr,0,i-1); } } intmain(){ intarr[]={3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2,6}; intlen=(int)sizeof(arr)/sizeof(*arr); heap_sort(arr,len); for(inti=0;i>1)-1; for(inti=beginIndex;i>=0;i--) maxHeapify(i,len); /* *第二步：对堆化数据排序 *每次都是移出最顶层的根节点A[0]，与最尾部节点位置调换，同时遍历长度-1。

*然后从新整理被换到根节点的末尾元素，使其符合堆的特性。

*直至未排序的堆长度为0。

*/ for(inti=len;i>0;i--){ swap(0,i); maxHeapify(0,i-1); } } privatevoidswap(inti,intj){ inttemp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } /** *调整索引为index处的数据，使其符合堆的特性。

* *@paramindex需要堆化处理的数据的索引 *@paramlen未排序的堆（数组）的长度 */ privatevoidmaxHeapify(intindex,intlen){ intli=(index<<1)+1;//左子节点索引 intri=li+1;//右子节点索引 intcMax=li;//子节点值最大索引，默认左子节点。

if(li>len)return;//左子节点索引超出计算范围，直接返回。

if(ri<=len&&arr[ri]>arr[li])//先判断左右子节点，哪个较大。

cMax=ri; if(arr[cMax]>arr[index]){ swap(cMax,index);//如果父节点被子节点调换， maxHeapify(cMax,len);//则需要继续判断换下后的父节点是否符合堆的特性。

} } /** *测试用例 * *输出： *[0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,8,8,8,9,9,9] */ publicstaticvoidmain(String[]args){ int[]arr=newint[]{3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2,6}; newHeapSort(arr).sort(); System.out.println(Arrays.toString(arr)); } } Python[编辑] #!/usr/bin/envpython #-*-coding:utf-8-*- defheap_sort(lst): defsift_down(start,end): """最大堆调整""" root=start whileTrue: child=2*root+1 ifchild>end: break ifchild+1<=endandlst[child]=end)//若子節點指標超過範圍直接跳出函數 return; if(son+1=0;i--) max_heapify(i,len); //先將第一個元素和已排好元素前一位做交換，再從新調整，直到排序完畢 for(vari=len-1;i>0;i--){ swap(0,i); max_heapify(0,i); } returnarr; }; vara=[3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2,6]; console.log(a.heap_sort()); PHP[编辑] =$end)//若子節點指標超過範圍直接跳出函數 return; if($son+1=0;$i--) max_heapify($arr,$i,$len); //先將第一個元素和已排好元素前一位做交換，再從新調整，直到排序完畢 for($i=$len-1;$i>0;$i--){ swap($arr[0],$arr[$i]); max_heapify($arr,0,$i); } return$arr; } $arr=array(3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2,6); $arr=heap_sort($arr); for($i=0;$i Go[编辑] packagemain import( "fmt" ) funcHeapSort(array[]int){ m:=len(array) s:=m/2 fori:=s;i>-1;i--{ heap(array,i,m-1) } fori:=m-1;i>0;i--{ array[i],array[0]=array[0],array[i] heap(array,0,i-1) } } funcheap(array[]int,i,endint){ l:=2*i+1 ifl>end{ return } n:=l r:=2*i+2 ifr<=end&&array[r]>array[l]{ n=r } ifarray[i]>array[n]{ return } array[n],array[i]=array[i],array[n] heap(array,n,end) } funcmain(){ array:=[]int{ 55,94,87,1,4,32,11,77,39,42,64,53,70,12,9, } HeapSort(array) fmt.Println(array) } julia[编辑] functionHeapSort(array) functionadjust(l,u) whiletrue j=2*l#左子點 if(j>u)#代表沒有子點 break end if((j+1)<=u)#有右子點 if(array[j]array[l])#比較父點跟子點 array[l],array[j]=array[j],array[l] l=j#有交換 else break#沒交換跳出迴圈 end end end n=length(array) foriinn:-1:1#建maxHeap adjust(i,n) end #持續把第一個(最大)的元素最後一個交換 array[n],array[1]=array[1],array[n] foriinn-1:-1:1 adjust(1,i) array[i],array[1]=array[1],array[i] end returnarray end Rust[编辑] fnmax_heapify(data:&mut[T],pos:usize,end:usize){ letmutdad=pos; letmutson=dad*2+1; whileson<=end{ ifsondata[son]{ return; }else{ data.swap(dad,son); dad=son; son=dad*2+1; } } } fnheap_sort(data:&mut[T]){ letlen=data.len(); foriin(0..=len/2-1).rev(){ max_heapify(data,i,len-1); } foriin(1..=len-1).rev(){ data.swap(0,i); max_heapify(data,0,i-1); } } fnmain(){ letmutnums=vec![9,2,1,7,6,8,5,3,4]; heap_sort(nums.as_mut_slice()); } 原地堆排序[编辑] 基于以上堆相关的操作，我们可以很容易的定义堆排序。

例如，假设我们已经读入一系列数据并创建了一个堆，一个最直观的算法就是反复的调用del_max()函数，因为该函数总是能够返回堆中最大的值，然后把它从堆中删除，从而对这一系列返回值的输出就得到了该序列的降序排列。

真正的原地堆排序使用了另外一个小技巧。

堆排序的过程是： 建立一个堆 H [ 0.. n − 1 ] {\displaystyleH[0..n-1]} 把堆首（最大值）和堆尾互换 把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置 重复步骤2，直到堆的尺寸为1 平均复杂度[编辑] 堆排序的平均时间复杂度为 O ( n log ⁡ n ) {\displaystyle\mathrm{O}(n\logn)} ，空间复杂度为 Θ ( 1 ) {\displaystyle\Theta(1)} 。

參考[编辑] ^http://dx.doi.org/10.1006/jagm.1993.1031 外部連結[编辑] 常见排序算法-堆排序(HeapSort) 查论编排序算法理论 計算複雜性理論 大O符号 全序关系 数据结构术语列表 原地算法 稳定性 比较排序 自适应排序（英语：Adaptivesort） 排序网络（英语：Sortingnetwork） 整数排序（英语：Integersorting） X+Y排序（英语：X+Ysorting） 量子排序（英语：Quantumsort） 交换排序 冒泡排序 鸡尾酒排序 奇偶排序 梳排序 侏儒排序 快速排序 慢速排序 臭皮匠排序 Bogo排序 选择排序 选择排序 堆排序 平滑排序（英语：Smoothsort） 笛卡尔树排序（英语：Cartesiantreesort） 锦标赛排序（英语：Tournamentsort） 圈排序（英语：Cyclesort） 弱堆排序（英语：Weakheap） 插入排序 插入排序 希尔排序 伸展排序 二叉查找树排序 图书馆排序 耐心排序 归并排序 归并排序 梯级归并排序（英语：Cascademergesort） 振荡归并排序（英语：Oscillatingmergesort） 多相归并排序（英语：Polyphasemergesort） 分布排序 美国旗帜排序（英语：Americanflagsort） 珠排序 桶排序 爆炸排序（英语：Burstsort） 计数排序 比較計數排序 插值排序 鸽巢排序 相邻图排序（英语：Proxmapsort） 基数排序 闪电排序（英语：Flashsort） 并发排序 双调排序器（英语：Bitonicsorter） Batcher归并网络 两两排序网络（英语：Pairwisesortingnetwork） 混合排序 塊排序（英语：Blocksort） Tim排序 内省排序 Spread排序（英语：Spreadsort） 归并插入排序（英语：Merge-insertionsort） 其他 拓撲排序 煎餅排序 意粉排序（英语：Spaghettisort） 查论编算法排序比较排序 冒泡排序 选择排序 插入排序 希尔排序 快速排序 归并排序 堆排序 鸡尾酒排序 梳排序 侏儒排序 图书馆排序 内省排序 奇偶排序 线性时间排序 鸽巢排序 基数排序 計數排序 桶排序 并行排序 排序网络（英语：Sortingnetwork） Batcher归并网络 不实用的 Bogo排序 臭皮匠排序 图 拓撲排序 搜索列表 线性搜索 二分搜索 插值搜尋 树・图 广度优先搜索 最良優先搜索（英语：Best-firstsearch） 均一开销搜索 A* 深度优先搜索 迭代深化深度优先搜索 深度限制搜索（日语：深さ制限探索） 双向搜索 分枝限定法（英语：Branchandbound） 字符串 KMP算法 博耶-穆尔字符串搜索算法 AC自动机算法 拉宾-卡普算法 bitap算法 最短路问题 戴克斯特拉算法 贝尔曼-福特算法 A*搜尋演算法 Floyd-Warshall算法 最小生成树 普林姆算法 克鲁斯克尔演算法 最大流最小割 福特-富尔克森算法 埃德蒙兹-卡普算法 迪尼茨算法 线性规划 单纯形法 卡马卡尔算法（英语：Karmarkar'salgorithm） 順序統計量 选择算法 中位数的中位数（英语：Medianofmedians） 種類 近似算法 随机化算法 其他 分治法 动态规划 贪心算法 Category:算法 取自“https://zh.wikipedia.org/w/index.php?title=堆排序&oldid=71785226” 分类：​排序算法隐藏分类：​使用过时图像语法的页面含有英語的條目带有代码示例的条目 导航菜单 个人工具 没有登录讨论贡献创建账号登录 命名空间 条目讨论 不转换 不转换简体繁體大陆简体香港繁體澳門繁體大马简体新加坡简体臺灣正體 查看 阅读编辑查看历史 更多 搜索 导航 首页分类索引特色内容新闻动态最近更改随机条目资助维基百科 帮助 帮助维基社群方针与指引互助客栈知识问答字词转换IRC即时聊天联络我们关于维基百科 工具 链入页面相关更改上传文件特殊页面固定链接页面信息引用本页维基数据项目 打印/导出 下载为PDF打印页面 在其他项目中 维基共享资源 其他语言 العربيةAzərbaycancaБългарскиবাংলাCatalàČeštinaDeutschEnglishEspañolEestiفارسیSuomiFrançaisעבריתहिन्दीMagyarՀայերենÍslenskaItaliano日本語한국어LëtzebuergeschLietuviųമലയാളംNederlandsNorskbokmålPolskiPortuguêsРусскийSimpleEnglishSlovenščinaСрпски/srpskiSvenskaไทยTürkçeУкраїнськаTiếngViệt 编辑链接