上文我们曾经说过选择排序是将整个数组从头到尾全部扫描一遍,然后选择最小的与第一位进行交换,接着再在剩下的元素中进行扫描,直到扫描完毕,最终,得到一个有序数列。我们通过观察可以发现,选择排序适合长度比较小的数组,如果一个数组太长,一般的选择排序明显不能满足。那么我们就需要一种排序来解决这种问题,那么堆排序就出现了。下面我们就先简单介绍一下堆排序:
堆排序:
堆排序是指利用堆积树(一种二叉树)这种数据结构所设计的一种排序算法,它是选择排序升级版。可以利用数组的特点快速定位指定索引的角标。堆分为大根堆和小根堆,是完全二叉树。
大顶堆:
大顶堆的要求是每个节点的值都不大于其父节点的值,即A[PARENT[i]] >= A[i]。在数组的非降序排序中,需要使用的就是大顶堆,因为根据大顶堆的要求可知,最大的值一定在堆顶。如图:
小顶堆:
与大顶堆恰好相反,小顶堆的要求是每个节点的值都不小于其父节点的值,即A[PARENT[i]] <= A[i]。在数组的降序排序中,需要使用的就是小顶堆,因为根据小顶堆的要求可知,最小的值一定在堆顶。如图:
对于二叉树说起来大家可能有点迷糊,那么我们就先简单了解一下二叉树吧!
二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。大概是这么个结构:
关于二叉树的介绍以及一些相关知识,可以去看看:【程序员怎能不会二叉树系列】,里面对于二叉树的类型,遍历方式,以及二叉树结构都有详细的文字说明。文尾会附上链接。
为了便于大家理解,下面我们先贴上我已经写好的大顶堆排序代码,根据代码进行讲解。
代码如下:
public static void main(String[] args) { int[] arr = { 1, 3, 4, 2, 6, 7, 8, 0, 5 }; int len = arr.length; long startTime = System.nanoTime(); // 获取排序开始时间 // 初始建堆 for (int i = (len - 2) / 2; i >= 0; i--) { maxHeapfy(arr, i, len); } //建堆完成 arr[len - 1] = arr[0] ^ arr[len - 1]; // 交换 arr[0] = arr[0] ^ arr[arr.length - 1]; arr[len - 1] = arr[0] ^ arr[len - 1]; for (int i = 1; i < len - 1; i++) { // 初始建堆之后还要排a.length-2次 maxHeapfy(arr, 0, len - i); arr[len - 1 - i] = arr[0] ^ arr[len - 1 - i]; // 交换 arr[0] = arr[0] ^ arr[len - 1 - i]; arr[len - 1 - i] = arr[0] ^ arr[len - 1 - i]; } long endTime = System.nanoTime(); // 获取排序结束时间 System.out.println("排序結果:" + Arrays.toString(arr)); System.out.println("程序运行时间: " + (endTime - startTime) + "ns"); } static void maxHeapfy(int[] a, int i, int heapSize) { // 数组a,第i个结点,heapSize是数组实际要排序的元素的长度 // 有的时候能够递归到叶子结点,叶子结点无后继,下面两个if都注意到了这一点 int left = 2 * i + 1; int right = 2 * i + 2; int largest = i; if (left < heapSize && a[left] > a[largest]) { // largest = left; } if (right < heapSize && a[right] > a[largest]) { largest = right; } if (largest != i) { // 把最大值给父节点 a[largest] = a[largest] ^ a[i]; a[i] = a[largest] ^ a[i]; a[largest] = a[largest] ^ a[i]; maxHeapfy(a, largest, heapSize); // 发生交换之后还要保证大根堆性质 } }
打印结果:
排序結果:[0, 1, 2, 3, 4, 5, 6, 7, 8] 程序运行时间:5400ns
首先,我们第一步是初始化一个堆,代码如下:
for (int i = (len - 2) / 2; i >= 0; i--) { maxHeapfy(arr, i, len); }
创建一个堆之后,将我们的数据进行大顶堆排序操作,maxHeapfy方法是整个排序的核心,代码如下:
static void maxHeapfy(int[] a, int i, int heapSize) { // 数组a,第i个结点,heapSize是数组实际要排序的元素的长度 // 有的时候能够递归到叶子结点,叶子结点无后继,下面两个if都注意到了这一点 int left = 2 * i + 1; int right = 2 * i + 2; int largest = i; if (left < heapSize && a[left] > a[largest]) { // largest = left; } if (right < heapSize && a[right] > a[largest]) { largest = right; } if (largest != i) { // 把最大值给父节点 a[largest] = a[largest] ^ a[i]; a[i] = a[largest] ^ a[i]; a[largest] = a[largest] ^ a[i]; maxHeapfy(a, largest, heapSize); // 发生交换之后还要保证大根堆性质 } }
我们对着上面的代码进行讲解一下:我们先把左子节点进行排序,再将右子节点进行排序,将最大值传递给父节点,递归操作一下,整个逻辑就完成了。
总结:
整个堆排序的主要原理就是比较交换,父子节点的相互比较,根据大小顶堆排序规则进行交换。可能有的同学理解起来比较困难,但是相信多看几遍,多敲几遍,还是能够理解的。想要理解代码,其实只有一个字,敲。敲多了自然会去思考。不然终究是纸上谈兵。