快速排序三指针分区法

千公子

有相同元素值的快速排序——三分法
三分法有三个指针，一个向右扫描比主元小的元素指针，
一个记录与主元相等元素的指指，另一个是从右向左扫描
比主元大的元素指针。
将数组分为四个区，小于主元区，等于主元区，未知区，
与大于主元区

千公子

1. #include <iostream>
   
2. 
   
3. using namespace std;
   
4. 
   
5. void swap(int arr[], int a, int b)
   
6. {
   
7.     int temp = arr[a];
   
8.     arr[a] = arr[b];
   
9.     arr[b] = temp;
   
10. }
    
11. 
    
12. void quick_sort(int arr[], int left, int right)
    
13. {
    
14.     if(left >= right)
    
15.         return;
    
16. 
    
17.     int e = left + 1; //记录等于主元的指针
    
18.     int sp = left + 1; //扫描小于主元元素指针
    
19.     int bigger = right; //扫描大于主元元素指针
    
20.     int pivot = arr[left]; //主元
    
21.     while(sp <= bigger)
    
22.     {
    
23.         while(sp <= bigger && arr[sp] < pivot)
    
24.         {
    
25.             e++;
    
26.             sp++;
    
27.         }
    
28.         while(sp <= bigger && arr[sp] == pivot)
    
29.         {
    
30.             swap(arr, e, sp);
    
31.             e++;
    
32.             sp++;
    
33.         }
    
34.         while(sp <= bigger && arr[bigger] > pivot)
    
35.             bigger--;
    
36.         
    
37.         if(sp < bigger)
    
38.             swap(arr, bigger, sp);
    
39.     }
    
40.     swap(arr, bigger, left);
    
41.     quick_sort(arr, left, bigger-1);
    
42.     quick_sort(arr, bigger+1, right);
    
43. }
    
44. 
    
45. int main()
    
46. {
    
47.     int arr[10] = {5, 1, 2, 4, 3, 6, 1, 1, 2, 2};
    
48.     quick_sort(arr, 0, 9);
    
49.     for(int i = 0; i<10; i++)
    
50.         cout << arr[i] << "\t";
    
51.     return 0;
    
52. }

复制代码