龙岩市住房与城乡建设部网站,制作一个网页需要哪几个步骤,discuz论坛应用中心,奢侈品+网站建设方案堆排序 详解 堆排序代码实现 排序#xff1a; 排序#xff0c;就是使一串记录#xff0c;按照其中的某个或某些关键字的大小#xff0c;递增或递减的排列起来的操作。
稳定性#xff1a; 假定在待排序的记录序列中#xff0c;存在多个具有相同的关键字的记录#xff0c… 堆排序 详解 堆排序代码实现 排序 排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。
稳定性 假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中 r[i] r[j] 且 r[i] 在 r[j] 之前而在排序后的序列中 r[i] 仍在 r[j] 之前则称这种排序算法是稳定的否则称为不稳定的。 注意稳定排序可以实现为不稳定的形式 而不稳定的排序实现不了稳定的形式 内部排序 数据元素全部放在内存中的排序。
外部排序 数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。
堆排序
堆排序 (Heapsort) 是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。
为什么排升序建大堆?
因为假如排升序建小堆的话, 那么 我们只能得到最小的数字这一个, 同时堆的结构已经被破坏了, 因为我们直到最小值之后肯定要把这个最小值拿出来, 让剩下的元素进行排序, 也就是说堆的根节点下标要从 1 开始了, 这样就需要重新建堆了, 而建堆的时间复杂度是 O(N), 这样每选出来一个数, 就建一次堆, 总的时间复杂度就是 O(N*N) 了, 完全没有用上堆的优势。但是假如排升序建大堆的话 每次我们能选出来最大的值 然后把它与最后位置的元素进行交换 那么堆的根节点的位置还是从 0 开始唯一可能不满足堆的性质情况就是 根节点小于 其他节点 此时只需要 将根节点进行向下调整算法即可不用重新建堆 。
友情链接堆的讲解
基本思想: 建堆和排序。
建堆Heapify
首先将待排序的数组视为一个完全二叉树。从数组的最后一个非叶子节点开始逐个向前处理对每个节点执行向下调整算法将较大的元素交换到子节点的位置直至整个数组构建成一个最大堆Max Heap或最小堆Min Heap。最大堆的特点是每个节点的值都大于或等于其子节点的值最小堆则相反每个节点的值都小于或等于其子节点的值。
排序
一旦构建好堆堆顶元素就是最大最小元素。将堆顶元素与堆的最后一个元素交换位置然后将堆的大小减 1。对新的堆顶元素执行一次下沉操作将新的最大最小元素浮到堆顶。重复上述步骤直到堆的大小为 1排序完成。
堆排序的关键在于如何维护堆的性质即使交换元素后仍然保持堆的性质。这是通过向下调整操作来实现的确保每次交换后最大最小元素移到堆的顶部。 代码实现 public static void heapSort(int[] arr) {int len arr.length;// 排升序// 建大堆// 从最后一个非叶子节点进行向下调整for (int i (len-1-1)/2; i 0; i--) {shiftDown(arr, i, len);}// 排序// 从最后一个节点开始与第一个节点交换位置for (int i len-1; i 0; i--) {// 最大值放到最后面swap(arr, 0, i);// 交换完成后重新调整堆, 注意 此时堆的大小要 - 1, 但是 这正好与 i 相同, 所以直接使用了 ishiftDown(arr, 0, i);}}/*** 向下调整算法*/public static void shiftDown(int[] arr, int index, int len) {int parent index;int child parent * 2 1;// 一直向下调整至符合堆 或者 至最后一个节点while (child len) {if (child1 len arr[child1] arr[child]) {child;}if (arr[child] arr[parent]) {// 交换节点swap(arr, parent, child);// 继续向下调整parent child;child parent * 2 1;} else {// 调整完成break;}}}总结
时间复杂度 ON*logN空间复杂度 O1是不稳定排序: 向下调整过程中, 可能相对顺序发生变化对数据不敏感: 不管原本数据怎么分布, 都要先建堆, 然后排序相对于快速排序和归并排序堆排序通常效率较低因为它的数据访问模式不够连续可能导致缓存不命中
以上就是对堆排序的讲解 希望能帮到你 评论区欢迎指正
