0088 堆排序

 

 

 

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/*
 * 堆排序
 * 1.堆排序是利用堆这种数据结构而设计的一种排序算法，是一种选择排序
 *   最好，最坏，平均时间复杂度均为O（nlogn）, 是不稳定排序
 * 2.堆是具有以下性质的完全二叉树，每个节点的值都大于或等于其左右孩子结点的值，
 *   称为大顶堆，注：没有要求结点的左孩子值和右孩子值的大小关系
 * 3.每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
 * 
 * 大顶堆特点：arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2]
 * 小顶堆特点：arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2]
 *      //i对应第几个结点，从0开始编号
 *      //一般升序采用大顶堆，降序采用小顶堆
 * 
 * 堆排序基本思想
 * 1.将待排序序列造成一个大顶堆
 * 2.整个序列的最大值就是堆顶的根节点
 * 3.将其与末尾元素进行交换，此时末尾为最大值
 * 4.将剩余n-1个元素重新构造一个大顶堆，反复执行就得到了有序序列
 * 
 * 要求：一个数组[4,6,8,5,9],利用 堆排序 将数组 升序 排列
 * 原始：[4,6,8,5,9]
 * 步骤一
 * 1.从最后一个非叶子结点开始（arr.length/2-1=5/2-1=1，即为6）从左至右，从下至上进行调整（即比较左右子节点，大的交换）
 * --->[4,9,8,5,6]
 * 2.找到第二个非叶子节点（即4），[4,9,8]中9大，所以交换
 * -->[9,4,8,5,6]
 * 3.这时导致子根[4,5,6]结构混乱，[4,5,6]中6大，交换
 * -->[9,6,8,5,4]
 * 此时就将一个无序序列构造成了一个大顶堆
 * 
 * 步骤二
 * 将堆顶元素与末尾元素进行交换，使末尾元素最大，继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素，如此反复进行交换、重建、交换
 * 即-->[4,6,8,5][9]-->重新调整结构-->[8,6,4,5][9]-->[5,6,4][8,9]-->如此反复-->[4,5,6,8,9]
 */
public class HeapSort_ {
    public static void main(String[] args) {
        int[] arr = {4,6,8,5,9};
        heapSort(arr);//[4, 5, 6, 8, 9]
        System.out.println(Arrays.toString(arr));
        
        //测试堆排序的速度
        int[] arr2 = new int[80000];
        for(int i = 0;i < 80000;i++) {
            arr2[i] = (int)(Math.random() * 80000);
        }
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(date1);
        System.out.println("排序前的时间=" + date1Str);
        
        heapSort(arr2);
        
        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
        System.out.println("排序后的时间=" + date2Str);
    }
    
    //编写堆排序的方法(升序排列-->大顶堆)
    public static void heapSort(int arr[]) {
        int temp = 0;
/*        //分步完成
        adjustHeap(arr, 1, arr.length);
        System.out.println("第一次" + Arrays.toString(arr));//4,9,8,5,6
        adjustHeap(arr, 0, arr.length);
        System.out.println("第二次" + Arrays.toString(arr));//9,6,8,5,4
*/
        //步骤一
        for(int i = arr.length / 2 - 1;i >= 0;i--) {
            adjustHeap(arr, i, arr.length);
        }
        
        //步骤二
        for(int j = arr.length - 1;j > 0;j--) {
            //交换
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }
    }
    
    //将一个数组（二叉树）调整成一个大顶堆
    //arr:待调整的数组，i:非叶子节点在数组中的索引，length:对多少个元素进行调整（length是逐渐减少的）
    //如：int[] arr = {4,6,8,5,9};==>i=1==>int[] arr = {4,9,8,5,6};==>i=0==>int[] arr = {9,6,8,5,4};
    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;k < length;k = k * 2 + 1) {
            if (k + 1 < length && arr[k] < arr[k+1]) {//说明左子节点的值 小于 右子节点的值
                k++;//让k指向右子节点
            }
            if (arr[k] > temp) {//子节点 大于 父节点，交换
                arr[i] = arr[k];//把大的值赋给父节点
                i = k;//让i指向k，继续循环比较
            }else {
                break;
            }
        }
        //当for循环结束后，已经将i为父节点的树的最大值放在了堆顶
        arr[i] = temp;//将temp放到调整后的位置
    }