快捷導(dǎo)航

C語言實(shí)現(xiàn)桶排序的方法示例

更新時(shí)間：2018年01月04日 11:39:40 作者：cjc雪狼

這篇文章主要介紹了C語言實(shí)現(xiàn)桶排序的方法,簡(jiǎn)單描述了桶排序的概念、原理并結(jié)合實(shí)例形式分析了C語言實(shí)現(xiàn)桶排序算法的具體操作技巧,需要的朋友可以參考下

本文實(shí)例講述了C語言實(shí)現(xiàn)桶排序的方法。分享給大家供大家參考，具體如下：

一、定義

假定：輸入是由一個(gè)隨機(jī)過程產(chǎn)生的[0, 1)區(qū)間上均勻分布的實(shí)數(shù)。將區(qū)間[0, 1)劃分為n個(gè)大小相等的子區(qū)間（桶），每桶大小1/n：[0, 1/n)， [1/n, 2/n)， [2/n, 3/n)，…，[k/n, (k+1)/n )，…將n個(gè)輸入元素分配到這些桶中，對(duì)桶中元素進(jìn)行排序，然后依次連接桶輸入0 ≤A[1..n] <1輔助數(shù)組B[0..n-1]是一指針數(shù)組，指向桶（鏈表）。

二、性能

對(duì)于N個(gè)待排數(shù)據(jù)，M個(gè)桶，平均每個(gè)桶[N/M]個(gè)數(shù)據(jù)的桶排序平均時(shí)間復(fù)雜度為：

O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)

快排的時(shí)間復(fù)雜度為n*log2(n)

當(dāng)N=M時(shí)，即極限情況下每個(gè)桶只有一個(gè)數(shù)據(jù)時(shí)。桶排序的最好效率能夠達(dá)到O(N)。

桶排序是穩(wěn)定的

三、實(shí)現(xiàn)

/*==============================
8 name:bucket sort
--------------------------------
time complexity:
average
O(n+nlogn-nlogm)
--------------------------------
space complexity:
O(n)
--------------------------------
stability:
unstable
==============================*/
//suppose: 0<data[i]<100
//we should design the project function based on the data distribution
void bucket_sort(std::vector<int> &a)
{
  std::vector<std::vector<int>> bucket;
  bucket.resize(10);
  std::vector<int>::iterator it=a.begin();
  while(it!=a.end())
  {
    int idx=*it/10;
    bucket[idx].push_back(*it);
    it++;
  }
  std::vector<std::vector<int>>::iterator it1=bucket.begin();
  while(it1!=bucket.end())
  {
    simple_sort(*it1);
    it1++;
  }
  it=a.begin();
  it1=bucket.begin();
  while(it!=a.end() && it1!=bucket.end())
  {
    std::vector<int>::iterator tmp_it=(*it1).begin();
    while(tmp_it!=(*it1).end())
    {
      *it=*tmp_it;
      tmp_it++;
      it++;
    }
    it1++;
  }
}

PS：這里再為大家推薦一款關(guān)于排序的演示工具供大家參考：

在線動(dòng)畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過程工具：
http://tools.jb51.net/aideddesign/paixu_ys

希望本文所述對(duì)大家C語言程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: