剑指offer——面试题11：快速排序

 1 #include"iostream"
 2 #include"random"
 3 using namespace std;
 4 
 5 /*
 6 void Swap(int &a,int &b)
 7 {
 8     int tmp;
 9     tmp=a;
10     a=b;
11     b=tmp;
12 }
13 */
14 //官方给的partition函数
15 int Partition1(int *data,int start,int end)
16 {
17     int index=start+(rand()%(end-start+1));
18     swap(data[index],data[end]);
19     int small=start-1;
20     for(index=start;index<end;index++)
21     {
22         if(data[index]<data[end])
23         {
24             small++;
25             if(index!=small)
26                 swap(data[index],data[small]);
27         }
28     }
29     small++;
30     swap(data[small],data[end]);
31     return small;
32 }
33 
34 //自定义Partition函数
35 int Partition2(int *data,int start,int end)
36 {
37     int value=data[start];
38     while(start<end)
39     {
40         while(start<end)
41         {
42             if(data[end]>value)
43                 end--;
44             else
45                 break;
46         }
47         if(start<end)
48             data[start++]=data[end];
49         while(start<end)
50         {
51             if(data[start]<=value)
52                 start++;
53             else
54                 break;
55         }
56         if(start<end)
57             data[end--]=data[start];
58     }
59     data[start]=value;
60     return start;
61 }
62 
63 void QuickSort1(int *data,int start,int end)
64 {
65     if(start==end) return;
66 
67     int mid=Partition1(data,start,end);
68     if(mid>start)
69         QuickSort1(data,start,mid-1);
70     if(mid<end)
71         QuickSort1(data,mid+1,end);
72 }
73 
74 void QuickSort2(int *data,int start,int end)
75 {
76     if(start==end) return;
77 
78     int mid=Partition2(data,start,end);
79     if(mid>start)
80         QuickSort2(data,start,mid-1);
81     if(mid<end)
82         QuickSort2(data,mid+1,end);
83 }

QuickSort.h

 1 #include"QuickSort.h"
 2 
 3 void Test1()
 4 {
 5     int data[10]={6,4,1,5,2,9,8,10,3,7};
 6     cout<<"use QuickSort1:";
 7     QuickSort1(data,0,9);
 8     for(int i=0;i<10;i++)
 9         cout<<data[i]<<" ";
10     cout<<endl;
11 }
12 
13 void Test2()
14 {
15     int data[10]={6,4,1,5,2,9,8,10,3,7};
16     cout<<"use QuickSort2:";
17     QuickSort2(data,0,9);
18     for(int i=0;i<10;i++)
19         cout<<data[i]<<" ";
20     cout<<endl;
21 }
22 int main()
23 {
24     Test1();
25     Test2();
26 }

TestQuickSort.cpp