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
| template<class Type> void QuickSort3Way(Type a[], int left, int right) { if(left < right) { Type x = a[right];
int i = left - 1, j = right, p = left - 1, q = right; while(1) { while( a[++i] < x ); while( a[--j] > x ) if( j == left ) break; if(i < j) { swap(a[i], a[j]); if(a[i] == x) { p++; swap( a[p], a[i] ); } if(a[j] == x) { q--; swap( a[q], a[j] ); } } else break; } swap(a[i], a[right]); j = i - 1; i = i + 1;
for(int k = left; k <= p; k++, j--) swap( a[k], a[j] ); for(int k = right - 1; k >= q; k--, i++) swap( a[i], a[k] ); QuickSort3Way(a, left, j); QuickSort3Way(a, i, right); } }
int main() { int a[28] = {1,2,5,2,7,4,7,10,65,2,3,63,78,23,61,11,8,34,6,23,23,23,23,23,23,23,23,23}; time_t start, end; start = clock(); QuickSort3Way(a, 0, 28); end = clock(); cout << 1.0 * (end - start)/CLOCKS_PER_SEC << " s " << endl; for(int i = 0;i < 20;i++) cout << a[i] << " "; cout << endl; }
|