堆排序

  |   0浏览

基本原理

堆排序的基本原理也是选择排序,只是不在使用遍历的方式查找无序区间的最大的数,而是通过堆来选择无序区间的最大的数。

大致过程:

1.建堆(这里是以建大顶堆为例)

先把数组中的数转换成二叉树的形式,在这个基础上建堆。这里用到的大顶堆的性质:所有父节点的值要大于其子节点的值。按照这个性质,将无序的二叉树调整成堆。堆排序父节点和子节点计算:堆排序如图是一个简易的二叉树,蓝色的数字为节点的序号。计算父节点的序号要根据已知的子节点的序号求得。假设当前孩子节点的序号为 i ,那么这个节点的父节点 = ( i - 1 ) / 2。不管当前节点是右孩子节点还是左孩子节点,这个都是成立的。计算子节点的序号则是根据父节点的序号求得。假设父节点的序号为 i ,左孩子节点的序号 = ( 2 i ) + 1,右孩子节点的序号 = ( 2 i ) + 2。建堆的代码实现:

 public static void buildHeap(int[] tree) {        //n 表示数组的个数,即原始数组的长度        int last_node = tree.length - 1;//这个是最后一个节点的序号        int parent = (last_node - 1) / 2;//计算最后一个父节点是为了从最后一个小堆开始调整        for (int i = parent; i >= 0; i--) {//从下往上依次调整            adjust(tree, tree.length, i);        }    }    public static void adjust(int[] tree, int n, int i) {        //n 表示数组的个数,即原始数组的长度;i 表示节点的序号        if(i >= n) {//如果越界了,就退出递归循环            return;        }        int left = 2 * i + 1;//左孩子结点        int right = 2 * i + 2;//右孩子结点        int max = i;//先令最大值为父节点的值,后面再比较父节点和两个孩子结点的值,找出最大值        if(left < n && tree[left] > tree[max]) {            max = left;        }        if(right < n && tree[right] > tree[max]) {            max = right;        }        if(max != i) {//当最大值不是父节点的时候,就将最大值和父节点交换            swap(tree, max, i);            adjust(tree, n, max);//用递归进行调整        }    }

2.运用堆进行排序

堆排序建大顶堆就是将数字按升序排列。建好大顶堆后,此时大顶堆堆顶的值就是最大值,将堆顶元素与最后一个节点交换,最后的这个节点就是排序好的值,节点前面的值再进行建大顶堆,这里再建堆就不再包含已经排序好的节点了,依次类推,直到排序完成。堆排序的代码实现:

    public static void heapSort(int[] tree, int n) {        //n 表示数组的个数,即原始数组的长度        buildHeap(tree);        for (int i = n - 1; i > 0; i--) {            swap(tree, 0, i);//将最大值交换到当前数组的最后面,交换之后[0,i)区间是无序的,[i,n)是有序的            adjust(tree, i, 0);//再调整[0,i)区间,直到排序完成        }    }

完整代码:

    public static void heapSort(int[] tree, int n) {        //n 表示数组的个数,即原始数组的长度        buildHeap(tree);        for (int i = n - 1; i > 0; i--) {            swap(tree, 0, i);//将最大值交换到当前数组的最后面,交换之后[0,i)区间是无序的,[i,n)是有序的            adjust(tree, i, 0);//再调整[0,i)区间,直到排序完成        }    }    public static void buildHeap(int[] tree) {        //n 表示数组的个数,即原始数组的长度        int last_node = tree.length - 1;//这个是最后一个节点的序号        int parent = (last_node - 1) / 2;//计算最后一个父节点是为了从最后一个小堆开始调整        for (int i = parent; i >= 0; i--) {//从下往上依次调整            adjust(tree, tree.length, i);        }    }    public static void adjust(int[] tree, int n, int i) {        //n 表示数组的个数,即原始数组的长度;i 表示节点的序号        if(i >= n) {//如果越界了,就退出递归循环            return;        }        int left = 2 * i + 1;//左孩子结点        int right = 2 * i + 2;//右孩子结点        int max = i;//先令最大值为父节点的值,后面再比较父节点和两个孩子结点的值,找出最大值        if(left < n && tree[left] > tree[max]) {            max = left;        }        if(right < n && tree[right] > tree[max]) {            max = right;        }        if(max != i) {//当最大值不是父节点的时候,就将最大值和父节点交换            swap(tree, max, i);            adjust(tree, n, max);//用递归进行调整        }    }    public static void swap(int[] tree, int x, int y) {        int tmp = tree[x];        tree[x] = tree[y];        tree[y] = tmp;    }

原文地址:https://blog.51cto.com/14298563/2507790