堆排序算法.docx

文档介绍：
堆排序算法
预备学问
堆排序

堆排序是利用堆这种数据构造而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间困难度均为O(nlogn)，它也是不稳定排序。首先简洁了解下堆构造。
中6最大，交换4和6。



此时，我们就将一个无需序列构造成了一个大顶堆。

步骤二 将堆顶元素与末尾元素进展交换，使末尾元素最大。然后接着调整堆，再将堆顶元素与末尾元素交换，得到其次大元素。如此反复进展交换、重建、交换。








，使其接着满意堆定义



，得到其次大元素8.



后续过程，接着进展调整，交换，如此反复进展，最终使得整个序列有序



再简洁总结下堆排序的根本思路：

，依据升序降序需求选择大顶堆或小顶堆;

，将最大元素"沉"到数组末端;




，使其满意堆定义，然后接着交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
代码实现
package sortdemo;

import ;

/**
* Created by chengxiao on 2022/12/17.
* 堆排序demo
*/
public class HeapSort {
public static void main(String []args){
int []arr = {9,8,7,6,5,4,3,2,1};
sort(arr);
((arr));
}
public static void sort(int []arr){
//



for(int i=-1;i>=0;i--){
//从第一个非叶子结点从下至上，从右至左调整构造
adjustHeap(arr,i,arr