qsort2.cpp

经典c++程序的实现

#include <iostream.h>
#include "book.h"

typedef int ELEM;
typedef int KEY;
#include "swap.h"
  
void inssort(ELEM* array, int n) { // Insertion Sort
  for (int i=1; i<n; i++)          // Insert i'th record
    for (int j=i; (j>0) && (key(array[j])<key(array[j-1])); j--)
      swap(array[j], array[j-1]);
}

// Quicksort sort

extern int THRESHOLD;

// 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) {
  if (j <= i) return;  // Don't sort 0 or 1 elements
  int pivotindex = findpivot(array, i, j);
  swap(array[pivotindex], array[j]); // stick pivot at end
  int k = partition(array, i-1, j, key(array[j]));
  swap(array[k], array[j]);  // Put pivot value in place
  if ((k-i) >= THRESHOLD) qsort(array, i, k-1);
  if ((j-k) >= THRESHOLD) qsort(array, k+1, j);
}

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