数据结构-八大排序之堆排序

 堆排序

1.1 基础知识

原理：

1.  利用完全二叉树构建大顶堆

2.  堆顶元素和堆底元素进行交换，除堆底元素之外其余元素继续构建大顶堆

3.  重复2，直到所有元素都不参与构建  整个数组排序完成

---

完全二叉树：

数据从上到下，从左到右排列

大顶堆：

父节点的值大于或等于其左右孩子的值

堆顶元素和堆底元素进行交换

数组的形式：

完全二叉树：

arr [ i ] 的左孩子  arr [ 2i+1 ]

arr [ i ] 的右孩子  arr [ 2i+2 ]

arr [ i ] 的父节点  arr [ (i-1) / 2 ]

大顶堆：

arr [ i ] >= arr [ 2i+1 ]&& arr [ i ]>= arr [ 2i +2 ]

堆顶元素和堆底元素进行交换

如何构建？

从后往前依次检测所有的节点是否符合大顶堆，如果符合，则检测下一个元素

                                                                            如果不符合，则进行调整让其符合大顶堆

如何检测和调整？

1.定义parent 游标指向检测的节点

2. 定义parent 的左孩子child ( 有孩子一定会有 左孩子 ）

3.判断有没有右孩子  ，如果有右孩子，左右孩子进行比较，child 指向左右孩子当中的最大值

4. parent 和child 指向的值进行比较

                若parent的值大，则符合大顶堆

                若parent的值小，父子节点进行交换，parent指向child， child 指向其左右孩子的最大值，继续进行比较

        直到 child为空 或 parent指向的 值大 ，则停止

调整：

1. parent 指向堆顶元素

2. child 指向其左右孩子的最大值

3. parent 和 child 指向的值进行比较

4. 若 parent 的值大，则符合大顶堆 

                若parent的值小，父子节点进行交换，parent指向child， child 指向其左右孩子的最大值，继续进行比较

        直到 child为空 或  超出有效范围  或 parent指向的 值大 ，则停止

---

时间复杂度

第一大步+第二大步

O(nlogn)

1.2 代码

 

public class HeapSort {
public static void main(String[] args) {
int[] arr= {5,7,4,2,0,3,1,6};
//第一大步:构建大顶堆
for(int p=arr.length-1;p>=0;p--) {
adjust(arr,p,arr.length);
}
//第二大步  堆顶和堆底进行交换  除堆底外剩余元素继续构建大顶堆
for(int i=arr.length-1;i>=0;i--) {
int temp=arr[i];
arr[i]=arr[0];
arr[0]=temp;
adjust(arr,0,i);
}
System.out.println(Arrays.toString(arr));
/*//第一轮
int temp=arr[arr.length-1];
arr[arr.length-1]=arr[0];
arr[0]=temp;
//第二轮
int temp2=arr[arr.length-2];
arr[arr.length-2]=arr[0];
arr[0]=temp2;*/
}
//堆的维护
public static void adjust(int[] arr,int parent,int length) {
int child=2*parent+1;//左孩子
while(child<length) {
int rchild=2*parent+2;
if(rchild<length&&arr[rchild]>arr[child]) {
child++;
}
//child指向左右孩子中最大的
//父子节点进行比较
if(arr[parent]<arr[child]) {
//父子节点进行交换
int temp=arr[parent];
arr[parent]=arr[child];
arr[child]=temp;
//parent指向child,child继续指向左右孩子的最大值
parent =child ;
child=2*child+1;

}else 
break;
}


}
}

原文地址：https://blog.csdn.net/m0_75163045/article/details/142766652

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！