算法与数据结构学习（40）堆排序的实现

堆排序的基本思想

堆排序的基本思想是&＃xff1a;
1.将待排序序列构造成一个大顶堆
2.此时&＃xff0c;整个序列的最大值就是堆顶的根节点。
3.将其与末尾元素进行交换&＃xff0c;此时末尾就为最大值。
4.然后将剩余n-1个元素重新构造成一个堆&＃xff0c;这样会得到n个元素的次小值。如此反复执行&＃xff0c;便能得到一个有序序列了。

实际应用理解

要求&＃xff1a;给你一个数组 {4,6,8,5,9} , 要求使用堆排序法&＃xff0c;将数组升序排序。

初始结构如下&＃xff1a;

代码实现

/*** title:堆排序的实现* date&＃xff1a;2020.3.12*/
package sort;import java.util.Arrays;public class HeapSort {public static void main(String[] args) {//要求将数组进行升序排列int arr[] &＃61; {4,6,8,5,9,-1,90,3,-45,45};heapSort(arr);}//编写一个堆排序的方法public static void heapSort(int arr[]) {int temp &＃61; 0;System.out.println("堆排序&＃xff01;&＃xff01;&＃xff01;");//分布完成/** adjustHeap(arr,1,arr.length);* System.out.println("第一次调整"&＃43;Arrays.toString(arr));* * adjustHeap(arr,0,arr.length);* System.out.println("第二次调整"&＃43;Arrays.toString(arr));*///完成最终代码for(int i &＃61; arr.length/2 -1;i>&＃61;0;i--) {adjustHeap(arr,i,arr.length);}/*** 2.将堆栈元素与末尾的元素交换&＃xff0c;将最大元素沉到数组末端* 3.重新调整结构&＃xff0c;使其满足堆栈定义&＃xff0c;然后继续交换栈顶元素与末尾元素&＃xff0c;反复执行调整&＃43;交换步骤&＃xff0c;直到整个序列有序*/for(int j &＃61; arr.length-1;j>0;j--) {//交换temp &＃61; arr[j];arr[j] &＃61; arr[0];arr[0] &＃61; temp;adjustHeap(arr,0,j);}System.out.println("数组&＃61;"&＃43;Arrays.toString(arr));}/*** 功能&＃xff1a; 完成将以i对应的非叶子结点的树调整成大顶堆* &＃64;param arr 待调整的数组* &＃64;param i 表示非叶子节点在数组中的索引* &＃64;param length 表示对多少个元素进行调整&＃xff0c;length在逐渐减少*///将一个数组&＃xff08;二叉树&＃xff09;&＃xff0c;调整成一个大顶堆public static void adjustHeap(int arr[],int i,int length) {int temp &＃61; arr[i];//先取出当前变量的值保存在临时变量//开始调整//说明// k &＃61; i*2&＃43;1表示k是i结点的左子节点for(int k &＃61; i*2&＃43;1;k<length;k&＃61;k*2&＃43;1) {if(k&＃43;1<length &&arr[k] < arr[k&＃43;1] ) {//说明左子节点的值小于右子节点的值k&＃43;&＃43;;//k就指向右子节点}if(arr[k]>temp) {//如果子节点大于父节点arr[i] &＃61;arr[k];//把较大的值赋给当前结点i&＃61;k;//i指向k&＃xff0c;继续循环比较}else {break;}//当for循环结束后&＃xff0c;我们已经将以i为父节点的最大值&＃xff0c;放在了最顶&＃xff08;局部的&＃xff09;arr[i] &＃61; temp;//将temp赋值到调整后的位置}}
}

堆排序的时间复杂度为O&＃xff08;nlogn&＃xff09;