C++桶排序

2022-07-11 12:47:20

C++ 桶排序

排序原理

数据结构设计:链表可以采用很多种方式实现,通常的方法是动态申请内存建立结点,但是针对这个算法,桶里面的链表结果每次扫描后都不同,就有很多链表的分离和重建。如果使用动态分配内存,则由于指针的使用,安全性低。所以,笔者设计时使用了数组来模拟链表(当然牺牲了部分的空间,但是操作却是简单了很多,稳定性也大大提高了)。共十个桶,所以建立一个一维数组,行向量的下标0—9代表了10个桶,每个行形成的一维数组则是桶的空间。
下面展示一些 。
如果是:2 5 3 4 2
这几个数字,那么:

const a=5;//这里所有数字中最大的数字为其下标int x[a];

平均情况下桶排序以线性时间运行,接下来就来讲解它的算法:
假如有1号2号3号4号四个桶,有1 4 3 2四个数,那么排序(从小到大)从1到2开始:1和1号桶的编号相应,所以1存到1号桶,4和编号4相同,所以存到4号桶,3和编号3一样所以存到2号桶2和编号儿一样所以存到二号桶,然后再从1.2.3.4号桶依次到处所存的数字,可得从小到大排好顺序的数字:1 2 3 4
同样这几个桶,如果是数字1 4 4 2 3 4 2
那么
1>>1
4>>4
4>>4
2>>2
3>>3
4>>4
2>>2
那么1号桶有一个,二号桶有两个,三号通有一个,四号桶有三个
从一号通道四号桶依次到出,结果为:1 2 2 3 4 4 4

代码解析

#include<bits/stdc++.h>

这是这个代码所要用的头文件

#include<bits/stdc++.h>intmain(){return0;}

动手前,先把代码框架写好!

//1.根据数字范围确定数组大小并赋值int x[10001]={0};int a;

首先,用户将输入将要排序的数字(10个,范围:0~10000),所以我们要定义一个变量,和一个数组(空间为10001,int类型)

//2.数据放入对应的桶数组for(int h=0;h<=10-1;h++){
        cin>>a;
        x[a]++;}

接下来接受并储存数字

//3.遍历桶数组,并输出数组的下标for(int i=0;i<=10001-1;i++){for(int j=1;j<=x[i];j++){
            cout<<i<<" ";}}

C++代码

这是总代码

{//1.根据数字范围确定数组大小并赋值int x[10001]={0};int a;//2.数据放入对应的桶数组,并统计for(int h=0;h<=10-1;h++){
        
        cin>>a;
        x[a]++;}//3.遍历桶数组,并输出数组的下标for(int i=0;i<=10001-1;i++){for(int j=1;j<=x[i];j++){
            cout<<i<<" ";}}return0;}


  • 作者:LI_HERU
  • 原文链接:https://blog.csdn.net/weixin_47226648/article/details/107452170
    更新时间:2022-07-11 12:47:20