一、算法描述 快速排序是基于分治法的排序算法的一种。 三个步骤： 分解：数组A[p..r]被划分成两个子数组A[p..q-1]和A[q+1..r],使得A[p..q-1]中的每个元素都小于A[q],而且，小于等于A[q+1..r].下标q也在这个划分过程中进行计算。 解决：通过递归调用快速排序，对子数组A[p..q-1]和A[q+1..r]排序。 合并：递归到最后已经全部有序，不许要合并处理。 一趟快速排序的算法是： 1）设置两个变量I、J，排序开始的时候：I=0，J=N-1； 2）以第一个数组元素作为关键数据，赋值给key，即 key=A[0]； 3）从J开始向前搜索，即由后开始向前搜索（J=J-1即J--），找到第一个小于key的值A[j]，A[j]与A[i]交换； 4）从I开始向后搜索，即由前开始向后搜索（I=I+1即I++），找到第一个大于key的A[i]，A[i]与A[j]交换； 5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后令循环结束。）
二、代码清单
/*QuickSort*/ void quickSort(elementType a[],int size) { q_Sort(a,0,size-1); } void q_Sort(elementType a[],int left,int right) { if(right<=left) return; int i=left,j=right; //将数组最后一个元素赋给key elementType key=a[right]; while(i key&&i
三、时间复杂度讨论
整体复杂度是O(nlgn).
最坏情况是原序列有序，每次划分成两部分都是1，n-1，快排退化，时间复杂度O(n^2)。
为了避免退化，解决方法是随机取key值，或是每次取开头，中间，结尾三个数、取这三个当中中间的数为key等技巧进行优化。
参考书籍：算法导论（第二版）
《ACM-ICPC算法基础》