1、将给定数组转化为一个二叉堆2、定义一个指针,为数组的最后一位functionsortArray(nums:number[]){letN=nums.length-1//从中位开始,指针i,向左移动for(leti=Math.floor(N/2);i>=0;i--){//将i至N位元素堆有序直到数字组首位sink(nums,i,N)}}3、将二叉堆的根节点(最大值)与当前指针位交换,随后指针往左挪一位4、将数组索引0开始到指针这调用一次sink(),重新堆有序化functionsink(nums:number[],k:number,N:number){while(k*2<=N){letj=k*2//子节点if(j<N&&nums[j]<nums[j+1])j++if(nums[k]>=nums[j])break;exch(nums,k,j)k=j}}functionsortArray(nums:number[]){letN=nums.length-1//从中位开始,指针i,向左移动for(leti=Math.floor(N/2);i>=0;i--){//将i至N位元素堆有序直到数字组首位sink(nums,i,N)}while(N>0){exch(nums,0,N--)//交换首位与尾部,并且指针左移sink(nums,0,N)//指针移动后向堆有序化}returnnums}

堆排序是一种选择排序，利用堆这种数据结构来完成选择。其算法思想是将带排序数据构造一个最大堆（升序）/最小堆（降序），然后将堆顶元素与待排序数组的最后一个元素交换位置，此时末尾元素就是最大/最小的值。然后将剩余n-1个元素重新构造成最大堆/最小堆。

将待排序的序列构成一个大顶堆，这个时候整个序列的最大值就是堆顶的根节点，将它与末尾节点进行交换,然后末尾变成了最大值,然后剩余n-1个元素重新构成一个堆，这样得到这n个元素的次大值，反复进行以上操作便得到一个有序序列。

classSolution(object):defheap_sort(self,nums):i,l=0,len(nums)self.nums=nums#构造大顶堆，从非叶子节点开始倒序遍历，因此是l//2-1就是最后一个非叶子节点foriinrange(l//2-1,-1,-1):self.build_heap(i,l-1)#上面的循环完成了大顶堆的构造，那么就开始把根节点跟末尾节点交换，然后重新调整大顶堆forjinrange(l-1,-1,-1):nums[0],nums[j]=nums[j],nums[0]self.build_heap(0,j-1)returnnumsdefbuild_heap(self,i,l):"""构建大顶堆"""nums=self.numsleft,right=2*i+1,2*i+2##左右子节点的下标large_index=iifleft<=landnums[i]<nums[left]:large_index=leftifright<=landnums[left]<nums[right]:large_index=right#通过上面跟左右节点比较后，得出三个元素之间较大的下标，如果较大下表不是父节点的下标，说明交换后需要重新调整大顶堆iflarge_index!=i:nums[i],nums[large_index]=nums[large_index],nums[i]self.build_heap(large_index,l)