上浮，下沉的堆排序

小咪咪 2024-04-18 23:53 0阅读 0赞

package com.hnist.lzn.Resulbe;
    
    public class HeapSort {
    
    
        public static void Sort(int[] arr){
    
            if(arr == null || arr.length == 0)
                return;
            HeapSorts(arr);
        }
    
        public static void HeapSorts(int[] arr){
    
            // 堆排逻辑
            if(arr ==null || arr.length <2)
                return;
    
            for(int i = 0;i < arr.length ;i++)
            {
                heapInsert(arr,i); // 0-i
            }
    
            int heapSize = arr.length;
            swap(arr,0,--heapSize);
            while(heapSize > 0)
            {
                heapfly(arr,0,heapSize);
                swap(arr,0,--heapSize);
            }
    
        }
    
        // 上浮
        public static void heapInsert(int[] arr,int index){
    
            while(arr[index] > arr[(index-1)/2]){
    
                swap(arr,index,(index-1)/2);
    
                index = (index-1)/2;
            }
        }
    
        // 下沉
        public static void heapfly(int[] arr,int i,int heapSize){
    
            int left = i*2+1;
    
            while(left < heapSize){
    
               int largetest = left+1<heapSize&& arr[left]<arr[left+1]?left+1:left;
    
               largetest = arr[largetest]>arr[i]?largetest:i;
               if(largetest== i)
                   break;
    
               swap(arr,largetest,i);
               i = largetest;
               left = i*2+1;
            }
        }
    
    
        public static void swap(int[] arr,int a,int b){
    
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }
    
        public static void main(String[] args) {
    
            int[] nums = {1,2,3,7,2,0,8};
    
            Sort(nums);
            for(int i:nums){
                System.out.print(i);
            }
        }
    
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，0人围观）

还没有评论，来说两句吧...

相关阅读

相关排序-堆排序

1.堆排序前言前面博客中讲到简单选择排序，它在待排序的n个记录中选择一个最小的记录需要比较n-1次。本来这也可以理解，查找第一个数据需要比较这么多次是正常的，否则如何知

旧城等待，/ 2022年09月30日 06:45/ 0 赞/ 160 阅读

相关堆排序——C++关于堆排序的库函数排序

C++中对于堆排序算法，其实是有一个专门的库函数：sort\_heap void sort_heap (RandomAccessIterator first, Ran

绝地灬酷狼/ 2022年07月14日 03:44/ 0 赞/ 98 阅读

相关【排序】堆排序

堆的定义设有n个元素的序列 k1，k2，…，kn，当且仅当满足下述关系之一时，称之为堆。 ![图示][SouthEast] 解释：如果让满足以上条件的元素序列（k

分手后的思念是犯贱/ 2022年06月18日 11:47/ 0 赞/ 191 阅读

相关看懂堆排序——堆与堆排序（三）

看懂堆排序——堆与堆排序（三）看懂堆排序——堆与堆排序（三）堆排序的基本思想代码详解

偏执的太偏执、/ 2022年05月25日 06:52/ 0 赞/ 216 阅读

相关排序——堆排序

堆排序代码 include <iostream> using namespace std; include <stdio.h> in

墨蓝/ 2022年05月21日 12:05/ 0 赞/ 193 阅读

相关下沉的船

Problem Description 一艘船很不幸的撞上了暗礁，船长组织大家上救生艇，而且船长决定女人（woman）和小孩（child）先上船，然后其次是男人（man）,最

柔光的暖阳◎/ 2022年04月14日 03:44/ 0 赞/ 110 阅读

相关堆排序

什么是堆排序，堆排序能解决什么问题？在排序的过程中，不能把进行排序的过程中，得一些信息保留下来吗？来加快排序的速度吗？答案是可以的。通过利用完全二叉堆的结构来保留信息。

迷南。/ 2021年10月29日 07:20/ 0 赞/ 297 阅读

相关堆和堆排序

堆排序堆排序基本介绍 1. 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为 O(nlogn)，它也

柔光的暖阳◎/ 2021年10月19日 21:12/ 0 赞/ 301 阅读

相关排序-堆排序

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] 在说明堆排序的过程前得先了解什么是堆：先看下图（来源

清疚/ 2021年09月20日 03:22/ 0 赞/ 372 阅读

相关堆排序

堆排序的特点是：在排序过程中，将待排序数组看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中父结点和子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）

不念不忘少年蓝@/ 2021年09月17日 00:16/ 0 赞/ 389 阅读