04堆排序的原理
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}
来自:排序算法-高级排序(快排、堆排等)