堆排序

堆排序的介绍

• 堆排序利用堆这中数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它是不稳定排序
• 堆是具有以下性质的完全二叉树:每个节点的值都大于或等于其它左右孩子节点的值,称为大顶堆,注意:没有要求节点的左孩子和右孩子的值的大小关系.
• 每个节点的值都小于或等于其左右孩子节点的值,称为小顶堆
• 大顶堆举例说明
• 
  大顶堆特点:arr[i]>arr[2i+1]&&arr[i]>=arr[2i+2]
• 小顶对举例说明
• 
• 小顶堆特点:arr[i]<=arr[2i+1]&&arr[2i+2]
• 一般升序排序我们采用大顶堆,降序排序我们采用小顶堆

堆排序的思想

堆排序的基本思想

1. 将待排序的序列构造成一个大顶堆
2. 此时,整个序列的最大值就是堆顶的根节点
3. 将其与末尾元素进行交换,此时末尾就是最大值
4. 然后将剩余的n-1个元素重写构造成一个大顶堆,这样就会得到n个元素的次小值,如此反复的执行,便能得到一个有序序列了.
5. 可以看到在构建大顶堆的过程中,元素的个数逐渐减少,最后就得到一个有序序列.

堆排序步骤图解说明

1. 构造初始堆,将给定一个无序序列构造成一个大顶堆(一般升序大顶堆,降序小顶堆)
2. 原始数组[4,6,8,5,9]

• 假设给定无序序列结构如下
  
• 此时我们从最后一个非叶子节点开始(叶节点自然不用调整,第一个非叶子节点arr.length/2-1=5/2-1=1,也就是下面的6节点,)从左至右,从上至下进行调整
  
• 再找到第二个非叶子节点,由于[4,9,8]中9元素最大,4和9交换
  
• 这时,交换导致了子根[4,5,6]结构混乱,继续调整,[4,5,6]中6最大,交换4,6

此时,我们就得到了一个大顶堆

3. 将堆顶元素与末尾元素进行交换,使末尾元素最大,然后继续调整堆,再将堆顶元素与末尾元素交换,得到第二大元素,得到第二大元素,如此反复进行交换,重建,交换.

• 将堆顶元素9和末尾元素4进行交换,
  
• 重新调整结构,使其满足堆定义
  
• 再将堆顶元素8与末尾元素5进行交换,得到第二大元素8
  
• 后续过程中,继续进行调整,交换,如此反复进行,最终使得整个序列有序
  
  在简单总结一下堆排序思路
  1, 将无序序列构建成一个堆,根据升序降序的需求选择大顶堆或小顶堆
  2, 将堆顶元素与末尾元素进行交换,将最大元素"沉"大数组末端
  3,重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序
  结合代码分析
  
  代码实现

package com.atguigu.tree;import java.util.Arrays;public class HeapSort {public static void main(String[] args) {int[] arr={4,6,8,5,9};heapSort(arr);//插入排序的速度测试int[] arr2=new int[80000];for (int i=0;i<80000;i++){arr2[i]=(int)(Math.random()*40000);//生成一个[0,20000)的随机整数}long startTime=System.currentTimeMillis();heapSort(arr2);long endTime=System.currentTimeMillis();System.out.println("排序用的时间:"+(endTime-startTime));}//编写一个堆排序的方法public static void heapSort(int[] arr){int temp=0;System.out.println("堆排序");//分部完成adjustHeap(arr,1,arr.length);System.out.println("第一次调整后:"+ Arrays.toString(arr));adjustHeap(arr,0,arr.length);System.out.println("第二次调整后:"+Arrays.toString(arr));//完成我们的最终代码//将一个无序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆for(int i=arr.length/2-1;i>=0;i--){adjustHeap(arr,i,arr.length);}System.out.println("数组:"+Arrays.toString(arr));//将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端//重写调整结构,使其能满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复调整+交换步骤,直到整个序列有序for(int j=arr.length-1;j>0;j--){//交换temp=arr[j];arr[j]=arr[0];arr[0]=temp;adjustHeap(arr,0,j);//真实情况每次调整总是重顶上调整的.}System.out.println("数组:"+Arrays.toString(arr));}//将一个数组(二叉树),调整成一个大顶堆/*** 完成将以i对应的非叶子节点数调整为大顶堆* @param arr 待调整的数组* @param i 表示非叶子节点的在数组中索引* @param length 多少个元素进行调整,length是在逐渐减少*/public  static void adjustHeap(int[] arr,int i,int length){int temp=arr[i];//先取出当前元素的值,保存在临时变量里面//开始调整/*说明,k=i*2+1是i节点的左子节点.*/for(int k=i*2+1;kif((k+1)//说明左子节点它的值小于右子节点的值k++;//k指向右子节点}if(arr[k]>temp){//如果子节点大于父节点arr[i]=arr[k];//把较大的值赋值给当前的父节点i=k;//让i执行k,继续循环比较}else {break;}}//当for循环结束后,我们已经将以i为父节点的树的最大值,调整到了最上面arr[i]=temp;//将temp放到调整之后的位置}
}