当前位置: 首页 > news >正文

做公众号主页面的有哪些网站电商项目策划书

做公众号主页面的有哪些网站,电商项目策划书,怎么在年报网站做简易注销,上海资质代办1. 概述 桶排序(Bucket Sort)又称箱排序,是一种比较常用的排序算法。其算法原理是将数组分到有限数量的桶里,再对每个桶分别排好序(可以是递归使用桶排序,也可以是使用其他排序算法将每个桶分别排好序&…

1. 概述

桶排序(Bucket Sort)又称箱排序,是一种比较常用的排序算法。其算法原理是将数组分到有限数量的桶里,再对每个桶分别排好序(可以是递归使用桶排序,也可以是使用其他排序算法将每个桶分别排好序),最后一次将每个桶中排好序的数输出。

2. 算法详解

桶排序的思想就是把待排序的数尽量均匀地放到各个桶中,再对各个桶进行局部的排序,最后再按序将各个桶中的数输出,即可得到排好序的数。

    首先确定桶的个数。因为桶排序最好是将数据均匀地分散在各个桶中,那么桶的个数最好是应该根据数据的分散情况来确定。首先找出所有数据中的最大值mx和最小值mn;

    根据mx和mn确定每个桶所装的数据的范围 size,有
    size = (mx - mn) / n + 1,n为数据的个数,需要保证至少有一个桶,故而需要加个1;

    求得了size即知道了每个桶所装数据的范围,还需要计算出所需的桶的个数cnt,有
    cnt = (mx - mn) / size + 1,需要保证每个桶至少要能装1个数,故而需要加个1;

    求得了size和cnt后,即可知第一个桶装的数据范围为 [mn, mn + size),第二个桶为 [mn + size, mn + 2 * size),…,以此类推
    因此步骤2中需要再扫描一遍数组,将待排序的各个数放进对应的桶中。

    对各个桶中的数据进行排序,可以使用其他的排序算法排序,例如快速排序;也可以递归使用桶排序进行排序;

    将各个桶中排好序的数据依次输出,最后得到的数据即为最终有序。

例子:待排序的数为:3, 6, 9, 1

1)求得 mx = 9,mn = 1,n = 4
size = (9 - 1) / n + 1 = 3
cnt = (mx - mn) / size + 1 = 3

2)由上面的步骤可知,共3个桶,每个桶能放3个数,第一个桶数的范围为 [1, 4),第二个[4, 7),第三个[7, 10)
扫描一遍待排序的数,将各个数放到其对应的桶中,放完后如下图所示:

3)对各个桶中的数进行排序,得到如下图所示:

4)依次输出各个排好序的桶中的数据,即为:1, 3, 6, 9
可见,最终得到了有序的排列。

3. 时间复杂度和空间复杂度分析

最好时间复杂度 : O(n + k)
其中k为桶的个数。即当数据是均匀分散排列的,那么每个桶分到的数据个数都是一样的,这个步骤需要O(k)的书剑复杂度,在对每个桶进行排序的时候,最好情况下是数据都已经是有序的了,那么最好的排序算法的时间复杂度会是O(n),因此总的时间复杂度是 O(n + k) 。

最坏时间复杂度:O(n^2)
当对每个桶中的数据进行排序的时候,所使用的排序算法,最坏情况下是O(n^2),因此总的最坏情况下的时间复杂度为O(n^2)。

平均时间复杂度:O(n + n²/k + k) <=> O(n)
如果k是根据Θ(n)来获取的,那么平均时间复杂度就是 O(n)。

 4.桶排序误区

1、如果数据分布不均,大量数据集中在少量桶里,桶排序就没有效果。

2、桶排序要时间就省不了空间,要空间就省不了时间,意义不大。

首先桶排序排序的内容是均匀分布的一串数字,不存在数据分布不均的问题。其次桶排序可以在时间和空间之间找一个点,使其满足两者。

5.代码

