【数据结构】-java实现堆排序算法（六）

【数据结构】-java实现堆排序算法（六）

堆排序的算法思想、动态演示、C++、python实现，推荐参考​​堆排序算法详解​​ 堆排序是一种选择排序。

算法思想：利用堆的性质来选择排序。

算法的性能分析

堆排序是一种不稳定的排序方法。

java实现堆排序算法

建的堆为大顶堆。小顶堆类似。 堆排序的算法，以及测试。

public class Dui { public static void main(String[] args) { int[] array = new int[] { 7, 6, 6, 10, 11, 12, 13, 17 }; sort(array);//调用排序方法 System.out.println(Arrays.toString(array));//数组输出 } //排序方法 public static void sort(int[] array) { //这个for循环就是建成第一个大顶堆的初始状态，从底向上建成大顶堆 for (int i = array.length / 2 - 1; i >= 0; i--) { adjustHeap(array, i, array.length); } for (int j = array.length - 1; j > 0; j--) { //交换顶点和最后一层且最右边的叶子结点。 swap(array, 0, j); //将剩下的重新排序成大顶堆。 adjustHeap(array, 0, j); } } //这个是堆排序的核心部分，一定要深度理解每一行的含义，可以手绘一下。 public static void adjustHeap(int[] array, int i, int length) { // 先把当前元素取出来 int temp = array[i]; int n=2 * i + 1;//先找到其左边的子结点 for (int k = n; k < length;k = 2 * k + 1 ) {//k=2 * k + 1意思是跳跃到和它交换的子结点 if (k + 1 < length && array[k] < array[k + 1]) { k++; } //经过if语句 ，k为子节点中最大的那个结点 // 如果发现子节点更大，则进行值的交换 if (array[k] > temp) { swap(array, i, k); //下面这一句是最核心的迭代式的代码。 //思考下：如果子节点更换了，那么，以子节点为根的子树会不会受到影响呢？ // 所以，循环对子节点所在的树继续进行判断 i = k;//此时i变成了k,为什么？理解它整个建堆就明白了 } else {// 如果不用交换，那么，就直接终止循环了 break; } } } //这个是数组中的a位置的值和b位置的值的交换 public static void swap(int[] arr, int a, int b) { int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } }

总结

堆排序用到了二叉树，所以首先要进行初始化成大顶堆，adjustHeap(array, i, array.length)这个方法的使用特别重要，此是初始化大顶堆，初始化的过程中是从下至上建堆。adjustHeap(int[] array, int i, int length) 方法，是一个将第i个元素，放到应有的位置。同理也是一个建堆的过程，但是它是跳跃式的。注意循环的过程，因为仅仅交换一次并不足以将该元素放入应有的位置。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。