【七类排序】之第四种：快速排序

用 while(1)，可減少多次判斷 i==j 的情況

1. 
   
2. void quickSort(int a[],int n)
   
3. {
   
4.    int key;
   
5.    int i,j;
   
6. 
   
7.    if(n<=1) return;
   
8. 
   
9.    key=a[n-1];
   
10.    i=0;
    
11.    j=n-1;
    
12.    while(1) {
    
13.       for(; i<j && a[i]<=key ; i++);
    
14. 
    
15.       if(i==j) break;
    
16. 
    
17.       a[j]=a[i];
    
18.        j--;
    
19. 
    
20.       for(; i<j && a[j]>key ; j--);
    
21. 
    
22.       if(i==j) break;
    
23. 
    
24.       a[i]=a[j];
    
25.       i++;
    
26. 
    
27.    }
    
28. 
    
29.    a[i]=key;
    
30. 
    
31.    quickSort(a,i);
    
32.    quickSort(&a[i+1],n-1-i);
    
33. 
    
34. }
    

复制代码

public static void swap (int A[], int x, int y)
   {
      int temp = A[x];
      A[x] = A[y];
      A[y] = temp;
   }

   // Reorganizes the given list so all elements less than the first are
   // before it and all greater elements are after it.                  
   public static int partition(int A[], int f, int l)
   {
      int pivot = A[f];
      while (f < l)
      {
         if (A[f] == pivot || A[l] == pivot)
         {
            System.out.println("Only distinct integers allowed - C321");
            System.out.println("students should ignore this if statement");
            System.out.exit(0);
         }
         while (A[f] < pivot) f++;
         while (A[l] > pivot) l--;
         swap (A, f, l);
      }
      return f;
   }

   public static void Quicksort(int A[], int f, int l)
   {
      if (f >= l) return;
      int pivot_index = partition(A, f, l);
      Quicksort(A, f, pivot_index);
      Quicksort(A, pivot_index+1, l);
   }

gy21 发表于 2013-2-21 09:08
public static void swap (int A[], int x, int y)
   {
      int temp = A[x];

i am also from UW...