快速排序是由Hoare提出的一种排序方法，对于这种排序方法，复杂度是N乘logN。是一种比较高效的排序方法！
这种排序的的基本思想简单阐述一下就是，找一个key值，这个key值一般选择数组首末位置比较合理！如果选择了首位置（升序排列），那么我们就从右边开始遍历，寻找比key值小的值，而后从左边开始遍历，寻找比key值大的值！当他们各自找到对应应数字后，进行交换，而后继续左右遍历。当begin与end重合的时候，那么我们将重和点位置的值与key进行交换即可！我这里所说的是一个单趟排列。单趟捋清后，多躺就是多加几个递归循环即可！
下面是单趟排序代码！
//这三种方法只针对于单趟排序进行优化！多趟排序的递归代码是没有差别的 //快速排序（hoare版本,左右指针法） void PartSort(int *a, int begin, int end){ //end做key，左边先走 。begin做key，右边先走！ int key = a[end]; int keyindex = end; while (begin < end) { while (begin<end&&a[begin]<=key) { ++begin; } while (begin < end&&a[end] >= key) { --end; } Swap(&a[begin], &a[end]); } Swap(&a[keyindex], &a[begin]); }
这里我简单阐述一下左右指针法代码的含义以及注意事项：首先形参传入数组，首末位置！而后选择key值，我们这里选择的是末尾做我们的key值，而后应为进行最终交换的时候，我们要交换的不是key值与起始位置（begin与end最终指向同一个地方）而是key这个位置的值与begin（end）最终重合位置的值，所以选择设立keyindex这个变量来保存end位置，方便交换！这个地方很容易出现错误！接下来，当begin位置小于end位置时，在begin<end的情况下，从begin头位置寻找大于key的值！走出循环，已经找到！而后，在begin<end的情况下，从末尾end位置开始遍历查找小于key的值！而后交换这次查找所找到的两个值。而后继续进行循环，直至begin不再小于end，前后位置重合的时候！我们就交换刚才提到的keyindex的值与begin（或者end，因为两个位置是重合的）的值！则单趟排序圆满完成！
//挖坑法
挖坑法可以说是对左右指针法的一个优化。而后拿选出的key值作为一个坑，来是遍历，遍历规则与左右指针法相同，拿 升序来说，选择最后一个位置作为key值。那么最后一个位置就可以看作是一个坑，从begin位置开始，寻找一个比key值大的数字，找到后与key值进行交换！咋交换后，新坑就产生了，而后从end位置开始寻找一个比key值小的数字，找到后与上一次产生的坑进行交换！这样几轮下来，begin与end就会重合！就把key值放到产生的最后一个坑内！而后返回这个key值最后待的位置！挖坑法不会产生左右指针法那样 交换值但位置没变的困扰！就解决了keyindex的存在！ int PartSort(int *a, int begin, int end) { int key = a[end]; while (begin < end) { //找大 while (begin < end&&a[begin] <= key) ++begin; a[end] = a[begin];//找到大扔到右边的坑里面去，同时begin形成新的坑位！ while (begin < end&&a[end] >= key) --end; a[begin] = a[end];//找到小的扔到左边的坑位中去，同时end形成新的坑位！ } a[begin] = key; return begin; }
前后指针法 //1.找到小的以后停下，++prev,交换prev与cur位置的值！ //2.当cur遇到endkey的位置就停下来，然后++prev，再交换key和prev
对于前后指针法，是一种相当新颖的优化方式！会给出一个cur，一个end，还有一个prev。prev指向begin的前一个位置！选择末位置end等于key！当cur小于end，cur进行遍历，当找到小于key值得就停下，++prev，而后交换prev位置与cur位置的值！当cur遇到末尾的key值时，就停下来，再对prev进行一次++，而后交换末尾位置值与prev位置的值！ void PrevCurMethod(int *a, int begin, int end) { int prev = begin - 1; int cur = begin; int key = a[end]; while (cur < end) { if (a[cur] < key&&++prev != cur) //在这里，第一个条件为假，就不会走第二个条件 ，也就不会对prev进行加加！ Swap(&a[prev], &a[cur]); ++cur; } ++prev; Swap(&a[prev], &a[end]);
return prev； }
快速排序的多趟排序总代码
void QuickSort(int *a, int begin, int end){ if (begin >= end) return; int keyindex = PartSort(a, begin, end); QuickSort(a, begin, keyindex - 1); QuickSort(a, keyindex - 1, end); }
形参传入数组，起始位置与末位置！当起始位置大于等于末位置，直接跳出返回！寻找keyindex值，该值将整个数组区间分为了[begin,keyindex-1] keyindex [keyindex+1,end].而后分别对前半部分与后半部分分别使用递归，就可以吧杂乱顺序的数组排成一个有序的数组！
