radix1.cpp

数据结构中排序的实例分析

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

typedef int ELEM;
extern int BITS;

int POW2[9] = {1, 2, 4, 8, 16, 32, 64, 128, 256};

#define pow2(X) POW2[X]
#define COUNTSIZE 256

ELEM count[COUNTSIZE];

void radix(ELEM* A, ELEM* B, int n, int k, int r, ELEM* count) {
  // Count[i] stores number of records in bin[i]

  for (int i=0, rtok=1; i<k; i++, rtok*=r) { // For k digits
    for (int j=0; j<r; j++) count[j] = 0;    // Initialize count

    // Count the number of records for each bin on this pass
    for (j=0; j<n; j++) count[(key(A[j])/rtok)%r]++;

    // Index B: count[j] will be index for last slot of bin j.
    for (j=1; j<r; j++) count[j] = count[j-1] + count[j];

    // Put records into bins working from bottom of each bin.
    // Since bins fill from bottom, j counts downwards
    for (j=n-1; j>=0; j--) B[--count[(key(A[j])/rtok)%r]] = A[j];

    for (j=0; j<n; j++) A[j] = B[j];         // Copy B back to A
  }
}

void sort(ELEM* array, ELEM* temp, int listsize) {
//cout << "radix: k = " << 16/BITS << ", r = " << ipow(BITS) << "\n";
  radix(array, temp, listsize, 16/BITS, pow2(BITS), count);
}