C++排序算法之桶排序原理及實現(xiàn)詳解
更新時間：2023年10月30日 10:40:04 作者：大慶指針
這篇文章主要介紹了C++排序算法之桶排序原理及實現(xiàn)詳解, C++ 桶排序是一種線性時間復雜度的排序算法,它通過將待排序元素分配到不同的桶中,然后對每個桶中的元素進行排序,最后將所有桶中的元素按順序合并得到有序序列,需要的朋友可以參考下
思想
原理：將數(shù)值作為桶號，遍歷整個數(shù)組，將相應的桶進行計數(shù)
1、 遍歷原數(shù)組，找到最大值max，然后申請max+1個空間(桶)，初始化為0(下標為0-max)，即 vector<int>bucket(max+1,0)
2、 再次遍歷原數(shù)組，找到每個數(shù)值對應的桶號，并對桶計數(shù)++，即bucket[vec[i]]++
3、 遍歷桶數(shù)組，看對應的桶內(nèi)計數(shù)為幾就取出幾下下標值(桶號)，放到原數(shù)組中。
代碼
#include<iostream>
#include<vector>
using namespace std;
void bucketSort(vector<int>&vec, int n)
{
int max = vec[0];
for (int i = 0; i < n; i++)
{
if (vec[i] > max)
{
max = vec[i];
}
}
//申請max+1個桶
//int *bucket = new int[max + 1];
//給每個桶賦初值為0；
//memset(bucket, 0, (max + 1) * sizeof(int));
vector<int>bucket(max + 1, 0);
//遍歷原數(shù)組，把相應的數(shù)放到相應的桶里
for (int i = 0; i < n; i++)
{
bucket[vec[i]]++;
}
int index = 0;
//從桶里把數(shù)取出來, i代表的數(shù)值對應桶下標， bucket[i]代表的是個數(shù)
for (int i = 0; i < bucket.size(); i++)
{
while (bucket[i] > 0)
{
vec[index++] = i;
bucket[i]--;
}
}
}
int main()
{
vector<int>vec = { 2,3,5,8,9,7,4,6,1 };
bucketSort(vec, vec.size());
for (auto it : vec)
{
cout << it << " ";
}
return 0;
}時間復雜度
- 遍歷數(shù)組找最大值max 時間復雜度為O(n)
- 遍歷數(shù)組把對應的數(shù)放入對應的桶時間復雜度也為O（n）
- 遍歷桶，從桶中把數(shù)取出來放入原數(shù)組，假設有m個空桶，則時間復雜度為O(n+m)
總上所述時間復雜度為O(3n+m)=O(n)
空間復雜度
創(chuàng)建了輔助數(shù)組(桶)，即max+1個桶，(不管創(chuàng)建多少桶，只要創(chuàng)建了輔助數(shù)組，空間復雜度就是O(n))
穩(wěn)定性：穩(wěn)定
到此這篇關于C++排序算法之桶排序原理及實現(xiàn)詳解的文章就介紹到這了,更多相關C++桶排序原理及實現(xiàn)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
本文主要介紹了SpringBoot整合第三方技術的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-02-02
本文主要介紹了Java虛擬機棧jvm棧的作用，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
這篇文章主要介紹了SimpleDateFormat格式化日期問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-06-06
SpringBoot中過濾器Filter+JWT令牌實現(xiàn)登錄驗證
本文主要介紹了SpringBoot中過濾器Filter+JWT令牌實現(xiàn)登錄驗證,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2024-04-04
java system類使用方法示例 獲取系統(tǒng)信息
這篇文章主要介紹了java system類使用方法,該類中的方法都是靜態(tài)的。不能被實例化，沒有對外提供構造函數(shù),該類可以獲取系統(tǒng)信息2014-01-01
這篇文章主要介紹了Java中的JWT使用詳解,JWT是一個開放標準(rfc7519)，它定義了一種緊湊的、自包含的方式，用于在各方之間以JSON對象安全地傳輸信息,需要的朋友可以參考下2023-08-08
任何變成語言中,其實都有淺拷貝和深拷貝的概念,Java 中也不例外,下面這篇文章主要給大家介紹了關于Java中Object類和深淺拷貝的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2023-04-04
今天小編就為大家分享一篇關于判斷List和Map是否相等并合并List中相同的Map，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
JAVA 筆記 ClassLoader.getResourceAsStream() 與 Class.getResourc
這篇文章主要介紹了JAVA 筆記 ClassLoader.getResourceAsStream() 與 Class.getResourceAsStream()的區(qū)別,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-07-07
注解,也叫元數(shù)據(jù),一種代碼級別的說明,它是JDK1.5及以后版本引入的一個特性,與類、接口、枚舉是在同一個層次,本文給大家詳細介紹了SpringBoot如何自定義注解,文中通過代碼講解的非常詳細,需要的朋友可以參考下2024-08-08