十大经典排序算法-堆排序,计数排序,桶排序,基数排序
前言
这是十大经典排序算法详解的最后一篇了.
还没有看多之前两篇文章的小伙伴可以先去看看之前的两篇文章:
十大经典排序算法详解(一)冒泡排序,选择排序,插入排序
十大经典排序算法详解(二)希尔排序,归并排序,快速排序
这一篇文章真的耗费了我巨大的时间和精力,由于 堆排序是基于二叉树 的,所以写的篇幅比较大并且由于是关于树的,所以画图动态演示的工程量就进一步增加,其次就是因为计数排序,桶排序以及基数排序并不是基于比较的,所以算法的思想讲解相对于之前的基于比较的算法而言会稍微难一点.
其次就是这次的调试过程也比之前多了很多需要注意的地方,这些我都会在下面的代码中通过注释的方式提醒大家.
最后如果大家觉得我的文章写得还可以或者觉得文章对你有帮助的话,可以选择关注我的公众号:萌萌哒的瓤瓤,或者你也可以帮忙给文章来个一键三连吧.你的支持对我真的很有用.
1-堆排序
算法思想:
在介绍算法之前我们首先需要了解一下下面这些概念:什么是二叉树,什么是完全二叉树,什么是大根堆,什么是小根堆.
二叉树
学过数据结构的小伙伴肯定知道什么是二叉树,这部分主要是为那些可能还不太了解数据结构的小伙伴们说的.
二叉树的定义就是每个结点至多能有两个子树,二叉树是一种最简单的树,下面我们举几个树的例子:
我们可以来哦稍微区分一下,很明显只有4号树并不是我们所说的二叉树,因为它的1号结点下有三棵子树,所以4号树并不是我们所说的二叉树.到这里,相信大家也已经基本了解二叉树得出概念了,那么接下来我们再来了解一下另一个概念完全二叉树.
完全二叉树
说到完全二叉树,就应该知道它首先应该满足二叉树的一些条件,就比如说每个节点至多只能有两个子树,那么除了这个条件以外,还需要什么条件才能称得上是完全二叉树呢.
官方是这样说的: 一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
但是很明显说的太官方了,我们肯定需要简化一下概念.其实说白了就是在二叉树的基础上,所有的节点顺序必须要按照下面这样的顺序进行排列,否则就不能说是完全二叉树
并且每次必须是已经放满2的幂数之后才能放到下一层,并且必须是从每层最左边的节点开始添加节点,并且必须是先添加左节点在添加右节点.否则就不能称为是完全二叉树,这里呢,我们举几个反例,大家就知道我说的是什么意思了:
上面的这两棵树就是最明显的反例,看完这两棵树之后,相信大家就能更加了解什么是完全二叉树了.
大根堆
大根堆其实很容易理解,大根堆在完全二叉树的基础上就一条判定条件就是:每个根节点的值必须大于它的左孩子节点已经右孩子节点的值.满足这样条件的二叉树,我们就称这个二叉树是大根堆.当然了只要有一个节点不满足这样的情况,那么就不能称这是大根堆.
举个例子,下面这棵二叉树就是一个大根堆:
举完正确的例子之后,我们当然也需要来举几个反例来帮助我们更好的理解什么是大根堆:
看完这两个反例之后相信大家就能更加理解什么是大根堆了.
小根堆
当然了,理解完什么是大根堆了之后,大家就能举一反三的了解什么叫做小根堆了.这里就不再给大家废话.
在了解完上面的这些概念之后,我们就可以来讲解什么是堆排序了.
堆排序的算法步骤其实很简单,总共就三步.
1.将数组重构成大根堆
2.将数组的队头元素与队尾元素交换位置
3.对去除了队尾元素的数组进行重构,再次重构成大根堆
之后重复上述2,3步骤,直到需要重构成大根堆的数组为空为止.
算法的步骤的确简洁明了,其实大家看了也应该已经懂了.
因为每次重构成大根堆之后,根据大根堆的特性,每个节点的值一定大于左右孩子节点的值,所以很明显大根堆的根节点就是二叉树中值最大的值同时也就是数组中最大的值.所以重构成大根堆之后交换数组队头与队尾元素的操作就是在将最大的元素进行定位.也就意味着这一轮结束之后,数组中已经确定了一个元素的最终位置了.
算法的思想就是这样,谁都能说的出来,但是呢,堆排序的难点就是在于我们如何将数组重构成我们大根堆.这个就是堆排序的难点.
那么接下来,我们就着重讲解一下重构大根堆的过程是怎么样的.
首先我们需要明白一点就是我们一开始构建二叉树的时候遵循的是这样的原则: 从上往下,从左往右 .但是到了将二叉树重构成大根堆的时候我们的原则就必须要反过来了:从下往上,从右往左.这个大家动动小脑瓜应该就能理解了.
显然我们每次对小子树进行重构成大根堆的操作时,最后都会使得最大的元素上移,对不对,既然大的元素是在上移的,那么很显然我们就应该从下往上开始构建.
既然我们已经知道重构的顺序是什么样的之后,我们就需要再明白一点,那就是我们应该对哪些元素进行重构的操作呢?上面我们已经说过了,大根堆的一个硬性条件就是每个节点必需要大于它的左右孩子节点,那么很显然如果节点本身没有孩子节点的话,就不需要进行重构了.所以我们需要进行重构的元素必定包含孩子节点.并且结合我们上面所说重构顺序基本就可以得出一个结论:重构的元素就是最后一个非叶子节点之前的所有节点,包括该节点本身.,就比方下面这张图中红色圈圈的元素.
之后我们只需要通过循环,依次进行下面的操作:
比较节点及其左右孩子节点,如果有孩子节点的值大于该节点,那么就交换两者的位置.
这里需要大家特别注意!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
这里需要大家特别注意!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
这里需要大家特别注意!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
交换两者的位置之后我们还需要进行一个步骤 重新校验
特别注意!!!特别注意!!!重复这个过程,直到最后一个元素为止.
到这里堆排序的基本思想也就已经基本讲解完毕了,接下来就是通过图来动态的演示一下堆排序的过程,这样能够让大家更好的理解堆排序:
这是第一轮堆排序:
第二次堆排序:
第三次堆排序:
这里给大家模拟三次,大家应该就差不多懂这个流程了.主要是这图图画起来实在是太麻烦了.能力有限就只画这三次的了.在下面的代码里面,我还会着重讲重新校验的过程,大家如果这里还没理解的,也可以接着往下面看.
算法的基本思想大家应该基本上就能理解了.那么我们再来稍微聊聊堆排序的一些特点:
堆排序是不稳定的,这个其实还是比较好理解的.因为我们在进行小分支的调整时时有序的,但是之后可能会出现小分支扩大到大分支进行重新的调整,那么这时候就有可能会出现元素的相对位置混乱的情况.
这个混乱的过程其实有点像我们之前所说的希尔排序,希尔排序也是小区间内的插入排序是有序的,但是一旦扩散到更大的区间进行二次的插入排序时就有可能造成相对位置混乱的情况.
说的差不多了,那么我们接下来还是举一个例子来帮助大家更好的理解:
通过上面这张图,相信大家就能更好的理解堆排序为啥是不稳定的了.
堆排序每轮排序都可以确定一个元素的最终位置,这个大家看我上面的演示图也能看出来.
算法图解:
示例代码:
这是我写的第一版的代码:
//交换数组中的元素 public static void swap(int[]num ,int i,int j) { int temp=num[i]; num[i]=num[j]; num[j]=temp; } //将待排序的数组构建成大根堆 public static void buildbigheap(int []num,int end) { //从最后一个非叶子节点开始构建,依照从下往上,从右往左的顺序 for(int i=end/2;i>=0;i--) { int left=2*i+1; int right=2*i+2; int big=i; //判断小分支那个是大元素 if(left<end&&num[i]<num[left]) // swap(num, i, left); i=left; if(right<end&&num[i]<num[right]) // swap(num, i, right); i=right; swap(num, i, big); } } public static void main(String[] args) { int []num ={7,4,9,3,2,1,8,6,5,10}; long startTime=System.currentTimeMillis(); //第一次构建大根堆 buildbigheap(num, num.length); for(int j=num.length-1;j>0;j--) { //交换队头已经排序得到的最大元素与队尾元素 swap(num, 0, j); System.out.print("第"+(num.length-j)+"次排序: "); for(int k=0;k<num.length;k++) { System.out.print(num[k]+" "); } System.out.println(); //交换结束之后,大根堆已经内破坏,需要开始重新构建大根堆 buildbigheap(num,j); } long endTime=System.currentTimeMillis(); System.out.println("程序运行时间： "+(endTime-startTime)+"ms"); }
一开始我觉得我的代码是对的,并且运行出来的结果也和我预期的一样,但是当我自己画图以后画到这张图的时候我就知道算法还是有BUG的,这个BUG就是每次构建大根堆的时候:我们的确能够在每次构建大根堆的时候将最大的元素挑选出来,但是,我们在挑选出当前最大的元素之后,我们的大根堆真的还是大根堆吗,这里用上面画的图,我们就能看出来了:
很明显这个这一步我们的确已经将最大的元素挑选出来了,但是我们当前的已经不是大根堆了,所以我就在想我到底是哪一步做错了呢.之后我参考了网上的资料发现,该算法还有一个重点就是:如果我们发现根节点与孩子节点交换顺序之后,我们就需要重新检查交换之后的孩子节点以下的所有节点是否还满足大根堆的定义,因为可能我们交换后的孩子节点的值还是比他的孩子节点要小的.就比方上面那张图里我们所看到的.所以修改后的代码主要就是加上了重新校验的过程.
修改后的第二版代码:
//交换数组中的元素 public static void swap(int[]num ,int i,int j) { int temp=num[i]; num[i]=num[j]; num[j]=temp; } //将待排序的数组构建成大根堆 public static void buildbigheap(int []num,int end) { //从最后一个非叶子节点开始构建,依照从下往上,从右往左的顺序 for(int i=end/2;i>=0;i--) { adjustnode(i, end, num); } } //调整该节点及其以下的所有节点 public static void adjustnode(int i,int end,int []num) { int left=2*i+1; int right=2*i+2; int big=i; //判断小分支那个是大元素 if(left<end&&num[i]<num[left]) i=left; if(right<end&&num[i]<num[right]) i=right; if(i!=big) { //交换顺序之后需要继续校验 swap(num, i, big); //重新校验,防止出现交换之后根节点小于孩子节点的情况 adjustnode(i, end, num); } } public static void main(String[] args) { int []num ={5,3,7,1,4,6,2}; long startTime=System.currentTimeMillis(); //第一次构建大根堆 buildbigheap(num, num.length); for(int j=num.length-1;j>0;j--) { System.out.print("第"+(num.length-j)+"次排序前: "); for(int k=0;k<num.length;k++) { System.out.print(num[k]+" "); } //交换队头已经排序得到的最大元素与队尾元素 swap(num, 0, j); System.out.print("第"+(num.length-j)+"次排序后: "); for(int k=0;k<num.length;k++) { System.out.print(num[k]+" "); } System.out.println(); //交换结束之后,大根堆已经被破坏,需要开始重新构建大根堆 buildbigheap(num,j); } long endTime=System.currentTimeMillis(); System.out.println("程序运行时间： "+(endTime-startTime)+"ms"); }
这里我们将这两个排序结果对比一下,大家就更加能了解重新校验步骤的重要性了.
相信经过我这样的讲解之后,大家一定能够更好的理解堆排序了.
复杂度分析:
理解完堆排序的基本思想之后,我们就需要来分析一下他的时间复杂度,空间复杂度.
时间复杂度
堆排序的本质思想也是利用了二叉树的特性,所以根据他的遍历次数以及二叉树的层数可以得到堆排序的时间复杂度为O(N*logn),不仅仅是平情况是这样最好与最坏的情况都是如此.
空间复杂度
这个我们可以看到我们整个排序的过程中只增加一个存储交换元素的temp,所以堆排序的空间复杂是常量级别的仅为O(1).
