qsort4.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;
extern long count1;

// Quicksort sort
struct qentry { int left, right; };

void qsort(ELEM* array, int i, int j) {
  int listsize = j-i+1;
  struct qentry Stack[100];
  int top = 0;
  KEY pivot;
  int pivotindex, l, r;

  Stack[top].left = i;
  Stack[top].right =j;

  while (top >= 0) {
    // Pop Stack
    i = Stack[top].left;
    j = Stack[top--].right;

    // Findpivot
    pivotindex = (i+j)/2;
    pivot = array[pivotindex];
    swap(array[pivotindex], array[j]); // Stick pivot at end

    // Partition
    l = i-1;
    r = j;
    do {
      while (key(array[++l]) < pivot);
      while (r && (key(array[--r]) > pivot));
      swap(array[l], array[r]);
    } while (l < r);
    swap(array[l], array[r]);  // Undo final swap
    swap(array[l], array[j]);  // Put pivot value in place

    // Load up Stack
    if ((l-i) > THRESHOLD) {   // Left partition
      Stack[++top].left = i;
      Stack[top].right = l-1;
    }
    if ((j-l) > THRESHOLD) {   // Right partition
      Stack[++top].left = l+1;
      Stack[top].right = j;
    }
  }
  inssort(array, listsize);    // Final Insertion Sort
}

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