C语言实现Hoare版快速排序（递归版）

Hoare版

快速排序是由Hoare发明的，所以我们先来讲创始人的想法。我们直接切入主题，Hoare版快速排序的思想是将一个值设定为key，这个值不一定是第一个，如果你选其它的值作为你的key，那么你的思路也就要转换一下，好，我们刚刚说到将一个值设为key（这里我们就将第一个值设为key就好了），left在最左边，right在最右边，我们设定好key值之后，先让right往左走（目标是找小），找到比key小的值就停下，再让left往右走（目标是找大），找到比key大的值就停下，然后交换right和left的值，这样就会让大的那一个值到右边，小的那一个值到左边，交换完后再让right先走，以此类推直到相遇，相遇后的那个值再跟key进行交换，一趟就结束了，快速排序的一个特点是每一趟走完都会定下这个key值的位置，也就是说每一趟走完都将固定一个值，然后进行递归，把所有值都固定就排序完成了。

接下来说说第二趟也就是如何来递归，我们前面说过了，每一趟都会确认一个值的位置，那么，我们的步骤就是类比二叉树的后序遍历一样，以固定的值为最左值或最右值，依次固定住所有的该在的位置。

我们已经知道，每一趟都会确定key值以及位置，那么我们就将每一趟排序的过程单独封装成一个函数PartSort1.既然是递归，那么我们肯定要有结束条件吧，结束条件就是begin>=end，为什么是这个呢？我们看下面的代码，我说过了，类似后序遍历的思想，所以我们就写出了先找左，再找右的递归代码，第一个QuickSort就是往左递归嘛，那么起始位置就是begin不变，右边的界限就是我们通过函数找出来的k（key交换后的下标），但是要减一，因为key的下标k已经是确定好的了嘛，就不需要访问它了；第二个QuickSort自然就是访问右边了，访问右边最右边就不用动，最左边是k+1，理由跟上面的是一样的。

这样我们就理解了，第一个QuickSort后如果只有一个数据可以访问，那么begin是==end的，就该停止，那么第二QuickSort个可能就是没有数据，这个时候begin就会大于end，也要停止，接下来我们具体看看排序部分是怎么写的。

从上往下的思路是left等于最左值，right等于最右值，key也等于最左值的下标，当还没相遇的情况下，循环就会继续，按照思路先让右边找小，找到就停止，但是不要漏了后面的条件，因为如果没有找到，就会一直往左走，到最后right就变成负的了。同理，下面left的思路也是一样的，left和right都找到后就交换，当两个相遇之后，把key的值跟他们交换就行了。然后返回新的key下标。