C++排序算法之桶排序原理及實(shí)現(xiàn)詳解
思想
原理：將數(shù)值作為桶號(hào)，遍歷整個(gè)數(shù)組，將相應(yīng)的桶進(jìn)行計(jì)數(shù)
1、 遍歷原數(shù)組，找到最大值max，然后申請(qǐng)max+1個(gè)空間(桶)，初始化為0(下標(biāo)為0-max)，即 vector<int>bucket(max+1,0)
2、 再次遍歷原數(shù)組，找到每個(gè)數(shù)值對(duì)應(yīng)的桶號(hào)，并對(duì)桶計(jì)數(shù)++，即bucket[vec[i]]++
3、 遍歷桶數(shù)組，看對(duì)應(yīng)的桶內(nèi)計(jì)數(shù)為幾就取出幾下下標(biāo)值(桶號(hào))，放到原數(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];
}
}
//申請(qǐng)max+1個(gè)桶
//int *bucket = new int[max + 1];
//給每個(gè)桶賦初值為0；
//memset(bucket, 0, (max + 1) * sizeof(int));
vector<int>bucket(max + 1, 0);
//遍歷原數(shù)組，把相應(yīng)的數(shù)放到相應(yīng)的桶里
for (int i = 0; i < n; i++)
{
bucket[vec[i]]++;
}
int index = 0;
//從桶里把數(shù)取出來(lái), i代表的數(shù)值對(duì)應(yīng)桶下標(biāo)， bucket[i]代表的是個(gè)數(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í)間復(fù)雜度
- 遍歷數(shù)組找最大值max 時(shí)間復(fù)雜度為O(n)
- 遍歷數(shù)組把對(duì)應(yīng)的數(shù)放入對(duì)應(yīng)的桶時(shí)間復(fù)雜度也為O（n）
- 遍歷桶，從桶中把數(shù)取出來(lái)放入原數(shù)組，假設(shè)有m個(gè)空桶，則時(shí)間復(fù)雜度為O(n+m)
總上所述時(shí)間復(fù)雜度為O(3n+m)=O(n)
空間復(fù)雜度
創(chuàng)建了輔助數(shù)組(桶)，即max+1個(gè)桶，(不管創(chuàng)建多少桶，只要?jiǎng)?chuàng)建了輔助數(shù)組，空間復(fù)雜度就是O(n))
穩(wěn)定性：穩(wěn)定
到此這篇關(guān)于C++排序算法之桶排序原理及實(shí)現(xiàn)詳解的文章就介紹到這了,更多相關(guān)C++桶排序原理及實(shí)現(xiàn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
從 Spring Boot 3+Java 21 到 Spri
本文介紹了從SpringBoot3+Java21升級(jí)到SpringBoot4+Java25的具體步驟與注意事項(xiàng),主要包含環(huán)境與依賴(lài)自查、代碼適配、進(jìn)階優(yōu)化、測(cè)試與驗(yàn)證以及遷移checklist等內(nèi)容,感興趣的朋友跟隨小編一起看看吧2026-04-04
文章主要介紹了Java中字符串操作的兩種常用類(lèi)StringBuilder和StringBuffer,以及三元表達(dá)式的使用和字符串截取的方法2024-12-12
這篇文章主要介紹了springboot泛型封裝開(kāi)發(fā)方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-12-12
Java實(shí)現(xiàn)pdf轉(zhuǎn)圖片案例
這篇文章主要介紹了Java實(shí)現(xiàn)pdf轉(zhuǎn)圖片案例,按照步驟放置代碼,一步步完成該案例,將代碼部署便可,需要的朋友可以參考下2021-06-06
Java?對(duì)象深拷貝工具類(lèi)的實(shí)現(xiàn)
本文主要介紹了Java?對(duì)象深拷貝工具類(lèi)的實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-07-07
SpringBoot中MapStruct實(shí)現(xiàn)優(yōu)雅的數(shù)據(jù)復(fù)制
本文主要介紹了SpringBoot中MapStruct實(shí)現(xiàn)優(yōu)雅的數(shù)據(jù)復(fù)制,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2024-08-08
SpringBoot獲取配置文件中的配置項(xiàng)的常用方式
這篇文章主要介紹了SpringBoot獲取配置文件中的配置項(xiàng)的常用方式,并通過(guò)代碼示例講解的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作有一定的幫助,需要的朋友可以參考下2024-11-11
java中MultipartFile和File最簡(jiǎn)單的互相轉(zhuǎn)換示例
這篇文章主要給大家介紹了關(guān)于java中MultipartFile和File最簡(jiǎn)單的互相轉(zhuǎn)換的相關(guān)資料,MultipartFile和File都是Java中用于處理文件上傳的類(lèi),MultipartFile用于處理上傳的文件,File用于處理本地磁盤(pán)上的文件,需要的朋友可以參考下2023-09-09
Java中接口和抽象類(lèi)的異同以及具體的使用場(chǎng)景
文章主要介紹了Java中接口（Interface）和抽象類(lèi)（AbstractClass）的區(qū)別和聯(lián)系,包括相同點(diǎn)和不同點(diǎn),以及它們?cè)趯?shí)際開(kāi)發(fā)中的具體使用場(chǎng)景,結(jié)合實(shí)例代碼給大家介紹的非常詳細(xì),感興趣的朋友跟隨小編一起看看吧2025-11-11
基于java時(shí)區(qū)轉(zhuǎn)換夏令時(shí)的問(wèn)題及解決方法
下面小編就為大家分享一篇基于java時(shí)區(qū)轉(zhuǎn)換夏令時(shí)的問(wèn)題及解決方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2017-11-11