堆排序java实现

//堆排序：
//基本思想：
//首先要了解堆这种数据结构：
//堆是实质上是一个满足如下条件的完全二叉树：树中任意非叶节点的关键字均不大于（或不小于）其左右孩子节点的关键字，即：
//给定关键字数列：T1,T2,...,Tn，
//当且仅当数列满足如下性质：（1）Ti<=T2i且Ti<=T2i+1或者（2）Ti>=T2i且Ti>=T2i+1(1<=i<=n/2取最小值)
//堆分为大根堆和小根堆：
//大根堆是指根节点的关键字是所有堆节店关键字中的最大者（升序）
//小根堆是指：根节点的关键字是所有节点关键字的最小者（降序）
//堆排序顾名思义就是基于堆这种数据结构进行排序，在排序过程中，将数列看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中
//双亲节点和孩子节点之间的关系，在当前无序区中选择关键字最大或最小的记录。
//利用小根堆排序的步骤：
//1.构造一个大根堆
//2.将当前无序的堆顶记录T1和该区间的最后一个记录交换，然后将新的无序区调整为堆（称为重建堆）
//3.重复上述操作

image

//平均时间复杂度：O(nlogn)
//由于每次重新恢复堆的时间复杂度为O(logn),共n-1次重新恢复堆的操作，
//再加上前面简历堆时n/2次向下调整，每次调整的时间复杂度也为O(logn),两次操作时间相加还是O(nlogn)

public class HeapSort {
public static void main(String[] args) {

int[] arr = new int[]{6,2,4,1,9,3,6,7,0};

System.out.println("排序前=====");

print(arr);

System.out.println("");

System.out.println("排序后");

heapSort(arr,arr.length);

print(arr);

}

public static void heapSort(int[] arr,int n) {

int temp = 0;

MakeMinHeap(arr, n);

for(int i=n-1; i>0; i--){

temp = arr[0];

arr[0] = arr[i];

arr[i] = temp;

MinHeapFixDown(arr, 0, i);

}

}

//构建最小堆

public static void MakeMinHeap(int[] arr,int n){

for(int i=(n-1)/2; i>=0; i--){

MinHeapFixDown(arr,i,n);

}

}

//从节点i开始调整,n为节点总数，从0开始

public static void MinHeapFixDown(int[] arr,int i,int n){

int j = 2*i+1;//子节点

int temp = 0;

while(j<n){//在左右子节点中寻找最小的

if(j+1<n && arr[j+1]<arr[j]){

j++;

}

if(arr[i] <= arr[j])

break;

//较大节点下移

temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

i = j;

j = 2*i+1;

}

}

public static void print(int[] arr){

for(int i=0; i<arr.length; i++){

System.out.print(arr[i]+",");

}

}

}