国外设计网站怎么进入,东营网站建设收益高,专业北京seo公司,手机优化怎么解除引言
此文基于《经典数据结构——堆的实现》中堆结构#xff0c;实现一个以堆处理排序的算法。
一、算法思想
基于堆结构的堆排序的算法思想非常简单#xff0c;循环获取大根堆中的最大值#xff08;0位置的根节点#xff09;放到堆的末尾#xff0c;直到将堆拿空。
由…引言
此文基于《经典数据结构——堆的实现》中堆结构实现一个以堆处理排序的算法。
一、算法思想
基于堆结构的堆排序的算法思想非常简单循环获取大根堆中的最大值0位置的根节点放到堆的末尾直到将堆拿空。
由于一个现成的大根堆可以实现 O(1) 时间复杂度的最大值返回因此堆排序的主要时间消耗就是在 heapInsert 或 heapify 这类维护大根堆结构的过程上。 二、代码演示
首先将数组从0开始模拟逐个放入的过程循环 heapInsert 建堆。
然后以整个数组为堆模拟循环取出 0 位置最大值的操作循环 heapify。 小提示取出的最大值你可以放在原数组中即堆尾位置由于拿出元素会导致堆缩小数组末尾会有空余位置也可以新创建一个同长数组放入这对于排序本身并无影响只不过是会增加额外的空间复杂度。 public static void heapSort(int[] arr) {if (arr null || arr.length 2)return;// 整体变为大根堆for (int i 0; i arr.length; i) {heapInsert(arr, i);}// 以整个数组作为堆大小假设此堆已满int heapSize arr.length;swap(arr, 0, --heapSize);while (heapSize 0) {swap(arr, 0, --heapSize);heapify(arr, 0, heapSize);}}
模拟入堆的 heapInsert 、和模拟出堆的 heapify // heapInsertprivate static void heapInsert(int[] arr, int index) {int father (index - 1) / 2;while (arr[index] arr[father]) {swap(arr, index, father);index father;father (index - 1) / 2;}}// heapifyprivate static void heapify(int[] arr, int index, int heapSize) {int leftIdx index * 2 1;while (leftIdx heapSize) {int largest leftIdx 1 heapSize arr[leftIdx] arr[leftIdx 1] ? leftIdx 1 : leftIdx;largest arr[index] arr[largest] ? largest : index;if (index largest)break;else {swap(arr, index, largest);index largest;leftIdx index * 2 1;}}}// 交换数组元素private static void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}
完整代码及对数器
public class HeapSort {public static void heapSort(int[] arr) {if (arr null || arr.length 2)return;// 整体变为大根堆for (int i 0; i arr.length; i) {heapInsert(arr, i);}// 以整个数组作为堆大小假设此堆已满int heapSize arr.length;swap(arr, 0, --heapSize);while (heapSize 0) {swap(arr, 0, --heapSize);heapify(arr, 0, heapSize);}}private static void heapInsert(int[] arr, int index) {int father (index - 1) / 2;while (arr[index] arr[father]) {swap(arr, index, father);index father;father (index - 1) / 2;}}/*** 结合了两个方向的入堆方式** param arr* param index* param heapSize*/private static void heapifyNew(int[] arr, int index, int heapSize) {if (index 0) {// 向下int left index * 2 1;while (left heapSize) {int largest left 1 heapSize arr[left] arr[left 1] ? left 1 : left;largest arr[index] arr[largest] ? largest : index;if (largest index) break;else {swap(arr, index, largest);index largest;left index * 2 1;}}} else if (index heapSize - 1) {// 向上int father (index - 1) / 2;while (arr[index] arr[father]) {swap(arr, index, father);index father;father (index - 1) / 2;}}}private static void heapify(int[] arr, int index, int heapSize) {int leftIdx index * 2 1;while (leftIdx heapSize) {int largest leftIdx 1 heapSize arr[leftIdx] arr[leftIdx 1] ? leftIdx 1 : leftIdx;largest arr[index] arr[largest] ? largest : index;if (index largest)break;else {swap(arr, index, largest);index largest;leftIdx index * 2 1;}}}private static void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}// for testpublic static void comparator(int[] arr) {Arrays.sort(arr);}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr new int[(int) ((maxSize 1) * Math.random())];for (int i 0; i arr.length; i) {arr[i] (int) ((maxValue 1) * Math.random()) - (int) (maxValue * Math.random());}return arr;}// for testpublic static int[] copyArray(int[] arr) {if (arr null) {return null;}int[] res new int[arr.length];for (int i 0; i arr.length; i) {res[i] arr[i];}return res;}// for testpublic static boolean isEqual(int[] arr1, int[] arr2) {if ((arr1 null arr2 ! null) || (arr1 ! null arr2 null)) {return false;}if (arr1 null arr2 null) {return true;}if (arr1.length ! arr2.length) {return false;}for (int i 0; i arr1.length; i) {if (arr1[i] ! arr2[i]) {return false;}}return true;}// for testpublic static void printArray(int[] arr) {if (arr null) {return;}for (int i 0; i arr.length; i) {System.out.print(arr[i] );}System.out.println();}// for testpublic static void main(String[] args) {int testTime 500000;int maxSize 100;int maxValue 100;boolean succeed true;for (int i 0; i testTime; i) {int[] arr1 generateRandomArray(maxSize, maxValue);int[] arr2 copyArray(arr1);heapSort(arr1);comparator(arr2);if (!isEqual(arr1, arr2)) {succeed false;break;}}System.out.println(succeed ? Nice! : Fucking fucked!);int[] arr generateRandomArray(maxSize, maxValue);printArray(arr);heapSort(arr);printArray(arr);}
}
三、时间复杂度
结论堆排序的时间复杂度是O(N * logN)。
简单说明一下各个步骤的大体时间复杂度详细推导不做讨论。
堆排序突破不了这个复杂度为什么这是因为第二步取值调整无法改变O(N* logN)同时基于比较的排序方法也没有比 O(N * logN) 更好的排序了。
首先heapInsert 的时间复杂度是 O(logN) 这个不难理解因为是二叉树每次向上比较和交换的次数只与堆的层高有关而层高又约等于 logN 因此调整一次的复杂度就是 O(logN)。
而建堆的过程是循环 heapInsert因此建堆的时间复杂度就是 O(N * logN)。
同样heapipfy 的时间复杂度也是 O(logN)每次下沉也只与层高有关。而循环下沉同样也是 O(N * logN)。
因此除去一些常数时间复杂度和倍数项最终可知堆排序的时间复杂度是 O(N * logN)。
扩展--建堆的两种方式
上面的代码以模拟入堆的方式建堆循环 heapInsert 时间复杂度是 O(N * logN)。
但是如果使用反向建堆 从数组最后一个元素开始循环 heapify那么时间复杂度会降 O(N)。
// O(N)
for (int i arr.length - 1; i 0; i--) {heapify(arr, i, arr.length);
}
首先不考虑复杂度但看这种建堆方式就要比 heapInsert 更优因为 heapify 是指定 i 位置向下沉由于最后一层元素更多而这些元素不需要向下沉因此可以减少很多不必要的操作。那么每一层从下往上越来越少向下沉的元素也会越来越少。
再来看时间复杂度。
我们从最后一个元素开始执行 heapify由于heapify是向下比较向下沉因此叶子节点只看一眼自身就直接返回了而堆的叶子节点数量大概是 N/2 数量级因此时间消耗公式可以是
T(N) (N / 2) * 1 (N/4) * 2 (N/8) * 3 (N/16) * 4 ...
这个算式如何求解可以使用数学上常用的 扩倍相减
2 * T(N) N (N / 2) * 2 (N / 4) * 3 (N / 8) * 4 ...
最后两式错位相减得到 T(N) N N/2 N/4 N/8 N/16.... 等比数列求和当 N 无限大时收敛于 O(N)。
