网站开发从入门到实战,wordpress改底部信息,wordpress博客 免费下载,网站轮播动态图如何做堆排序#xff08;借助 API#xff09;
算法思想
利用堆能够维护数组中最大值的性质#xff0c;根据数组元素建立最大堆#xff0c;依次弹出元素并维护堆结构#xff0c;直到堆为空。
稳定性分析
堆排序是不稳定的#xff0c;因为堆本质上是完全二叉树#xff0c;排…堆排序借助 API
算法思想
利用堆能够维护数组中最大值的性质根据数组元素建立最大堆依次弹出元素并维护堆结构直到堆为空。
稳定性分析
堆排序是不稳定的因为堆本质上是完全二叉树排序的过程涉及二叉树的父子节点交换没有办法保证办法保证相等的值一定在同一棵子树上被处理。
具体实现
// Java 本身实现了优先队列的 API其本质类似于堆可以用来实现堆排序
private void heapSort(int[] arr) {QueueInteger queue new PriorityQueue();for(int item : arr) {queue.offer(item);}for(int i 0; i arr.length; i) {arr[i] queue.poll();}
}堆操作
上面的堆排序实现有一种脑干缺失的美图一乐就行。堆相关的内容中堆的原理和操作显然更重要。
自顶向底建堆
自顶向底建堆时间复杂度是 O ( N l o g N ) O(NlogN) O(NlogN) 这个量级的。自下而上的调整操作实现起来比较简单原因是对于每个子节点而言父节点是唯一的。
// 交换数组中的两个元素
private void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;
}// 由下而上调整元素
private void upAdjust(int[] arr, int cur) {while (arr[cur] arr[(cur - 1) / 2]) {// 当前元素大于父节点那么进行交换并移动工作指针swap(arr, cur, (cur - 1) / 2);cur (cur - 1) / 2;}
}// 自顶向底建堆
private void buildHeap(int[] arr) {for (int i 0; i arr.length; i) {upAdjust(arr, i);}
}自底向顶建堆
自底向顶建堆它的时间复杂度是 O ( N ) O(N) O(N) 这个量级的。实现相对来说要更麻烦原因是父节点可能有两个子节点涉及到与谁交换的判断。
// 交换数组中的两个元素
private void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;
}// 由上而下调整元素
private void downAdjust(int[] arr, int cur, int size) {// 数组下标从零开始当前节点的左孩子下标为 2 * cur 1int child 2 * cur 1;while (child size) {// 如果当前节点有右孩子那么比较两个子节点的值确定潜在的交换对象int target child 1 size arr[child 1] arr[child] ? child 1 : child;// 再与当前节点比较大小target arr[target] arr[cur] ? target : cur;// 一旦发现此次操作中无需交换立即停止流程if (target cur) {break;}// 交换父子节点swap(arr, target, cur);// 移动工作指针cur target;child 2 * cur 1;}
}// 自底向顶建堆
private void buildHeap(int[] arr) {int n arr.length;for (int i n - 1; i 0; i--) {downAdjust(arr, i, n);}
}堆排序自己实现
自顶向底建堆并实现排序
// 交换数组中的两个元素
private void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;
}// 由下而上调整元素
private void upAdjust(int[] arr, int cur) {while (arr[cur] arr[(cur - 1) / 2]) {// 当前元素大于父节点那么进行交换并移动工作指针swap(arr, cur, (cur - 1) / 2);cur (cur - 1) / 2;}
}// 自顶向底建堆
private void buildHeap(int[] arr) {for (int i 0; i arr.length; i) {upAdjust(arr, i);}
}// 由上而下调整元素
private void downAdjust(int[] arr, int cur, int size) {// 数组下标从零开始当前节点的左孩子下标为 2 * cur 1int child 2 * cur 1;while (child size) {// 如果当前节点有右孩子那么比较两个子节点的值确定潜在的交换对象int target child 1 size arr[child 1] arr[child] ? child 1 : child;// 再与当前节点比较大小target arr[target] arr[cur] ? target : cur;// 一旦发现此次操作中无需交换立即停止流程if (target cur) {break;}// 交换父子节点swap(arr, target, cur);// 移动工作指针cur target;child 2 * cur 1;}
}// 堆排序
private void heapSort(int[] arr) {buildHeap(arr);int size arr.length;// 不断地交换堆顶元素与堆中的最后一个元素并向下调整维护堆while (size 0) {swap(arr, 0, --size);downAdjust(arr, 0, size);}
}自底向顶建堆并实现排序
// 交换数组中的两个元素
private void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;
}// 由上而下调整元素
private void downAdjust(int[] arr, int cur, int size) {// 数组下标从零开始当前节点的左孩子下标为 2 * cur 1int child 2 * cur 1;while (child size) {// 如果当前节点有右孩子那么比较两个子节点的值确定潜在的交换对象int target child 1 size arr[child 1] arr[child] ? child 1 : child;// 再与当前节点比较大小target arr[target] arr[cur] ? target : cur;// 一旦发现此次操作中无需交换立即停止流程if (target cur) {break;}// 交换父子节点swap(arr, target, cur);// 移动工作指针cur target;child 2 * cur 1;}
}// 自底向顶建堆
private void buildHeap(int[] arr) {int n arr.length;for (int i n - 1; i 0; i--) {downAdjust(arr, i, n);}
}// 堆排序
private void heapSort(int[] arr) {buildHeap(arr);int size arr.length;// 不断地交换堆顶元素与堆中的最后一个元素并向下调整维护堆while (size 0) {swap(arr, 0, --size);downAdjust(arr, 0, size);}
}梳理总结
堆排序主要有两大步骤包括建堆和出堆排序其中建堆的操作根据方向的不同有效率上的差异但是因为出堆排序需要 O ( N l o g N ) O(NlogN) O(NlogN) 量级的时间所以总的时间复杂度为 O ( N l o g N ) O(NlogN) O(NlogN)。 在实现的选择上虽然自顶向底建堆本身相对比较容易实现但是由于出堆排序的过程中一定会涉及到由上而下的调整反而需要记忆更多的内容。因此可以考虑只记住自底向顶建堆的实现方法。 事实上鉴于堆排序不具有稳定性性能上也只是中规中矩所以通常只有在考试遇到、要求实现不使用额外空间的情况下随机快排需要额外的递归栈空间大约是 O ( l o g N ) O(logN) O(logN) 的水平归并需要额外的辅助数组是 O ( N ) O(N) O(N) 的水平会手写实现堆排序。 而在实际应用的过程中空间换时间是常见操作所以不需要额外空间的堆并没有什么优势。
堆本身可以维护数组中最大最小值的性质是非常美妙的一般来说直接调用语言本身提供的 API 即可例如 C 的 STL 和 Java 中都提供了优先队列。
后记
使用 Leetcode 912. 排序数组 进行测试堆排序能够比较高效地完成任务大致与随机快速排序相当。
相关阅读
常见排序算法总结 (一) - 三种基本排序常见排序算法总结 (二) - 不基于比较的排序常见排序算法总结 (三) - 归并排序与归并分治常见排序算法总结 (四) - 快速排序与随机选择
