CIYAWASAY

《Quick Sort》

if p<r

   then q←Partition(A,p,r)
      Quicksort(A,p,q-1)

   Quicksort(A,q+1,r)

x←A[r]
i←p-1
for j←p to r-1
   do if A[j]≦x

      then i←i+1
         exchange A[i]←→A[j]
exchange A[i+1]←→A[r]

return i+1

void quickSort(int[] Array, int p, int r){
   if(p < r){
      int q = partition(Array, p, r);
      quickSort(Array, p, q - 1);
      quickSort(Array, q + 1, r);
   }
}

int partition(int[] Array, int p, int r){
   int x = Array[r];
   int i = p - 1;

   for(int j = p; j <= r - 1; j++){
      if(Array[j] <= x){
         i++;
         int t1 = Array[i]; Array[i] = Array[j];
         Array[j] = t1;
      }
   }
   int t2 = Array[i+1]; Array[i+1] = Array[r]; Array[r] = t2;
   return i + 1;
}

int partition(String[] Array, int p, int r) {
   String x = Array[r].name;
   int i = p - 1;

   for (int j = p; j <= (r - 1); j++) {
      if (Array[j].name.compareTo(x) <= 0) {
         i++;

         String t1 = Array[i].name;
         Array[i].name = Array[j].name;
         Array[j].name = t1;
      }
   }

   String t2 = Array[i + 1].name;
   Array[i + 1].name = Array[r].name;
   Array[r].name = t2;

   return i + 1;
}

void quickSort(String[] Array) {
   quickSort(Array,0,Array.length-1);
}

void quickSort(String[] Array, int p, int r) {
   if (p < r) {
      int q = partition(Array, p, r);
      quickSort(Array, p, q - 1);
      quickSort(Array, q + 1, r);
   }
}

# posted by Unknown @ 08:28