1 #include <iostream> 2 /* 3 入门之快速排序 4 时间复杂度：O(nlogn) 5 最坏情况时时间复杂度能达到O(n^2) 6 借鉴自算法导论 7 */ 8 #include <algorithm> 9 using namespace std; 10 int a[5] = {2,4,1,5,3}; 11 void quick_sort3(int *a,int l,int r)//枢轴可以是任意一个位置的数 12 { 13 if(l >= r) return; 14 int k = a[r],i = l,j = r; 15 while(i < j){ 16 while(i < j && a[i] <= k) ++i; 17 while(i < j && a[j] >= k) --j; 18 if(i != j) swap(a[i],a[j]); 19 } 20 swap(a[i],a[r]); 21 quick_sort3(a,l,i-1); 22 quick_sort3(a,i+1,j); 23 } 24 void quick_sort2(int *a,int l,int r)//枢轴只能是最后一个 25 { 26 if(l >= r) return; 27 int t = a[r],j = l-1; 28 for(int i = l; i <= r; ++i) 29 if(a[i] < t) 30 { 31 ++j; 32 if(i != j) 33 swap(a[i],a[j]); 34 } 35 swap(a[j+1],a[r]); 36 quick_sort2(a,l,j); 37 quick_sort2(a,j+2,r); 38 } 39 void quick_sort(int *a,int l,int r)//枢轴只能是第一个 40 { 41 if(l >= r) return; 42 int m = a[l],i = l, j = r; 43 while(i < j){ 44 while(i < j && a[j] >= m) --j; a[i] = a[j]; 45 while(i < j && a[i] <= m) ++i; a[j] = a[i]; 46 } 47 a[i] = m; 48 quick_sort(a,l,i-1); 49 quick_sort(a,i+1,r); 50 } 51 int main() 52 { 53 quick_sort2(a,0,4); 54 for(int i = 0; i < 5; ++i) 55 cout << a[i] << " "; 56 cout << endl; 57 return 0; 58 }