拍个QuickSort

karpar posted @ 2008年10月14日 09:36 in Algorithm with tags algo quicksort c , 1594 阅读
  1. void Swap(int *a, int *b)
  2. {
  3.     int tmp = *a;
  4.     *a = *b;   
  5.     *b = tmp;   
  6. }
  7.  
  8. int partition(int *a, int p, int r)
  9. {
  10.     int x = a[r];
  11.     int i = p - 1;
  12.     int j = p;
  13.    
  14.     for (; j <= (r - 1); j++)
  15.         if (a[j] < x)
  16.         {
  17.             i++;
  18.             Swap(&a[i], &a[j]);
  19.         }
  20.     Swap(&a[i+1], &a[r]);
  21.     return i+1;
  22. }
  23.    
  24.        
  25. void quickSort(int *a, int p, int r)
  26. {
  27.     if (p < r) {
  28.         int q = partition(a, p, r);
  29.         quickSort(a, p, q - 1);
  30.         quickSort(a, q + 1, r);
  31.     }
  32. }
  33. int main(int argc, char *argv[])
  34. {
  35.     int a[] = {0, 8, 7, 1, 3, 5, 6, 4};
  36.     int sorted[8] = {0,1,3,4,5,6,7,8};
  37.     int ii = 0;
  38.    
  39.     quickSort(a, 2, 7);
  40.     for(; ii < 8; ii++)
  41.         //if(sorted[ii] != a[ii])
  42.             printf("failed in %d\n", a[ii]);
  43.  
  44.     // printf("Success\n");
  45.    
  46. //    int k1 = 3, k2 = 4;
  47. //    int a[2] ={0,1};
  48.    
  49.    
  50.     /* Swap(&a[0], &a[1]);   */
  51.     /* printf("k1=%d, k2=%d", a[0], a[1]); */
  52.    
  53.     return 0;
  54. }
  55.  
  56.  

 

Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter



Host by is-Programmer.com | Power by Chito 1.3.3 beta | Designed by Wink Hosting.