#include <stdio.h>
#include <stdlib.h>// 桶排序函数
void bucketSort(int arr[], int n) {// 创建桶数组int maxVal = arr[0];for (int i = 1; i < n; i++) {if (arr[i] > maxVal) {maxVal = arr[i];}}int bucket[maxVal + 1];for (int i = 0; i <= maxVal; i++) {bucket[i] = 0;}// 将元素放入桶中for (int i = 0; i < n; i++) {bucket[arr[i]]++;}// 从桶中取出元素并排序int index = 0;for (int i = 0; i <= maxVal; i++) {while (bucket[i] > 0) {arr[index++] = i;bucket[i]--;}}
}// 测试桶排序
int main() {int arr[] = {5, 2, 8, 4, 9, 1, 3, 7, 6};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组:");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");bucketSort(arr, n);printf("排序后数组:");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}
参考文章:桶排序详解-CSDN博客文章浏览阅读2.9k次,点赞19次,收藏30次。本文详细介绍了桶排序的基本原理,如何利用哈希表进行数据分配,以及进阶方法中如何通过区间划分和链表结构进行排序。特别强调了桶排序对数据分布均匀性的依赖和在时间和空间效率上的平衡。https://blog.csdn.net/2302_80297670/article/details/135852102?ops_request_misc=%257B%2522request%255Fid%2522%253A%25226BEB34D7-B27C-41C3-9542-2CA003EEF8BE%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=6BEB34D7-B27C-41C3-9542-2CA003EEF8BE&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-2-135852102-null-null.142^v100^pc_search_result_base6&utm_term=%E6%A1%B6%E6%8E%92%E5%BA%8F&spm=1018.2226.3001.4187
【算法】桶排序(Bucket Sort)详解-CSDN博客文章浏览阅读2.8w次,点赞56次,收藏351次。桶排序_桶排序https://blog.csdn.net/qq_27198345/article/details/126516234?ops_request_misc=%257B%2522request%255Fid%2522%253A%25226BEB34D7-B27C-41C3-9542-2CA003EEF8BE%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=6BEB34D7-B27C-41C3-9542-2CA003EEF8BE&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-126516234-null-null.142^v100^pc_search_result_base6&utm_term=%E6%A1%B6%E6%8E%92%E5%BA%8F

                
 

http://www.hrbkazy.com/news/21643.html

相关文章:

  • 成都网站设计报告书头条权重查询站长工具
  • 做国外网站网站seo网络优化
  • 360做网站经常打骚扰电话seo优化6个实用技巧
  • 武汉做网站小程序哪家公司好制作网页用什么软件
  • 如何做淘宝直播教学视频网站杭州百度快照优化公司
  • 天津b2b网站建设公司哪家好宁波seo关键词培训
  • 电商网站的建设的主要目的seo官网
  • 营销型网站建设教学seo外链工具源码
  • 国家电力安全网站两学一做上海seo优化公司
  • 盘锦做网站价格学营销app哪个更好
  • 国内十大网站建设品牌南昌网站设计
  • H5响应式网站数据百度投诉中心电话24个小时
  • 做音乐网站代码如何在百度发布文章
  • 有人做网站推广吗网站内容优化方法
  • 政府网站建设领导讲话稿百度平台我的订单查询在哪里
  • 长沙做网站最好的公司有哪些军事新闻
  • 常熟网站开发网站免费推广的方法
  • 滨州正规网站建设公司深圳网站seo推广
  • 丽水企业网站建设企业网络营销方案设计
  • 备案个人网站国际新闻最新消息今天军事新闻
  • 一键生成论文的网站seo3的空间构型
  • 南宁网站建设公司哪个好网站软文推广范文
  • php在动态网站开发企业推广托管
  • 安防 光速东莞网站建设百度云搜索引擎入口官网
  • 桂林网站推广互联网营销方法有哪些
  • 足球直播网站开发定制河南网站优化
  • 广州南沙建设和交通局网站做seo推广一年大概的费用
  • 做网站泉州中国新闻社
  • 自己搭建网站怎么搭建seo指的是搜索引擎营销
  • 廊坊企业网站服务互联网品牌营销公司