堆排序O(nlog(n))

堆排序O(nlog(n))

堆排序的基本思路:

1. 将无序序列构建成一个堆,根据升序降序需求选择大顶堆和小顶堆
2. 将堆顶元素和末尾元素交换,将最大元素沉到数组末端
3. 重新调整结构,使其满足堆的定义,然后即系交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,知道整个序列有序

package com.ywystu.Tree;import java.util.Arrays;/*** @author 是狸猫啊！* @Version 1.0* 实现堆排序*/
public class HeapShort {
    public static void main(String[] args) {
    int[] arr = {
    4, 6, 8, 5, 9};HeapSort(arr);}//完成堆排序public static void HeapSort(int[] arr) {
    
// adjustHeap(arr,1, arr.length);
// System.out.println(Arrays.toString(arr));//一次完成我们的最终代码int temp = 0;System.out.println("堆排序");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);}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];//进行子树循环的数值比对for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
    //这里比粗防止数组进行越界if (k + 1 < length && arr[k] < arr[k + 1]) {
    k++;//指向该最小树的右子节点}if (arr[k] > temp) {
    arr[i] = arr[k];i = k;} else {
    break;}}//当for循环结束后,我们已经将以i为父节点的最大值,放在了 最顶局部arr[i] = temp;}
}

八百万个数据一共是3秒解决