网站推广苏州,注册一个个人网站,html网页生成,谢岗网站建设公司Hoare版 快速排序是由Hoare发明的#xff0c;所以我们先来讲创始人的想法。我们直接切入主题#xff0c;Hoare版快速排序的思想是将一个值设定为key#xff0c;这个值不一定是第一个#xff0c;如果你选其它的值作为你的key#xff0c;那么你的思路也就要转换一下#xf… Hoare版 快速排序是由Hoare发明的所以我们先来讲创始人的想法。我们直接切入主题Hoare版快速排序的思想是将一个值设定为key这个值不一定是第一个如果你选其它的值作为你的key那么你的思路也就要转换一下好我们刚刚说到将一个值设为key这里我们就将第一个值设为key就好了left在最左边right在最右边我们设定好key值之后先让right往左走目标是找小找到比key小的值就停下再让left往右走目标是找大找到比key大的值就停下然后交换right和left的值这样就会让大的那一个值到右边小的那一个值到左边交换完后再让right先走以此类推直到相遇相遇后的那个值再跟key进行交换一趟就结束了快速排序的一个特点是每一趟走完都会定下这个key值的位置也就是说每一趟走完都将固定一个值然后进行递归把所有值都固定就排序完成了。 接下来说说第二趟也就是如何来递归我们前面说过了每一趟都会确认一个值的位置那么我们的步骤就是类比二叉树的后序遍历一样以固定的值为最左值或最右值依次固定住所有的该在的位置。 我们已经知道每一趟都会确定key值以及位置那么我们就将每一趟排序的过程单独封装成一个函数PartSort1.既然是递归那么我们肯定要有结束条件吧结束条件就是beginend为什么是这个呢我们看下面的代码我说过了类似后序遍历的思想所以我们就写出了先找左再找右的递归代码第一个QuickSort就是往左递归嘛那么起始位置就是begin不变右边的界限就是我们通过函数找出来的kkey交换后的下标但是要减一因为key的下标k已经是确定好的了嘛就不需要访问它了第二个QuickSort自然就是访问右边了访问右边最右边就不用动最左边是k1理由跟上面的是一样的。 这样我们就理解了第一个QuickSort后如果只有一个数据可以访问那么begin是end的就该停止那么第二QuickSort个可能就是没有数据这个时候begin就会大于end也要停止接下来我们具体看看排序部分是怎么写的。 从上往下的思路是left等于最左值right等于最右值key也等于最左值的下标当还没相遇的情况下循环就会继续按照思路先让右边找小找到就停止但是不要漏了后面的条件因为如果没有找到就会一直往左走到最后right就变成负的了。同理下面left的思路也是一样的left和right都找到后就交换当两个相遇之后把key的值跟他们交换就行了。然后返回新的key下标。
