算法導論------------桶排序算法之研究

舉個來說明桶排序的過程，假設現在有A={0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.68}，桶排序如下所示：

     研究過計數排序我們知道了————計數排序是假設輸入是由一個小範圍内的整數構成，而桶排序則假設輸入由一個随機過程産生的，該過程将元素均勻而獨立地分布在區間[0，1)上。當桶排序的輸入符合均勻分布時，即可以線性期望時間運作。桶排序的思想是：把區間[0，1)劃分成n個相同大小的子區間，成為桶（bucket），然後将n個輸入數分布到各個桶中去，對各個桶中的數進行排序，然後按照次序把各個桶中的元素列出來即可。

　　數中給出了桶排序的僞代碼，假設輸入是一個含有n個元素的數組A，且每個元素滿足0≤A[i]<1，另外需要一個輔助數組B[0....n-1]來存放連結清單（桶）。僞代碼如下所示：

BUCKET_SORT(A)

   n = length(A)

   for i= 1 to n

       do insert A[i] into list B

   for i=0 to n-1

       do sort list B[i] with insertion sort

   concatenate the list B[0]、B[1]，，，B[n-1] together in order

現在根據僞代碼實作真正的桶排序，這裡使用了c++的方法以及STL中的list以及疊代器的功能。以及在桶中使用了插入排序的算法的來對桶中元素進行排序。

<pre name="code" class="cpp">#include <iostream>
#include <vector>
#include <list>
#include <cstdlib>
using namespace std;

void bucket_sort(float *datas, size_t length)
{
  int i, j;
  int index;
  float fvalue;
  size_t lsize;
  list<float> *retlist = new list<float>[length];
  list<float>::iterator iter;
  list<float>::iterator prioiter, enditer;

  for (i = 0; i<length; ++i)
  {
    index = static_cast<int>(datas[i] * 10);
    //insert a new element
    retlist[index].push_back(datas[i]);
    lsize = retlist[index].size();
    if (lsize > 1)
    {
      //get the last element in the list[index]
      iter = --retlist[index].end();
      fvalue = *iter;
      enditer = retlist[index].begin();
      //insert the last element in right position
      while (iter != enditer)
      {
        //get the second last element in the list[index]
        prioiter = --iter;
        //back up iter to the last element in the list[index]
        iter++;
        //compare two float values
        if (*(prioiter)-*iter > 0.000001)
        {
          float temp = *(prioiter);
          *(prioiter) = *iter;
          *iter = temp;
        }
        iter--;
      }
      //the right inserted position
      *(++iter) = fvalue;
    }
  }
  //copy the result to datas
  j = 0;
  for (int i = 0; i<length; i++)
  {
    for (iter = retlist[i].begin(); iter != retlist[i].end(); ++iter)
      datas[j++] = *iter;a
  }
  delete[] retlist;
}

int main()
{
  float datas[10] = { 0.78f, 0.17f, 0.39f, 0.76f, 0.23f, 0.67f, 0.48f, 0.58f, 0.92f, 0.12f };
  bucket_sort(datas, 10);
  cout << "after bucket_sort the result is:" << endl;
  for (int i = 0; i<10; i++)
    cout << datas[i] << " ";
  cout << endl;
  exit(0);
}