Quick Sort

发表于 | 更新于: | |


the simplest quick sort is like following:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;
int Partition(int * a, int start, int end){
    swap(a[start],a[start+rand()%(end-start+1)]);
    int p = a[start];
    while(start<end){
        while(start<end && a[end] >= p) end--;
        swap(a[start],a[end]);
        while(start<end && a[start]<= p) start++;
        swap(a[start],a[end];)
    }
    return start;
}
void QuickSort(int * a, int start, int end){
     if(end-start>=1){
         int mid = Partition(a,start, end);
         QuickSort(a,start,mid-1);
         QuickSort(a,mid+1,end);
     }
}

But If you want do some optimization in QuickSort, first when the number of elements is small than 10, do insert sort not quick sort. Second, To find the near-like middle element of array, and not use the random one. Third, when the array is already sorted , do not use quick sort. and Reduce the function call. You will the following codes:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<iostream>
using namespace std;
void QuickSort(int *a, int start, int end){
    if(end - start <= 0 ) // or you can throw some exceptions!
       return ;
// if the number of element is less than 8, do insert sort;
    if(end - start<7){
      for(int i = start; i <= end; i++){
         for(int j = i; j > start && a[j] < a[j-1]; j--)
             swap(a[j],a[j-1]);
      }
      return;
    }
// check if the array is sorted.
    bool isSorted = true;
    for(int i = start; i < end; i++){
       if(a[i]>a[i+1])
         isSorted = false;
    }
    if(isSorted)
      return;
// get the near-like middle element, use 3 point middle method.
    int dm = start+(end-start)/2;
    int dl, dh;
    if(end-start<40){
       int d = (end-start+1)/8;
       dl = mid(a, start,start+d,start+2*d);
       dm = mid(a,dm-d,dm,dm+d);
       dh = mid(a,end-2*d,end-d, end);
       dm = mid(a,dl,dm,dh);
    }
// do partition
    swap(a[start],a[dm]);
    int low=start, high = end, p = a[start];
    while(low<high){
        while(low < high && a[high]>= p) high--;
        swap(a[low],a[high]);
        while(low<high && a[low]<= p) low ++;
        swap(a[low],a[high]);
    }
    QuickSort(a,start, low-1);
    QuickSort(a,low+1,end);
}