堆排序实现代码
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了堆排序实现代码,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2925字,纯文字阅读大概需要5分钟。
内容图文
堆排序迭代实现代码:
import java.util.Arrays; public class mainFunction { public static void main(String[] args) { //将数组进行升序排列 int arr[] = {4,6,8,5,9}; heapSort(arr); } //编写一个堆排序方法 public static void heapSort(int arr[]){ int temp = 0; System.out.println("堆排序"); //分步完成 /* 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);//真实的调整是从顶上开始调整(0) } 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 = i * 2 + 1; k < length; k = 2 * k + 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值放到调整后的位置 } }
堆排序递归实现
public class HeapSort { public static void heapSort(int[] arr) { if (arr == null || arr.length == 0) { return; } int len = arr.length; // 构建大顶堆,这里其实就是把待排序序列,变成一个大顶堆结构的数组 buildMaxHeap(arr, len); // 交换堆顶和当前末尾的节点,重置大顶堆 for (int i = len - 1; i > 0; i--) { swap(arr, 0, i); len--; heapify(arr, 0, len); } } private static void buildMaxHeap(int[] arr, int len) { // 从最后一个非叶节点开始向前遍历,调整节点性质,使之成为大顶堆 for (int i = (int)Math.floor(len / 2) - 1; i >= 0; i--) { heapify(arr, i, len); } } private static void heapify(int[] arr, int i, int len) { // 先根据堆性质,找出它左右节点的索引 int left = 2 * i + 1; int right = 2 * i + 2; // 默认当前节点(父节点)是最大值。 int largestIndex = i; if (left < len && arr[left] > arr[largestIndex]) { // 如果有左节点,并且左节点的值更大,更新最大值的索引 largestIndex = left; } if (right < len && arr[right] > arr[largestIndex]) { // 如果有右节点,并且右节点的值更大,更新最大值的索引 largestIndex = right; } if (largestIndex != i) { // 如果最大值不是当前非叶子节点的值,那么就把当前节点和最大值的子节点值互换 swap(arr, i, largestIndex); // 因为互换之后,子节点的值变了,如果该子节点也有自己的子节点,仍需要再次调整。 heapify(arr, largestIndex, len); } } private static void swap (int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }
内容总结
以上是互联网集市为您收集整理的堆排序实现代码全部内容,希望文章能够帮你解决堆排序实现代码所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。