radixsort.cpp

本程序实现了基数排序

//RadixSort.cpp
#include "Radixsort.h"



typedef std::stack<unsigned> Stack;
/*****************************************************
Radix sort using STACK as the container
*****************************************************/
static void distribute_s(Stack stacks[], 
                       unsigned* first, unsigned* last,
                       int power)
{
  --first; --last;
  for( ; first < last; --last)
    stacks[(*last/power)%radix].push(*last);
}

void collect_s(unsigned* first, Stack stacks[])
{
  int digit = 0; 
  for(; digit < radix; ++digit)
    while(!stacks[digit].empty())
    {
      *first++ = stacks[digit].top();
      stacks[digit].pop();
    }
}

void radix_sort10_s(unsigned* first, unsigned* last, int d)
{
  Stack stacks[radix];
  int pow;
  //for(pow = 0; pow < radix; ++pow)
   // stacks[pow].clear();

  for(pow = 1; --d >= 0; pow *= radix)
  {
    distribute_s(stacks, first, last, pow);
    collect_s(first, stacks);
  }
}


/*****************************************************
Radix sort using QUEUE as the container
*****************************************************/
typedef std::queue<unsigned> QT;
static void
distribute(QT queues[], T const* first, T const* last, int power)
{
  for(; first != last; ++first)
    queues[(*first / power) % radix].push(*first);
}

static void collect(T* first, QT queues[])
{
  for(int digit = 0; digit < radix; ++digit)
    while(!queues[digit].empty())
    {
      *first++ = queues[digit].front();
      //++first;
      queues[digit].pop();
    }
}

void radix_sort_10(T* first, T* last, int d)
{
  QT queues[radix];
  int pow;
  //for(pow = 0; pow < radix; ++pow)
   // queues[pow].clear();

  for(pow = 1; --d >= 0; pow *= radix)
  {
    distribute(queues, first, last, pow);
    collect(first, queues);
  }
}
/****************************************************
special Node type for radix sort
****************************************************/
struct Node
{
  unsigned value_;
  Node* next_;
  Node(unsigned key, Node* next):value_(key), next_(next){ }
  Node(void){}
};
/****************************************************
special Queue type for radix sort
****************************************************/
struct Queue_
{
  Node* head_;
  Node* rear_;
  Queue_(void){ head_ = new Node; rear_ = head_;}
  ~Queue_(void){ delete head_;}
  void push(Node* me){ rear_ = (rear_->next_ = me);}
  bool empty(void) const { return head_ == rear_;}
  void clear(void){ rear_ = head_;}
};

static void distribute(Queue_ queues[radix], 
                       Node* first, Node* last, 
                       int power)
{
  //for(int i = radix; --i >= 0;)
    //queues[i].clear();
  for(; first != last; first = first->next_)
  {
    queues[(first->value_ / power) % radix].push(first);
  }
}

static Node* collect(Queue_ queues[radix], Node* last)
{
  int end = radix - 1;
  for(; queues[end].empty(); --end)
    ;
  queues[end].rear_->next_ = last;

  int begin = 0;
  for(; queues[begin].empty(); ++begin)
    ;
  last = queues[begin].head_->next_;  //last is the return value
                                      //last is the first node 
  while(begin < end)
  {
    int n = begin + 1;
    for(; queues[n].empty(); ++n)
      ;
    queues[begin].rear_->next_ = queues[n].head_->next_;
    queues[begin].clear();
    begin = n;
  }
  queues[end].clear();
  return last;
}

Node* radix_sort10(Node* first, Node* last, int d)
{
  //last never changed 
  Queue_ queues[radix];
  for(int pow = 1; --d >= 0; pow *= radix)
  {
    distribute(queues, first, last, pow);
    first = collect(queues, last);
  }
  return first;
}


Node* push_front(Node* list, unsigned value)
{
  return new Node(value, list);
}

int size(Node const* list)
{
  int i = 0;
  for(; list!= 0; list = list->next_)
    ++i;
  return i;
}

bool sorted(Node const* list)
{
  if(list == 0) return true;
  Node const* prev = list;
  list = list->next_;
  for( ; list != 0; list = list->next_)
    if(list->value_ < prev->value_)
      return false;
  return true;
}
//~RadixSort.cpp