1. 快排的基本原理：
（1）在数据集之中，选择一个元素作为"基准"（pivot）。
（2）所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
（3）对"基准"左边和右边的两个子集，不断重复上述过程，直到所有子集只剩下一个元素为止。
2. 快排的特点：
快速排序是一种不稳定的排序，在最坏情况下时间复杂度为O（n2），平均时间复杂度为O（nlogn）。
快速排序适用的情况是：数据是杂乱无章的，每次选择基准后，小于和大于基准的元素数量基本相同，此时快排的速率最优，时间复杂度O（nlogn）
快速排序不适用的情况是：在数据有序或者逆序的情况下，选择基准后，左右两边元素数量极不均衡，此时快排的速率最差，时间复杂度O（n*n）
3.对于基准的选取，采用取数组首元素的二分Partition算法，C++代码如下：
/*采用partition算法分割数组，比枢纽小的在数组左边，比枢纽大的在数组右边，返回枢纽所在位置*/ int Partition(vector<int> &A, int start, int end) { int pivot = A[start]; //枢纽取第一个元素 while(start < end) { while(start<end && A[--end]>=pivot); A[start] = A[end]; while(start<end && A[++start]<=pivot); A[end] = A[start]; } A[start] = pivot; return start; //返回位置！！！ } int quicksort(vector<int> &A, int start, int end) { if(start < end) { //用partition算法分割数组，小于枢纽在左，大于枢纽在右，返回枢纽所在的位置 int pos = Partition(A,start,end); //递归地再次排序比枢纽小的元素集合和比枢纽大的元素集合 quicksort(A,start,pos); quicksort(A,pos+1,end); } } void QuickSort(vector<int> &A) { int start = 0; int end = A.size(); quicksort(A,start,end); }
4. 对于基准的选取，可以采用“三位取中”的做法，C++代码如下：
int GetPivot(std::vector<int> & a, int left, int right) { int center = (left+right)/2; if(a[left] > a[center]) std::swap(a[left],a[center]); if(a[left] > a[right]) std::swap(a[left],a[right]); if(a[center] > a[right]) std::swap(a[center],a[right]); //下面这个交换一定要做！！！ if(a[center] != a[right-1]) std::swap(a[center],a[right-1]); return a[right-1]; } void quicksort(std::vector<int> & a, int left, int right) { static int count_quick = 1; if(left < right) { std::cout<<"进行第 "<<count_quick++<<" 次快速排序 "; //取 { a[left]、a[right]、a[(left+right)/2] } 三数中，中间那个数作为基准 int pivot = GetPivot(a,left,right); int i = left; //真正的基准值放在right-1的位置，即rigt-1不用比较，直接从right-2向右比较 int j = right-1; //比枢纽大的在右边，比枢纽小的在左边 while(i<j) { while(a[++i] < pivot); while(a[--j] > pivot); if(i<j) std::swap(a[i],a[j]); } //此时i一定比基准值大，将其与基准值调换位置 std::swap(a[i],a[right-1]); //分治思想：递归枢纽的左边数组和右边数组 quicksort(a,left,i-1); quicksort(a,i+1,right); } } void QuickSort(std::vector<int> & a) { quicksort(a,0,a.size()-1); }