数据结构：排序（2）|| 快速排序
气泡排序
特性：反复交换相邻序列值，从而达到排序目的
时间复杂度：O(n^2)
气泡排序应该十分熟悉了，这里就略过了。
快速排序
快速排序简称快排，是对气泡排序的一种改进，是一种递归算法，通过一趟排序将待排记录分为独立两部分，在某一枢轴量左侧，均是小于它的值，在其右侧，均是大于它的值，对序列不断分割，最后会形成有序序列。
void QSort(Sqlist &L,int low,int high){int pivotloc;if(low<high){pivotloc=Partition(L,low,high);QSort(L,low,pivotloc-1);QSort(L,privotloc+1,high);}}
Partition函数的作用是，对low，high区间进行快排，返回枢轴位置
快速排序图解
Partition函数在使用过程中有“反复横跳”的感觉。
当low方向发现一个不合法数据，立刻跳转至high，将high覆盖，注意，由于枢轴被暂存，在数据中是有一个空格存在的，最后枢轴放进去，空格填补排序结束，返回枢轴位置。
int Partition(Sqlist &L, int low, int high){L[0] = L[low]; //暂存int pivotkey = L[low]; //令low处值为枢轴//反复横跳式判断while (low < high){while (low < high && L[high] >= pivotkey)--high; //该循环将high移动到了第一个不合法的位置L[low] = L[high]; //low用high覆盖，第一个low已经保存了所以不用担心lowwhile (low < high && L[low] <= pivotkey)++low; //移动low到第一个不合法位置L[high] = L[low];}//出口一定是low=highL[low] = L[0];return low; //返回枢轴位置便于下次调用}
时间复杂度分析
快速排序的时间复杂度：k*n*ln(n)
通常快速排序被认为是这一类较先进的排序方法中平均性能最好的，所以它叫做快速排序。但是如果对基本有序或已经有序的序列排序时，它会退化为气泡排序。详细分析过程见书。