qsort1.cpp

来自「经典c++程序的实现」· C++ 代码 · 共 36 行

#include "book.h"

typedef int ELEM;
typedef int KEY;
#include "swap.h"
  
// Quicksort sort
extern long count1;

int partition(ELEM* array, int l, int r, KEY pivot) {
  do {                // Move the bounds inward until they meet
    while (key(array[++l]) < pivot); // Move left bound right
    while (r && (key(array[--r]) > pivot)); // Move right bound left
    swap(array[l], array[r]);        // Swap out-of-place values
  } while (l < r);                   // Stop when they cross
  swap(array[l], array[r]);          // Reverse last, wasted swap
  return l;           // Return first position in right partition
}

int findpivot(ELEM* array, int i, int j)  { return (i+j)/2; }

void qsort(ELEM* array, int i, int j) { // Quicksort
  int pivotindex = findpivot(array, i, j);
  swap(array[pivotindex], array[j]);    // Stick pivot at end
  // k will be the first position in the right subarray
  int k = partition(array, i-1, j, key(array[j]));
  swap(array[k], array[j]);             // Put pivot in place
  if ((k-i) > 1) qsort(array, i, k-1);  // Sort left partition
  if ((j-k) > 1) qsort(array, k+1, j);  // Sort right partition
}

void sort(ELEM* array, int listsize) {
  qsort(array, 0, listsize-1);
}