算法-排序算法：堆排序（HeapSort ）【O(nlogn)】

2024-09-02 03:18
文章标签 算法 排序 堆排序 nlogn heapsort

本文主要是介绍算法-排序算法：堆排序（HeapSort ）【O(nlogn)】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

MyArray.java

/*** 数组** @author* @version 2018/8/4*/
public class MyArray<E> {private E[] arr;private int size;public MyArray(int capacity){arr = (E[])new Object[capacity];size = 0;}public MyArray() {this(10);}public int getSize(){return size;}public int getCapacity(){return arr.length;}public boolean isEmpty(){return size == 0;}/*** 向数组头部插入一个元素** @param e* @return void* @author ronglexie* @version 2018/8/4*/public void addFirst(E e){add(0,e);}/*** 向数组尾部插入一个元素** @param e* @return void* @author ronglexie* @version 2018/8/4*/public void addLast(E e){add(size,e);}/*** 向数组指定位置插入一个元素** @param index* @param e* @return void* @author ronglexie* @version 2018/8/4*/public void add(int index, E e){if(index < 0 || index > size){throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size");}if(size == arr.length){
//			throw new IllegalArgumentException("Add failed. Array is full.");//数组动态扩容两倍resize(2*arr.length);}for (int i= size-1; i >= index; i--){arr[i+1] = arr[i];}arr[index] = e;size++;}private void resize(int newCapacity) {E[] newData = (E[]) new Object[newCapacity];for (int i = 0; i < size; i++) {newData[i] = arr[i];}arr = newData;}/*** 获取指定位置的元素** @param index* @return E* @author ronglexie* @version 2018/8/4*/public E get(int index){if(index < 0 || index >= size){throw new IllegalArgumentException("Get failed. index is Illegal.");}return arr[index];}/*** 获取第一个元素** @param* @return E* @author ronglexie* @version 2018/8/4*/public E getFirst() {return arr[0];}/*** 获取最后一个元素** @param* @return E* @author ronglexie* @version 2018/8/4*/public E getLast() {return get(size - 1);}/*** 修改指定位置的元素** @param index* @param e* @return void* @author ronglexie* @version 2018/8/4*/public void set(int index, E e){if (index < 0 || index >= size){throw new IllegalArgumentException("Set failed. index is Illegal.");}arr[index] = e;}/*** 查看数组中是否包含某个元素** @param e* @return boolean* @author ronglexie* @version 2018/8/4*/public boolean contains(E e){for (int i = 0; i < size; i++) {if(arr[i].equals(e)){return true;}}return false;}/*** 查找元素在数组中的位置** @param e* @return int* @author ronglexie* @version 2018/8/4*/public int indexOf(E e){for (int i = 0; i < size; i++) {if(arr[i].equals(e)){return i;}}return -1;}/*** 移除数组中的一个元素** @param index* @return int* @author ronglexie* @version 2018/8/4*/public E remove(int index){if (index < 0 || index >= size){throw new IllegalArgumentException("Remove failed. index is Illegal.");}E result = arr[index];for (int i = index + 1; i < size; i++) {arr[i-1] = arr[i];}size--;//修改对象引用，垃圾回收机制回收arr[size] = null;//动态缩小数组一半容量if(size == arr.length/4 && arr.length/2 != 0){resize(arr.length/2);}return result;}/*** 移除数组中的第一个元素** @param* @return E* @author ronglexie* @version 2018/8/4*/public E removeFirst(){return remove(0);}/*** 移除数组中的最后一个元素** @param* @return int* @author ronglexie* @version 2018/8/4*/public E removeLast(){return remove(size - 1);}/*** 移除数组中的某个元素** @param e* @return void* @author ronglexie* @version 2018/8/4*/public void removeElement(E e){int index = indexOf(e);if(index != -1){remove(index);}}/*** 将索引为i和j的两个元素互相交换** @param i* @param j* @return void* @author ronglexie* @version 2018/8/19*/public void swap(int i, int j){if (i < 0 || i >= size || j < 0 || j >= size){throw new IllegalArgumentException("Swap failed. index is Illegal.");}E temp = arr[i];arr[i] = arr[j];arr[j] = temp;}/*** 自定义toString方法** @param* @return java.lang.String* @author ronglexie* @version 2018/8/4*/@Overridepublic String toString(){StringBuilder result = new StringBuilder();result.append(String.format("Array: size = %d , capacity = %d\n",size,arr.length));result.append("[");for (int i = 0; i < size; i++){result.append(arr[i]);if(i != size - 1){result.append(", ");}}result.append("]");return result.toString();}}

MaxHeap.java

/*** 最大堆* 完全二叉树实现、树中的根结点都表示树中的最大元素结点** @author ronglexie* @version 2018/8/19*/
public class MaxHeap<E extends Comparable<E>> {private MyArray<E> arr;public MaxHeap(int capacity){arr = new MyArray<>(capacity);}public MaxHeap() {arr = new MyArray<>();}// 返回堆中的元素个数public int size(){return arr.getSize();}public boolean isEmpty(){return arr.isEmpty();}/*** 查找用数组实现的完全二叉树中该索引下节点的父亲节点的索引** @param index* @return int* @author ronglexie* @version 2018/8/19*/public int parent(int index){if(index == 0){throw new IllegalArgumentException("root doesn't have parent.");}return (index - 1) / 2;}/*** 查找用数组实现的完全二叉树中该索引下节点的左孩子节点的索引** @param index* @return int* @author ronglexie* @version 2018/8/19*/public int leftChild(int index){return (index * 2) + 1;}/*** 查找用数组实现的完全二叉树中该索引下节点的右孩子节点的索引** @param index* @return int* @author ronglexie* @version 2018/8/19*/public int rightChild(int index){return (index * 2) + 2;}/*** 向最大堆中添加元素** @param e* @return void* @author ronglexie* @version 2018/8/19*/public void add(E e){arr.addLast(e);shifUp(arr.getSize() - 1);}/*** 上浮节点** @param k* @return void* @author ronglexie* @version 2018/8/19*/private void shifUp(int k) {while (k > 0 && arr.get(parent(k)).compareTo(arr.get(k)) < 0){arr.swap(k,parent(k));k = parent(k);}}/*** 查找堆中最大值** @param* @return E* @author ronglexie* @version 2018/8/19*/public E findMax(){if(arr .getSize() == 0){throw new IllegalArgumentException("FindMax failed. heap is empty.");}return arr.get(0);}/*** 取出最大值** @param* @return E* @author ronglexie* @version 2018/8/20*/public E extractMax(){E result = findMax();arr.swap(0,arr.getSize() - 1);arr.removeLast();siftDown(0);return result;}/*** 下沉节点** @param k* @return void* @author ronglexie* @version 2018/8/25*/private void siftDown(int k) {while (k >= 0 && leftChild(k) < arr.getSize()){int j = leftChild(k);//找到k节点的左右子节点的最大值jif (j + 1 < arr.getSize() && arr.get(j + 1).compareTo(arr.get(j)) > 0) {j = rightChild(k);}// 运行到此，arr[j] 是 leftChild 和 rightChild 中的最大值//比较大小判断是否还需要下沉操作if(arr.get(k).compareTo(arr.get(j)) > 0){break;}arr.swap(k,j);k = j;}}}

一、非原地堆排序

HeapSort.java

import java.util.Arrays;
import java.util.Random;/*** Description: 堆排序.*/
public class HeapSort01 {final static int MAX=20; //待排序数组大小private HeapSort01(){}/*** 堆排序 * @param arr 待排序数组*/public static void heapSort(int arr[]){MaxHeap<Integer> maxHeap = new MaxHeap<>();for(int elem : arr){maxHeap.add(elem);}for(int i = arr.length - 1; i>=0; i--){arr[i] = maxHeap.extractMax();}}public static void main(String[] args) {Random random=new Random();int []arr=new int[MAX];//生成随机数测试for(int i=0;i<MAX;i++){arr[i]= random.nextInt(20);}System.out.print("待排序数组：" + Arrays.toString(arr));long start=System.currentTimeMillis();heapSort(arr);long end=System.currentTimeMillis();System.out.println("\nheapSorting time cost:"+(end-start)+"ms");for (int anArray : arr) {System.out.print(anArray + " ");}System.out.println();}
}

输出结果：

待排序数组：[12, 16, 5, 3, 0, 6, 8, 13, 7, 13, 9, 0, 1, 1, 15, 7, 4, 13, 15, 1]
heapSorting time cost:4ms
0 0 1 1 1 3 4 5 6 7 7 8 9 12 13 13 13 15 15 16

二、原地堆排序

import java.util.Arrays;
import java.util.Random;/*** Description: 堆排序. 原地排序*/
public class HeapSort02 {final static int MAX = 20; //待排序数组大小/*** 堆排序* @param arr 待排序数组*/public static void heapSort(int[] arr) {if (arr.length <= 1) {return;}int length = arr.length;// heapify：将任意数组整理成堆的形状int parent_index = (length - 2) / 2;    // 最后一个叶子节点的父节点for (int i = parent_index; i >= 0; i--) {siftDown(arr, i, arr.length);}System.out.print("\nheapify后的数组：" + Arrays.toString(arr));for (int i = arr.length - 1; i >= 0; i--) {swap(arr, 0, i);    // 将最大值交换到i位置siftDown(arr, 0, i);}System.out.print("\n整理后的数组：" + Arrays.toString(arr));}/*** 下沉节点：对arr[0,n) 所形成的最大堆中，索引 k 的元素，执行siftDown*/private static void siftDown(int[] arr, int k, int n) {while (leftChild(k) < n) {int j = leftChild(k);  //在此轮循环中，arr[k]与arr[j]交换位置//找到k节点的左右子节点的最大值jif (j + 1 < n && arr[j + 1] > arr[j]) {j = rightChild(k);}// 运行到此，arr[j] 是 leftChild 和 rightChild 中的最大值//比较大小判断是否还需要下沉操作if (arr[k] >= arr[j]) {break;}swap(arr, k, j);k = j;}}public static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public static int leftChild(int index) {return (index * 2) + 1;}public static int rightChild(int index) {return (index * 2) + 2;}public static void main(String[] args) {Random random = new Random();int[] arr = new int[MAX];//生成随机数测试for (int i = 0; i < MAX; i++) {arr[i] = random.nextInt(20);}System.out.print("待排序数组：" + Arrays.toString(arr));long start = System.currentTimeMillis();heapSort(arr);long end = System.currentTimeMillis();System.out.println("\nheapSorting time cost:" + (end - start) + "ms");for (int anArray : arr) {System.out.print(anArray + " ");}System.out.println();}
}

输出结果：

待排序数组：[15, 9, 10, 12, 7, 1, 12, 18, 12, 7, 0, 8, 17, 5, 15, 3, 2, 16, 8, 14]
heapify后的数组：[18, 16, 17, 15, 14, 10, 15, 12, 12, 7, 0, 8, 1, 5, 12, 3, 2, 9, 8, 7]
整理后的数组：[0, 1, 2, 3, 5, 7, 7, 8, 8, 9, 10, 12, 12, 12, 14, 15, 15, 16, 17, 18]
heapSorting time cost:0ms
0 1 2 3 5 7 7 8 8 9 10 12 12 12 14 15 15 16 17 18 Process finished with exit code 0

这篇关于算法-排序算法：堆排序（HeapSort ）【O(nlogn)】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1128847。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...
hdu 1285（拓扑排序）

hdu 1285（拓扑排序）

题意： 给各个队间的胜负关系，让排名次，名词相同按从小到大排。 解析： 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式，对一个有向无回路图进行拓扑排序后，所有的顶点形成一个序列，对所有边(u,v)，满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上，某些工程完成后，另一些工程才能继续，此时
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2