C語(yǔ)言基本排序算法之桶式排序?qū)嵗?/h1>

 更新時(shí)間：2017年09月27日 10:41:54   作者：liyuxia713  

這篇文章主要介紹了C語(yǔ)言基本排序算法之桶式排序,簡(jiǎn)單說(shuō)明了桶式排序的原理并結(jié)合具體實(shí)例給出了C語(yǔ)言實(shí)現(xiàn)桶式排序算法的具體步驟與相關(guān)操作技巧,需要的朋友可以參考下

本文實(shí)例講述了C語(yǔ)言基本排序算法之桶式排序。分享給大家供大家參考，具體如下：

桶式排序是對(duì)一個(gè)有n個(gè)整型元素的數(shù)組a[n],其中對(duì)任意i，0 <= a[i] <= m的特殊排序算法。

可以對(duì) n==m, n != m分別處理。寫代碼時(shí)需要注意的的是a[i]是訪問(wèn)第i-1個(gè)元素，而非第i個(gè)。

/************************************************************************************/
/* Bucket_Sort.h 桶式排序算法 */
/* 問(wèn)題：對(duì)一個(gè)有n個(gè)整型元素a[0],a[1],…,a[n-1]的數(shù)組排序，其中0 <= a[i] <= m,任意i */
/* 程序：運(yùn)行時(shí)間為O(m+n),輔助空間為O(m) */
/* 當(dāng) n=m 時(shí)特殊處理，運(yùn)行時(shí)間為O(N), 輔助空間為O(1) */
/************************************************************************************/
#include <vector>
/*m != n */
void Bucket_Sort_m(int *a, int n, int m)
{
  std::vector<int> temp(m,0);
  int i;
  for(i = 0; i != n; ++i) //遍歷a[]
    ++temp[a[i]-1]; //如果有對(duì)應(yīng)于下標(biāo)的值，標(biāo)記為1，否則為0
  i = 0;
  for(int j = 1; j <= m; ++j) //遍歷temp向量
    if(temp[j-1]) a[i++] = j;
  temp.clear();
}
/* m == n */
/* 最后的結(jié)果是a[i-1] = i */
void Bucket_Sort(int *a,int n)
{
  for(int i = 1; i <= n; ++i)
  {
    while(a[i-1] != i)
    {
       int temp = a[a[i-1]-1];
       a[a[i-1]-1] = a[i-1];
       a[i-1] = temp;
    }
    /* 偽代碼:如果假設(shè)可以通過(guò)a[i]訪問(wèn)數(shù)組的第i個(gè)元素，而不是第i-1個(gè) */
    /*while(a[i] != i)
    {
       int temp = a[a[i]];
       a[a[i]] = a[i];
       a[i] = temp;
    }
    */
  }
}

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

您可能感興趣的文章:

• 必須知道的C語(yǔ)言八大排序算法(收藏)
• C語(yǔ)言基本排序算法之shell排序?qū)嵗?/a>
• C語(yǔ)言排序算法之冒泡排序?qū)崿F(xiàn)方法【改進(jìn)版】
• C語(yǔ)言基本排序算法之插入排序與直接選擇排序?qū)崿F(xiàn)方法
• C語(yǔ)言 實(shí)現(xiàn)歸并排序算法
• C語(yǔ)言 奇偶排序算法詳解及實(shí)例代碼
• C語(yǔ)言 冒泡排序算法詳解及實(shí)例
• c語(yǔ)言5個(gè)常用的排序算法實(shí)例代碼

• C語(yǔ)言
• 桶式排序

相關(guān)文章

• 

  C++函數(shù)指針詳解

  這篇文章主要介紹了C++函數(shù)指針詳解,通過(guò)文字描述C++函數(shù)指針基礎(chǔ)概念,內(nèi)涵詳細(xì)的代碼實(shí)現(xiàn)和解析,希望對(duì)你能夠有所幫助

  2021-06-06
• 

  深入理解數(shù)組指針與指針數(shù)組的區(qū)別

  本篇文章是對(duì)數(shù)組指針與指針數(shù)組的區(qū)別進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下

  2013-05-05
• 

  QT使用QChart繪制柱狀圖

  在Qt中使用QChart類可以快速繪制一個(gè)圖表出來(lái),比如折線圖、餅圖、柱狀圖等,本文就來(lái)為大家介紹一下如何利用QChart繪制簡(jiǎn)單的柱狀圖吧

  2024-11-11
• 

  C++學(xué)習(xí)之智能指針中的unique_ptr與shared_ptr

  吃獨(dú)食的unique_ptr與樂(lè)于分享的shared_ptr是C++中常見(jiàn)的兩個(gè)智能指針，本文主要為大家介紹了這兩個(gè)指針的使用以及智能指針使用的原因，希望對(duì)大家有所幫助

  2023-05-05
• 

  C++ 實(shí)現(xiàn)靜態(tài)鏈表的簡(jiǎn)單實(shí)例

  這篇文章主要介紹了C++ 實(shí)現(xiàn)靜態(tài)鏈表的簡(jiǎn)單實(shí)例的相關(guān)資料,需要的朋友可以參考下

  2017-06-06
• 

  C++實(shí)現(xiàn)簡(jiǎn)單猜數(shù)字小游戲

  這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)簡(jiǎn)單猜數(shù)字小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

  2022-01-01
• 

  深入HRESULT與Windows Error Codes的區(qū)別詳解

  本篇文章是對(duì)HRESULT與Windows Error Codes的區(qū)別進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下

  2013-05-05
• 

  c語(yǔ)言實(shí)現(xiàn)數(shù)組循環(huán)左移m位

  這篇文章主要介紹了c語(yǔ)言實(shí)現(xiàn)數(shù)組循環(huán)左移m位，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教

  2022-07-07
• 

  c/c++ 利用sscanf進(jìn)行數(shù)據(jù)拆分操作

  這篇文章主要介紹了c/c++ 利用sscanf進(jìn)行數(shù)據(jù)拆分操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧

  2020-12-12
• 

  C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中數(shù)制轉(zhuǎn)換實(shí)例代碼

  這篇文章主要介紹了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中數(shù)制轉(zhuǎn)換實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下

  2017-03-03

最新評(píng)論