我直接把代码贴出来了，晕，我发了一遍怎么突然博客就没了，刚开始还不太熟悉 进入正题：我实现的是三向切分的快速排序，和采用随机切分点，这么做有几个好处，一个是对于重复元素很多的数组有很好的性质，可以从代码中看到重复的元素并不执行交换操作，考虑一个极端条件，数组全是{1,1,1,1…1}，可以看到只用遍历一次数组就可以了，是O(N)时间复杂度。使用随机切分点的好处是使得最坏条件出现的几率大大大幅度下降，比如每次都取得最小值或者最大值。
.h /* author : yb time: 2016 12 2 edition: 1.0 describe:快速排序的实现 */ class Cquick { public: Cquick(); Cquick(int n); void exchange(int i , int j); void quickSort(int lo,int ed); //void partition(int lo, int ed); void show(); private: int *a; int Num; }; .cpp /* author : yb time: 2016 12 2 edition: 1.0 describe:快速排序的实现 */ #include "quick.h" #include <iostream> #include <stdio.h> using namespace std; Cquick::Cquick(int n):Num(n) { a = new int[n]; for (int i = 0 ; i<n;i++) { a[i] = rand()%100; } } void Cquick::exchange(int i , int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } void Cquick::quickSort(int lo , int ed)//出现个问题，晕晕乎乎的，第一：迭代没写返回条件 { // 第二：在切分时，边界条件没搞清楚 int k = rand()%(Num-1); int val = a[k]; //cout<<"K:"<<k<<endl; int i = lo; int it = lo; int j = ed; if (lo >= ed) { return; } while (i <= j) { if (a[i] < val) { if (i != it)//i和it不相等的时候才交换,将小于val的值交换到it左边 { exchange(i , it); } i++; it++; } else if (a[i] > val) { exchange(i ,j); j--; } else { i++; } } quickSort(lo , it - 1 ); quickSort(i , ed); } void Cquick::show() { for (int i = 0;i<Num;i++) { cout<<a[i]<<" "; } } void main() { Cquick myquick(20); myquick.show(); cout<<endl<<"after quick sort:"<<endl; myquick.quickSort(0,19); myquick.show(); }