# 8. 堆排序

一句话总结：

> 先建立最大堆，adjustHeap，此时第一个元素\[0]是全局最大值
>
> 然后第一个元素和最后一个切换，重新调整堆0-n-1，第一个元素和倒数第二个切换，重新调整堆0-n-2.....
>
> 使得全局最大放到最后面，全局第二大放到倒数第二位，...
>
> 直到第一个元素和第二个交换，调整堆
>
> 这样就得到了顺序的数组

python

```python
def sort(array):
    # 遍历非叶子节点
    for i in range(int(len(array) / 2) - 1, -1, -1):
        adjustHeap(array, i, len(array))

    # 堆积树建立完成，开始排序。
    # 既从n-0，不断和[0]元素交换，重新堆排序（既把第2、3..n大的翻转到最上面）
    # 一开始最大元素是[0]，然后被换到最后一个
    for j in range(len(array) - 1, 0, -1):
        array[0], array[j] = array[j], array[0]
        adjustHeap(array, 0, j)


def adjustHeap(array, i, length):
    # 获取非叶子节点的数据
    temp = array[i]
    # 非叶子节点的左子节点
    k = 2 * i + 1
    # 遍历对比k后面的节点，把temp放入合理位置
    while k < length:
        #  k + 1 < length 确保有左右节点才比较
        if k + 1 < length and array[k] < array[k + 1]:  # 如果左子节点比右子节点小，k就切换到右子节点
            k += 1
        # 如果子节点有更大的
        if array[k] > temp:
            # 父节点替换为更大的
            array[i] = array[k]
            # 记录当前最大点位置
            i = k
        else:
            break
        # k切换到下一个左子节点
        k = 2 * k + 1
    # 此时i是空位，i上层的都比temp大，temp放到这里
    array[i] = temp


data = [16, 25, 39, 27, 12, 8, 45, -10, 63]
sort(data)
print(data)
```

java

```java
//排序类抽象
public abstract class Sort<T extends Comparable<T>> {
    public abstract void sort(T[] nums);

    public boolean less(T v,T w){
        return v.compareTo(w)<0;
    }

    public void swap(T[] a,int i,int j){
        T t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
}


//堆排序实现类
public class HeapSort<T extends Comparable<T>> extends Sort<T>{
    @Override
    public void sort(T[] nums) {
        int n=nums.length-1;
        for(int k=n/2;k>=1;k--){
            sink(nums,k,n);
        }
        while(n>1){
            swap(nums,1,n--);
            sink(nums,1,n);
        }
    }

    public void sink(T[] nums,int k,int n){
        while(2*k<=n){
            int j=2*k;
            if(j<n&&less(nums,j,j+1)) j++;
            if(!less(nums,k,j)) break;
            swap(nums,k,j);
            k=j;
        }
    }

    public boolean less(T[] nums,int i,int j){
        return nums[i].compareTo(nums[j])<0;
    }

    public static void main(String[] args){
        //第一位不参与排序
        //排序：5,1,8,7,10,6,9,5,20,3,0
        Integer[] arr={
                999,5,1,8,7,10,6,9,5,20,3,0
        };
        Sort<Integer> sort=new HeapSort<>();
        sort.sort(arr);
        ArrayUtils.printArray(arr,1);
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://im-qianuxn.gitbook.io/pytorch/ji-suan-ji/shua-ti/pai-xu-lei/8-dui-pai-xu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.