【数据结构】【排序】堆排序

       堆排序核心思想是根据现有数组构建大顶堆或者小顶堆，堆顶元素就是该数组的最大值（大顶堆）或者最小值（小顶堆）；将该最值按照顺序放到一个“有序区”中，然后将“无序区”中最后一个元素放到堆顶，不断调整使其满足大顶堆或者小顶堆的条件，调整过后处于堆顶的就是剩余无序区中的最大值或者最小值，将该值放入到有序区中......不断如此这般的调整，最终当“无序区”中的元素数量为0的时候，“有序区”中的所有元素就是最终的排序结果。

根据上述描述，在堆排序中有两个问题需要解决：

1. 如何初始化堆（如何根据现有数组构建堆结构）
2. 如何调整数组使其满足堆结构的要求。

预备知识点：

   1.大顶堆是一种“完全二叉树”，所以满足以下特点：

      （1）若i>1，则该节点的父节点为tree[i/2]

      （2）若i为偶数，而且i<n，那么该节点的兄弟节点为tree[i+1]

   2.大顶堆要求节点值必须大于等于左子树中的所有元素值，也必须大于等于右子树中的所有元素值

 

以下程序通过构建大顶堆获取最大值的方法对若干个无序数字进行升序排序：

 

import java.util.Scanner;
/**
	该排序数组下标从1开始，这是和之前的排序方法不同的地方
*/

public class HeapSort{
        public static void main(String args[]){
                Scanner scanner=new Scanner(System.in);
                int total=scanner.nextInt();
                int[] array=new int[1025];
                for(int i=1;i<=total;i++){
                        array[i]=scanner.nextInt();
                }
		heapSort(array,total);
                output(array,total);
        }
        public static void output(int[] array,int total){
                for(int i=1;i<=total;i++){
                        System.out.print(array[i]+" ");
                }
                System.out.println();
        }
	public static void heapSort(int[] array,int total){
		//创建初始大顶堆
		buildHeap(array,total);	
		//不断调整大顶堆，获取最终的有序序列
		for(int i=total;i>1;i--){
			int temp=array[1];	
			array[1]=array[i];
			array[i]=temp;
			adjustHeap(array,1,i-1);
		}	
	}
	public static void buildHeap(int[] array,int total){
		for(int i=total/2;i>=1;i--){
			adjustHeap(array,i,total);
		}
	}
	public static void adjustHeap(int[] array,int start,int end){
		int temp=array[start];
		for(int j=2*start;j<=end;j*=2){
			if(j<end&&array[j]<array[j+1]){
				j++;
			}
			if(temp>=array[j]){
				break;
			}
			array[start]=array[j];
			start=j;			
		}
		array[start]=temp;
	}
}

 测试数据，还是使用MyRandom类产生的1024个数据：

import java.util.Random;

public class MyRandom {
	public static void main(String args[]){
		int[] array=new int[1024];
		for(int i=0;i<1024;i++){
			array[i]=i;
		}
		for(int i=0;i<=1023;i++){
			int m=new Random().nextInt(1024);
			int n=new Random().nextInt(1024);
			int temp=array[m];
			array[m]=array[n];
			array[n]=temp;
		}
		System.out.println("1024");
		for(int i=0;i<1024;i++){
			System.out.print(array[i]+" ");
		}
		System.out.println();
	}
}

 运行方法：

java MyRandom | java HeapSort