堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种**选择排序，**它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。

堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

堆排序的平均时间复杂度为 Ο(nlogn)。

JavaScript

实例

varlen;//因为声明的多个函数都需要数据长度，所以把len设置成为全局变量functionbuildMaxHeap(arr){//建立大顶堆len=arr.length;for(vari=Math.floor(len/2);i>=0;i--){heapify(arr,i);}}functionheapify(arr,i){//堆调整varleft=2*i+1,right=2*i+2,largest=i;if(leftarr[largest]){largest=left;}if(rightarr[largest]){largest=right;}if(largest!=i){swap(arr,i,largest);heapify(arr,largest);}}functionswap(arr,i,j){vartemp=arr[i];arr[i]=arr[j];arr[j]=temp;}functionheapSort(arr){buildMaxHeap(arr);for(vari=arr.length-1;i>0;i--){swap(arr,0,i);len--;heapify(arr,0);}returnarr;}

Python

实例

defbuildMaxHeap(arr):importmathforiinrange(math.floor(len(arr)/2),-1,-1):heapify(arr,i)defheapify(arr,i):left=2*i+1right=2*i+2largest=iifleftarr[largest]:largest=leftifrightarr[largest]:largest=rightiflargest!=i:swap(arr,i,largest)heapify(arr,largest)defswap(arr,i,j):arr[i],arr[j]=arr[j],arr[i]defheapSort(arr):globalarrLenarrLen=len(arr)buildMaxHeap(arr)foriinrange(len(arr)-1,0,-1):swap(arr,0,i)arrLen-=1heapify(arr,0)returnarr

Go

实例

funcheapSort(arr[]int)[]int{arrLen:=len(arr)buildMaxHeap(arr,arrLen)fori:=arrLen-1;i>=0;i--{swap(arr,0,i)arrLen-=1heapify(arr,0,arrLen)}returnarr}funcbuildMaxHeap(arr[]int,arrLenint){fori:=arrLen/2;i>=0;i--{heapify(arr,i,arrLen)}}funcheapify(arr[]int,i,arrLenint){left:=2*i+1right:=2*i+2largest:=iifleftarr[largest]{largest=left}ifrightarr[largest]{largest=right}iflargest!=i{swap(arr,i,largest)heapify(arr,largest,arrLen)}}funcswap(arr[]int,i,jint){arr[i],arr[j]=arr[j],arr[i]}

Java

实例

publicclassHeapSortimplementsIArraySort{@Overridepublicint[]sort(int[]sourceArray)throwsException{//对arr进行拷贝，不改变参数内容int[]arr=Arrays.copyOf(sourceArray,sourceArray.length);intlen=arr.length;buildMaxHeap(arr,len);for(inti=len-1;i>0;i--){swap(arr,0,i);len--;heapify(arr,0,len);}returnarr;}privatevoidbuildMaxHeap(int[]arr,intlen){for(inti=(int)Math.floor(len/2);i>=0;i--){heapify(arr,i,len);}}privatevoidheapify(int[]arr,inti,intlen){intleft=2*i+1;intright=2*i+2;intlargest=i;if(leftarr[largest]){largest=left;}if(rightarr[largest]){largest=right;}if(largest!=i){swap(arr,i,largest);heapify(arr,largest,len);}}privatevoidswap(int[]arr,inti,intj){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}}

PHP

实例

functionbuildMaxHeap(&$arr){global$len;for($i=floor($len/2);$i>=0;$i--){heapify($arr,$i);}}functionheapify(&$arr,$i){global$len;$left=2*$i+1;$right=2*$i+2;$largest=$i;if($left$len&&$arr[$left]>$arr[$largest]){$largest=$left;}if($right$len&&$arr[$right]>$arr[$largest]){$largest=$right;}if($largest!=$i){swap($arr,$i,$largest);heapify($arr,$largest);}}functionswap(&$arr,$i,$j){$temp=$arr[$i];$arr[$i]=$arr[$j];$arr[$j]=$temp;}functionheapSort($arr){global$len;$len=count($arr);buildMaxHeap($arr);for($i=count($arr)-1;$i>0;$i--){swap($arr,0,$i);$len--;heapify($arr,0);}return$arr;}

C

实例

#include#includevoidswap(int*a,int*b){inttemp=*b;*b=*a;*a=temp;}voidmax_heapify(intarr[],intstart,intend){//建立父節點指標和子節點指標intdad=start;intson=dad*2+1;while(sonif(son+1if(arr[dad]>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;iprintf("%d",arr[i]);printf("\n");return0;}

C++

实例#include#includeusingnamespacestd;voidmax_heapify(intarr[],intstart,intend){//建立父節點指標和子節點指標intdad=start;intson=dad*2+1;while(sonif(son+1if(arr[dad]>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'';coutreturn0;}