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;}