首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Java算法--堆排序

Java算法--堆排序

作者头像
solve
发布2019-10-30 13:03:35
3890
发布2019-10-30 13:03:35
举报
文章被收录于专栏:大数据技术栈大数据技术栈
package arithmetic;

import breeze.stats.distributions.Rand;

import java.util.Collections;
import java.util.Random;

public class HeapSort {

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6,21,24,546,65,34,65,768,9,5,2,3,5,6,344,32,12,14, 7, 8, 9};
        shuffle(arr);
        sort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    private static void shuffle(int[] arr) {
        for (int i : arr) {
            int i1 = (int) (Math.random() * (arr.length));
            int i2 = (int) (Math.random() * (arr.length));
            swap(arr, i1, i2);
        }
    }

    public static void sort(int[] arr) {
        //1.变大根堆
        bigHeap(arr);
        //sort
        int heapsize = arr.length - 1;
        while (heapsize > 0) {
            //remove top
            swap(arr, heapsize, 0);
            heapsize--;
            goBottom(arr, heapsize, 0);
        }
    }

    private static void goBottom(int[] arr, int heapsize, int currentIndex) {
        int left = (currentIndex * 2 + 1);
        if (left > heapsize) return;

        int right = left + 1;
        int largest = right < heapsize && arr[right] > arr[left] ? right : left;
        largest = arr[largest]>arr[currentIndex]?largest:currentIndex;

        if(largest == currentIndex)return;

        swap(arr,largest,currentIndex);

        goBottom(arr,heapsize,largest);
    }

    private static void bigHeap(int[] arr) {
        int heapSize = 0;
        while (heapSize < arr.length - 1) {
            heapSize++;
            goTop(arr, heapSize);
        }
    }

    private static void goTop(int[] arr, int changeIndex) {
        int parentIndex = (changeIndex - 1) / 2;
        if (arr[parentIndex] < arr[changeIndex]) {
            swap(arr, parentIndex, changeIndex);
            goTop(arr, parentIndex);
        }
    }

    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018.05.07 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档