这篇文章酝酿了好几天，今天终于开始敲击键盘写出来。之前学习数据结构与算法是大一下期的一门课程，但是那个们课老师的水平实在不敢恭维，讲的数据结构和算法都是在很浅的层次，仅此是PPT课，后来由于自己对算法这一块比较感兴趣，所以就自己自学了一些内容，今天想在这里写一篇博客全当是抛砖引玉吧，希望大家不吝赐教！
快速排序算法其实很简单，但是应用起来又不是那么简单，为什么这样说呢？因为单纯的想要理解算法的原理，是很简单的，不过就三个步骤：①分解②解决③合并，写出来代码也是相对简单的一件事情。
但是！！在待排序的数组内的数据不同的情况下，它的性能也不尽相同，比较好的情况下，复杂度正比于 Nlg（n），但是在坏的情况下，复杂度会退化到N^2级别。
所以本文就先说明快速排序的基本原理，然后再逐步写出它的改进版的算法和应用的情况。
首先快速排序可以由三个步骤组成：
①分解： 分解就是 把整个数组分解为两个，例如 A[p...r]分解为 两个（可能为空）的子数组 A[p...q-1]和A[q+1...r]使的A[p...q-1]中的每个元素都小于A[q]，而A[q+1...r]中的每个元素都大于A[q]。
②解决： 通过递归调用快速排序，对数组A[p...q-1]和A[q+1...r]进行排序。
③合并：因为子数组都是原址排序的，所以不需要合并操作，数组A[p...r]已经有序了。
其实无非就是，找到一个固定的元素（一般都选第一个或者最后一个，但是也有随机选择的），然后扫描整个数组，最后的状态就是比这个固定元素小的元素都在它左边，比它大的元素都在他右边。等于的它元素要看自己的代码怎么写了，可能在左也可能在右。（从这里其实可以看出来，快速排序不是一种稳定的排序方法）
一：第一种版本的快速排序（这是最简单的一种版本的，它是单向扫描的，所以权且成为单描版）
结合着算法导论的图片更容易理解：
等于是两个指针一起扫描，遇到比目标元素小的就交换到左边，遇到大于等于目标元素的就保持在两个指针之间。
以下是代码：
void quick_sort(int A[],int q,int r) { if(p < r) { q = partition(A,p,r); quick_sort(A,0,q-1); quick_sort(A,q+1,r); } }
上面是递归调用的算法。
int partition(int A[],int p,int r)//r其实为数组最边那个元素的下标，也就是n-1位置 { int x = A[r]; int i = p - 1; for(int j = p;j <= r - 1;j++) { if(A[j] <= x) { i++; swap(A[i],A[j]); } } swap(A[i+1],A[r]); return i+1; }
此代码是从左往右单向扫描的（也可以改为从右往左，纯粹是个人喜好） 上面的代码有什么毛病？其实毛病是大大滴！理想情况下，它的复杂度应该是Nlg（n），可如果待排序的数组本来就是有序的或者说是接近于有序，它就会退化到n^2级别，为什么？ 想象下，1 2 3 4 5 6 7 8 9 10 这几个有序的数字。 假设选择第一个元素 1 作为固定元素。第一遍扫描结束后数组分为 1和2 3 4 5 6 7 8 9 10，两部分，然后递归调用，第三次分为 2和3 4 5 6 7 8 9 10 两部分，依次类推。 那么有没有方法能够克服呢？
二 双向的快速排序
那就要看接下来这个版本的快速排序了，它采用双向排序的思想，从左到右，从右到左都扫描。
int partition(int l,int u) { int t = A[l]; int i = l; int j = u; while(i < j) { //从右向左，找小于t的数 while(i < j&&A[j] >= t) { j--; } if(i < j) //说明从右向左找到了一个数小于t，于是把这个数放到左边的坑里 { A[i] = A[j]; i++; //i++ 说明这个坑的元素已经找到放好，然后找未知区域 } //从左到右去找大于t的数字 while(i < j&&A[i] <t) { i++; } if(i < j)//说明从左到右找到了一个数大于t，于是把这个数字放到右边的坑里 { A[j] = A[i]; j--;//j-- 说明这个坑的元素已经放好，然后找未知区域 } } //退出时 已经保证t左边的元素都小于t，t右边的元素都大于t，此时i=j A[i] = t; return i; }
编程珠玑上还讲了一种建议，就是在数组较短的情况下，插入排序的性能更优，所以还有一种思路就是在递归前判断数组的长度，如果不算太长就调用插入排序。
但是什么样的长度才算不太长？在《算法》中作者的建议是15左右包括15在内的数组，用插入排序更加适合。
还有第三种快速排序的算法：
三， 三向排序
示意图如图所示：
它的思路其实只要你理解了上面的两种，他是很简单的。
关键就是再一个过程种让数组满足一下三个条件：
①对于某个j a[j]已经排定。
②a[lo] 到a[j-1]中所有的元素都不大于a[j]
③a[j+1] 到 a[hi]中所有的元素都不小于a[j]
代码：
void sort(int []a,int lo,int hi) { if(hi <= lo) return; int lt = lo,i = lo + 1,gt = hi;//lt,i,gt相当于三个游动的指针 v = a[lo]; while(i <= gt) { if(a[i] < v) { swap(a[lt],a[i]); i++; lt++; } else if(a[i] > v) { swap(a[gt],a[i]); gt--; } else if(a[i] == v) { i++; } } sort(a,lo,lt-1); sort(a,gt+1,hi); }
好了，上面就是我对快速排序算法的一些浅薄的见解和学习，希望能对你有用，也更希望有大佬能够批评指正。
参考资料：《编程珠玑》
《算法导论》
《算法》
