|
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 69 70 |
#include <stdio.h> int getPivot(int a, int b, int c) { if(a > b){ if(b > c){ return b; }else{ return a > c ? c : a; } }else{ if(a > c){ return a; }else{ return b > c ? c : b; } } } void swap(int* a, int l, int r) { int t = a[l]; a[l] = a[r]; a[r] = t; } void dispArrayInt(int* a, int len) { for(int i=0; i<len; i++){ printf("%d ", a[i]); } printf("\n"); } void quicksort_core(int* a, int len, int left, int right) { if(right <= left) { return; } int l = left; int r = right; int p = getPivot(a[l], a[l+1], a[r]); while(1){ while(a[l] < p){ l++; } while(p < a[r]){ r--; } if(r <= l){ break; } swap(a, l, r); l++; r--; } quicksort_core(a, len, left, l-1); quicksort_core(a, len, r+1, right); } void quicksort(int* a, int len) { int left = 0; int right = len - 1; quicksort_core(a, len, left, right); } int main(void) { int len = 10; int a[] = {9,8,7,6,5,4,3,2,1,0}; dispArrayInt(a, len); quicksort(a, len); dispArrayInt(a, len); } |
