桶排序(C/C++实现)

2022-07-10 09:17:39

算法精髓

  • 有一个元素均匀分布的原数组。
  • 创建多个临时数组将原数组内的元素按大小分层级装在不同的临时数组中
  • 在几个临时数组中分别排序
  • 将每一个临时数组中的值按大小转入原数组中。

算法实现

#include<iostream>#include<vector>#include<algorithm>usingnamespace std;voidBubble_sort(int arr[],int len){if(len<2)return;for(int i= len-1;i>0;i--)for(int j=0;j< i;j++)if(arr[j]> arr[j+1])swap(arr[j], arr[j+1]);return;}void_Bucket_sort(int arr[],int len){int i;int j;int bucket[5][5]={0};int _buckets_count[5]={0};//桶内元素计数器for(i=0;i< len;i++){//将数组元素装进各桶中
		bucket[arr[i]/10][_buckets_count[arr[i]/10]++]= arr[i];}for( i=0;i<5;i++)//各桶内进行排序Bubble_sort(bucket[i], _buckets_count[i]);int sign=0;//各桶内元素赋值给原数组for( i=0;i<5;i++){for( j=0;j< _buckets_count[i];j++){
			arr[sign++]= bucket[i][j];}}return;}intmain(){int arr[]={21,3,30,44,15,36,6,10,9,19,25,48,5,23,47};int len=sizeof(arr)/sizeof(int);_Bucket_sort(arr, len);for(int i=0;i< len;i++)cout<< arr[i]<<'\t';return0;}

分析
时间复杂度:O(n)(将n各数据装入桶中,当排序算法耗时较多时则时间复杂度由排序算法时间效率决定)
空间复杂度:O(n)

  • 作者:华枝歌
  • 原文链接:https://blog.csdn.net/weixin_45983489/article/details/123830062
    更新时间:2022-07-10 09:17:39