堆 排 序

堆可以看成是一个二叉树，假如根节点为i，若从 1 开始对堆中的节点进行编号，则节点的「左子节点」为 2i，「右子节点」为 2i+1。

1.首先就要建立一个堆，从非叶子节点开始，非叶子节点的索引值是len/2-1，叶子节点的索引值为len/2。
数组升序排列的话那我们就要建立大根堆。

for (int i = len /2 ; i>=0;i--){
	adjust(nums,i,len - 1);
}

这样就引出了我们的建堆函数adjust。第一个参数毋庸置疑肯定是数组，第二个参数就是开始的位置，表明从非叶子节点依次开始，将对它的叶子节点进行最大值推选。最后一个参数就是表示当前未排序数组的尾部坐标。

public static void adjust(int[] nums, int k, int limit){
	for(int i = 2k;i<=limit;i*= 2){
	int temp = nums[k];
		if (i 
			i++;
		}
		if (temp >= nums[i]){
			break;
		}else{
			nums[k] = nums[i];
			k = i;
		}
    }
} 

2.建立起大根堆后，便对数组中的元素进行排序，将堆顶元素和末尾元素进行交换，此时末尾元素就是最大值。

for (int i = len - 1; i>=1;i--){
	int temp = nums[0];
	nums[0] = nums[i];
	nums[i] = temp;
	adjust(nums,0,i-1);
}

代码参考

 //堆排序
    private void adjust(int[] nums,int k,int limit){
        int temp = nums[k];
        for (int i = 2 * k; i <= limit ; i*=2) {
            if (i < limit && nums[i] < nums[i+1]){
                i++;
            }
            if(temp >= nums[i]){
                break;
            }else{
                nums[k] = nums[i];
                k = i;
            }
        }
        nums[k] = temp;
    }
    public void heapSort(int[] nums){
        int len = nums.length;
        for (int i = len/2; i>=0 ; i--) {
            adjust(nums,i,len-1);
        }
        for (int i = len-1; i >=1 ; i--) {
            int temp = nums[0];
            nums[0] = nums[i];
            nums[i] = temp;
            adjust(nums,0,i-1);
        }
    }