快速排序的在內排中起到比較重要的作用，平均時間復雜度達到O(nlogn)。
升序快速排序
1 int partition(vector<int> &vi,int start,int end){
2 int key=vi[start];
3 while(start<end){
4 while(start<end&&vi[end]>=key)
5 end--;
6 vi[start]=vi[end];
7 while(start<end&&vi[start]<key)
8 start++;
9 vi[end]=vi[start];
10 }
11 vi[start]=key;
12 return start;
13 }
14 void quickCore(vector<int> &vi,int start,int end){
15 if(start<end){
16 int idx =partition(vi,start,end);
17 quickCore(vi,start,idx-1);
18 quickCore(vi,idx+1,end);
19 }
20 }
21
22 void quickSort(vector<int>&vi){
23 quickCore(vi,0,vi.size()-1);
24 }
指定排序順序快速排序
1 bool cmp(const int &a,const int &b){
2 return (b-a>=0)?true:false;
3 }
4 bool rcmp(const int &a,const int &b){
5 return (b-a>=0)?false:true;
6 }
7 int partition(vector<int> &vi,int start,int end,bool (*cmp)(const int&,const int&)){
8 int key=vi[start];
9 while(start<end){
10 while(start<end&&cmp(key,vi[end]))
11 end--;
12 vi[start]=vi[end];
13 while(start<end&&!cmp(key,vi[start]))
14 start++;
15 vi[end]=vi[start];
16 }
17 vi[start]=key;
18 return start;
19 }
20 void quickCore(vector<int> &vi,int start,int end,bool (*cmp)(const int&,const int&)){
21 if(start<end){
22 int idx =partition(vi,start,end,cmp);
23 quickCore(vi,start,idx-1,cmp);
24 quickCore(vi,idx+1,end,cmp);
25 }
26 }
27
28 void quickSort(vector<int>&vi,bool (*cmp)(const int&,const int&)){
29 quickCore(vi,0,vi.size()-1,cmp);
30 }
指定任意對象和排序規則的快速排序
1 struct component{
2 int a;
3 int b;
4 };
5 bool cmp(const component& obj1,const component& obj2){
6 if(obj2.a>obj1.a)
7 return true;
8 else if(obj2.a<obj1.a)
9 return false;
10 else if(obj2.b>=obj1.b)
11 return true;
12 return false;
13 }
14 bool rcmp(const component& obj1,const component& obj2){
15 if(obj1.a>obj2.a)
16 return true;
17 else if(obj1.a<obj2.a)
18 return false;
19 else if(obj1.b>=obj2.b)
20 return true;
21 return false;
22 }
23
24 template<class T>
25 int partition(vector<T> &vi,size_t start,size_t end,bool (*cmp)(const T&,const T&)){
26 T key=vi[start];
27 while(start<end){
28 while(start<end&&cmp(key,vi[end]))
29 end--;
30 vi[start]=vi[end];
31 while(start<end&&!cmp(key,vi[start]))
32 start++;
33 vi[end]=vi[start];
34 }
35 vi[start]=key;
36 return start;
37 }
38 template<class T>
39 void quickCore(vector<T> &vi,size_t start,size_t end,bool (*cmp)(const T&,const T&)){
40 if(start<end){
41 size_t idx =partition(vi,start,end,cmp);
42 quickCore(vi,start,idx-1,cmp);
43 quickCore(vi,idx+1,end,cmp);
44 }
45 }
46 template<class T>
47 void quickSort(vector<T>&vi,bool (*cmp)(const T&,const T&)){
48 quickCore(vi,0,vi.size()-1,cmp);
49 }
迭代器類型快速排序
1 struct component{
2 int a;
3 int b;
4 };
5 bool cmp(const component& obj1,const component& obj2){
6 if(obj2.a>obj1.a)
7 return true;
8 else if(obj2.a<obj1.a)
9 return false;
10 else if(obj2.b>=obj1.b)
11 return true;
12 return false;
13 }
14 bool rcmp(const component& obj1,const component& obj2){
15 if(obj1.a>obj2.a)
16 return true;
17 else if(obj1.a<obj2.a)
18 return false;
19 else if(obj1.b>=obj2.b)
20 return true;
21 return false;
22 }
23 bool cmp1(const int &a,const int &b){
24 return (b-a>=0)?true:false;
25 }
26 bool rcmp1(const int &a,const int &b){
27 return (b-a>=0)?false:true;
28 }
29 template<class Iterator, class Comparator>
30 Iterator partition(Iterator start,Iterator end,Comparator cmp){
31 typedef typename iterator_traits<Iterator>::value_type value_type;
32 value_type key=*start;
33 while(start!=end-1){
34 while(start!=end-1&&cmp(key,*(end-1)))
35 end--;
36 *start=*(end-1);
37 while(start!=end-1&&!cmp(key,*start))
38 start++;
39 *(end-1)=*start;
40 }
41 *(end-1)=key;
42 return end-1;
43 }
44 template<class Iterator, class Comparator>
45 void quickCore(Iterator start,Iterator end,Comparator cmp){
46 if(start !=end){
47 Iterator idx =::partition(start,end,cmp);
48 quickCore(start,idx,cmp);
49 quickCore(idx+1,end,cmp);
50 }
51 }
52 template<class Iterator, class Comparator>
53 void quickSort(Iterator start,Iterator end,Comparator cmp){
54 quickCore(start,end,cmp);
55 }
56 template<class Iterator>
57 void quickSort(Iterator start,Iterator end){
58 quickCore(start,end,less<typename iterator_traits<Iterator>::value_type>());
59 }
測試
1 #include <iostream>
2 #include<vector>
3 #include<algorithm>
4 #include<set>
5 using namespace std;
6
7 int main( )
8 {
9 vector<int> vi{1,7,3,1};
10 quickSort(vi.begin(),vi.end());
11 sort(vi.begin(),vi.end(),cmp1);
12 for(int i=0;i<vi.size();i++)
13 cout<<vi[i]<<" ";
14 cout<<endl;
15
16 vector<component> obj{
17 {1,4},
18 {3,6},
19 {2,8},
20 {2,7},
21 {1,1}
22 };
23 quickSort(obj.begin(),obj.end(),cmp);
24 for(int i=0;i<obj.size();i++){
25 cout<<obj[i].a<<" "<<obj[i].b<<endl;
26 }
27 return 0;
28 }
