堆排序中第一个元素没排序？

发布网友

我来回答

共1个回答

热心网友

.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:005px0;padding:5px;border:1pxsolid#d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc100px);background-image:linear-gradient(#fff,#e5eecc100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1pxsolid#d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"AndaleMono","lucidaconsole","CourierNew",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1pxsolid#d4d4d4;width:98%}div.code{width:98%;border:1pxsolid#d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.codediv{font-size:110%}div.codediv,div.codep,div.example_codep{font-family:"couriernew"}pre{margin:15pxauto;font:12px/20pxMenlo,Monaco,Consolas,"AndaleMono","lucidaconsole","CourierNew",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1pxsolid#ddd;border-left-width:4px;padding:10px15px}排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是堆排序算法：
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；堆排序的平均时间复杂度为Ο(nlogn)。
1.算法步骤创建一个堆H[0??n-1]；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小1，并调用shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤2，直到堆的尺寸为1。
2.动图演示
代码实现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(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){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=iifleft<arrLenandarr[left]>arr[largest]:largest=leftifright<arrLenandarr[right]>arr[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)returnarrGo实例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:=iifleft<arrLen&&arr[left]>arr[largest]{largest=left}ifright<arrLen&&arr[right]>arr[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(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,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<stdio.h>#include<stdlib.h>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+1])//先比___子__大小，__最大的son++;if(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;i<len;i++)printf("%d",arr[i]);printf("
");return0;}C++实例#include<iostream>#include<algorithm>usingnamespacestd;voidmax_heapify(intarr[],intstart,intend){//建立父__指_和子__指_intdad=start;intson=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;}}}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<len;i++)cout<<arr[i]<<'';cout<<endl;return0;}参考文章：
https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/7.heapSort.md
https://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F
以下是热心网友对堆排序算法的补充，仅供参考：热心网友提供的补充1：
上方又没些C#的堆排序，艾孜尔江补充如下：

///<summary>
///堆排序
///</summary>
///<paramname="arr">待排序数组</param>
staticvoidHeapSort(int[]arr)
{
intvCount=arr.Length;
int[]tempKey=newint[vCount+1];
//元素索引从1开始
for(inti=0;i<vCount;i++)
{
tempKey[i+1]=arr[i];
}
//初始数据建堆（从含最后一个结点的子树开始构建，依次向前，形成整个二叉堆）
for(inti=vCount/2;i>=1;i--)
{
Restore(tempKey,i,vCount);
}
//不断输出堆顶元素、重构堆，进行排序
for(inti=vCount;i>1;i--)
{
inttemp=tempKey[i];
tempKey[i]=tempKey[1];
tempKey[1]=temp;
Restore(tempKey,1,i-1);
}
//排序结果
for(inti=0;i<vCount;i++)
{
arr[i]=tempKey[i+1];
}
}
///<summary>
///二叉堆的重构（针对于已构建好的二叉堆首尾互换之后的重构）
///</summary>
///<paramname="arr"></param>
///<paramname="rootNode">根结点j</param>
///<paramname="nodeCount">结点数</param>
staticvoidRestore(int[]arr,introotNode,intnodeCount)
{
while(rootNode<=nodeCount/2)//保证根结点有子树
{
//找出左右儿子的最大值
intm=(2*rootNode+1<=nodeCount&&arr[2*rootNode+1]>arr[2*rootNode])?2*rootNode+1:2*rootNode;
if(arr[m]>arr[rootNode])
{
inttemp=arr[m];
arr[m]=arr[rootNode];
arr[rootNode]=temp;
rootNode=m;
}
else
{
break;
}
}
}热心网友提供的补充2：
堆排序是不稳定的排序！

既然如此，每次构建大顶堆时，在父节点、左子节点、右子节点取三者中最大者作为父节点就行。我们追寻的只是最终排序后的结果，所以可以简化其中的步骤。

我将个人写的Java代码核心放在下方，有兴趣的同学可以一起讨论下：

pub