箱子排序

实现

把每个箱子用一个链表实现。在进行节点分配之前，每个箱子都是空的。

基本思想

1.从与排序链表的头部开始，逐个删除节点，并把它放到合适的箱子链表的头部

2.收集并连接每个箱子中的节点，产生有序的链表

两种实现

第一种实现：

只使用一个箱子数组

//range 是分数的范围

void BinSort(Chain<Node>& X,int range)

{//按分数排序

  int len = X.Length();

  Node x;

  Chain<Node> *bin;//bin是所有的箱子

  bin = new Chain<Node> [range + 1];

  //分配到每个箱子中

  for (int i = 1;i<=len;i++)

  {

      X.Delete(1,x);

      bin[x.score].Insert(0,x);

  }

  //从箱子中收集各元素(从后向前收集)

  for (int j = range;j >= 0;j--)

  {

      while (!bin[j].Empty())

      {

          bin[j].Delete(1,x);

          X.Insert(0,x);

      }

  }

  delete [] bin;

}

第二种实现

直接写成Chain的成员函数，使用两个箱子数组，一个指向头，一个指向尾。

template <class T>

void Chain<T>::BinSort(int range)

{//按分数排序

  int b;//箱子索引号

  bottom = new ChainNode<T>* [range +1];

  top = new ChainNode<T> * [range +1];

  for (b=0;b<=range;b++)//初始化

  {

      bottom[b] = 0;

  }

  //把节点分配到各个箱子中

  for (; first;first = first.link)//添加到箱子中

  {

      b = first.data;

      if (bottom[b])//箱子非空

      {

          top[b].link = first;

          top[b] = first;

      }

      else //箱子为空

        bottom[b] = top[b] = first;

  }

  //收集各箱子中的元素

  ChainNode<T> *y =0;//暂存箱子的顶部指针

  for (b=0;b<=range;b++)

  {

      if (bottom[b])//箱子非空

      {

          if(y)//不是第一个非空的箱子

          {

              y.link = bottom[b];

          }

          else//第一个非空的箱子

              first = bottomo[b];

          y = top[b];

      }

  }

  if (y) y.link = 0;

  delete [] top;

  delete [] bottom;

}

巴特西

C++箱子排序

箱子排序

实现

基本思想

两种实现

第一种实现：

第二种实现

最新文章

热门文章