江苏龙网

  1. 首页 > 人文 > >

1T数据快速排序！十种经典排序算法总结( 二 )

< array.length; i++) {int temp = array[i];int j = i - gap;while (j >= 0j = j - gap;}array[j + gap] = temp;}gap >>>= 1;}return array;}5 堆排序堆排序的过程是首先构建一个大顶堆 ， 大顶堆首先是一棵完全二叉树 ， 其次它保证堆中某个节点的值总是不大于其父节点的值 。
因为大顶堆中的最大元素肯定是根节点 ， 所以每次取出根节点即为当前大顶堆中的最大元素 ， 取出后剩下的节点再重新构建大顶堆 ， 再取出根节点 ， 再重新构建…重复这个过程 ， 直到数据都被取出 ， 最后取出的结果即为排好序的结果 。
public class MaxHeap {/*** 排序数组*/private int[] nodeArray;/*** 数组的真实大小*/private int size;private int parent(int index) {return (index - 1) >>> 1;}private int leftChild(int index) {return (index << 1) + 1;}private int rightChild(int index) {return (index << 1) + 2;}private void swap(int i, int j) {nodeArray[i] = nodeArray[i] ^ nodeArray[j];nodeArray[j] = nodeArray[i] ^ nodeArray[j];nodeArray[i] = nodeArray[i] ^ nodeArray[j];}private void siftUp(int index) {//如果index处节点的值大于其父节点的值 ， 则交换两个节点值 ， 同时将index指向其父节点 ， 继续向上循环判断while (index > 0index = parent(index);}}private void siftDown(int index) {//左孩子的索引比size小 ， 意味着索引index处的节点有左孩子 ， 证明此时index节点不是叶子节点while (leftChild(index) < size) {//maxIndex记录的是index节点左右孩子中最大值的索引int maxIndex = leftChild(index);//右孩子的索引小于size意味着index节点含有右孩子if (rightChild(index) < size}//如果index节点值比左右孩子值都大 ， 则终止循环if (nodeArray[index] >= nodeArray[maxIndex]) {break;}//否则进行交换 ， 将index指向其交换的左孩子或右孩子 ， 继续向下循环 ， 直到叶子节点swap(index, maxIndex);index = maxIndex;}}private void add(int value) {nodeArray[size] = value;size++;//构建大顶堆siftUp(size - 1);}private void extractMax() {//将堆顶元素和最后一个元素进行交换swap(0, size - 1);//此时并没有删除元素 ， 而只是将size-1 ， 剩下的元素重新构建成大顶堆size--;//重新构建大顶堆siftDown(0);}public int[] heapSort(int[] array) {if (array == null || array.length < 2) {return array;}nodeArray = new int[array.length];for (int value : array) {add(value);}for (int i = 0; i < array.length; i++) {extractMax();}return nodeArray;}}上面的经典实现中 ， 如果需要变动节点时 ， 都会来一次父子节点的互相交换操作（包括删除节点时首先做的要删除节点和最后一个节点之间的交换操作也是如此） 。 如果仔细思考的话 ， 就会发现这其实是多余的 。 在需要交换节点的时候 ， 只需要siftUp操作时的父节点或siftDown时的孩子节点重新移到当前需要比较的节点位置上 ， 而比较节点是不需要移动到它们的位置上的 。 此时直接进入到下一次的判断中 ， 重复siftUp或siftDown过程 ， 直到最后找到了比较节点的插入位置后 ， 才会将其插入进去 。 这样做的好处是可以省去一半的节点赋值的操作 ， 提高了执行的效率 。 同时这也就意味着 ， 需要将要比较的节点作为参数保存起来 ， 而在ScheduledThreadPoolExecutor源码中也正是这么实现的（《较真儿学源码系列-ScheduledThreadPoolExecutor（逐行源码带你分析作者思路）》） 。
6 归并排序归并排序使用的是分治的思想 ， 首先将数组不断拆分 ， 直到最后拆分成两个元素的子数组 ， 将这两个元素进行排序合并 ， 再向上递归 。 不断重复这个拆分和合并的递归过程 ， 最后得到的就是排好序的结果 。


推荐阅读


上一篇：用了5年才知道，微信转账和红包差别不小，建议与转告家里亲友

下一篇：Win10新预览版20236推送：刷新率调节更方便、可保留搜索历史