堆排序实现

说到堆排序，我们就得先知道什么是堆，而堆又分为最大堆（大顶堆）和最小堆（小顶堆）

堆

在元素序列满足如下关系时，可称为堆

最大堆

堆顶元素为最大值，如下图所示：

最小堆

堆顶元素为最小值，如下图所示：

堆排序

复杂度

堆排序是利用堆所设计的一种排序方法，它的各类复杂度如下：

时间复杂度(最好、最差、平均)	空间复杂度
O(nlogN)	O(n)

算法思想

1. 将无序队列构建为堆，若是n个元素的序列，然后从n/2个元素开始，到第一个元素结束，进行反复筛选。
2. 输出顶堆的最大值或最小值，与堆中最后一个元素交换位置，使得处理的序列范围减一
3. 将剩下的n-1个元素重复上述步骤，重新调整为新的堆，筛选出新的最大值或最小值
4. 得到新的序列

代码实现

public void heapSort(int[] arr) {
    for(int i=arr.length/2-1;i>=0;i--){
        heapAdjust(arr,i,arr.length);
    }
    for(int j=arr.length-1;j>0;j--){
        swap(arr,0,j);
        heapAdjust(arr,0,j);
    }
}

private void heapAdjust(int[] arr, int i, int length) {
    int temp = arr[i];
    for(int k=i*2+1;k<length;k=k*2+1){
        if(k+1<length && arr[k]<arr[k+1]){
            k++;
        }
        if(arr[k] >temp){
            arr[i] = arr[k];
            i = k;
        }else{
            break;
        }
    }
    arr[i] = temp;
}

private void swap(int[] nums, int i, int j) {
    nums[i] ^= nums[j];
    nums[j] ^= nums[i];
    nums[i] ^= nums[j];
}