快排（quick sort），，是快速排序的简称。快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 快排有很多版本，不同的版本其写法略有差别，此处给出一种双指针扫描法。 具体做法是：（此处是升序，降序同理）
1.需要排序的区间是的数，设为val，否则退出 2.在区间中，将小于val的数放在左边，将大于等于val的数放在右边，将val这个值放在中间，让pos等于此位置 3.递归将排序
/*Author: RoyecodeDate: 2015-07-22*///将数组升序排序#include <iostream>#include <cstdlib>#include <ctime>#include <vector>using namespace std;//将l到r排好序void quick_sort(int l, int r, int *arr){if(l < r){int begin = l, end = r, val = arr[l];while(begin < end){while(begin < end && arr[end] >= val) –end;//将大于等于val的数放在右边if(begin < end) arr[begin] = arr[end];while(begin < end && arr[begin] < val) ++begin; //将小于val的数放在左边if(begin < end)arr[end] = arr[begin];}arr[begin] = val;//begin位置的数已确定，将[l, begin – 1]排序，将[begin + 1, r]排序 quick_sort(l, begin – 1, arr);quick_sort(begin + 1, r, arr);}}int main(){srand(time(NULL));const int size = 8;int arr[size];for(int i = 0; i < size; ++i) //随机生成范围[0,size)的size个数arr[i] = rand() % size;for(int i = 0; i < size; ++i) //排序前cout << arr[i] << “\n”[i != size – 1];quick_sort(0, size – 1, arr);for(int i = 0; i < size; ++i) //排序后cout << arr[i] << “\n”[i != size – 1];return 0;}
一般来说，快排的时间复杂度是，可以采取一定措施避免这一点，那就是在开始排序的时候，写一个函数将需要排序的数组打乱顺序。做法如下：
void disorderly(int *arr, int n){srand(time(NULL));for(int i = 0; i < n; ++i){int x = rand() % n, y = rand() % n;//随机生成[0, n)的两个下标swap(arr[x], arr[y]);}}
所以快排的时间复杂度是。
那绿叶上的水珠，是思念的泪滴。
