数据结构之排序（一）

前言

一直想着能有机会来写一写自己的对于数据结构的理解，无奈最开始没有认真深入的学习，对于很多知识都是浅尝辄止，所以迟迟没有写一字一句。趁着现在还有些许时间，也顺便为了准备考研，遂重学数据结构以及写写自己的理解和感受，当然很多知识都是借鉴国内外优秀的书籍，在此对写那些书的人提出感谢。关于排序的数据结构与算法目前会写八篇，后续可能会有补充。因为是第一篇，所以有些许啰嗦，后续文章不会存在。关于程序实现部分主要是采用 C 语言实现，由于时间问题，可能会在寒假用 C++/Java 实现。

正文

桶排序

本篇主要讲述桶排序的的原理及程序实现。（这里只是对桶排序进行一个简单的实现，后续在写了链表之后会写的很详细）

论排序算法，单纯的对无符号整型数字进行排序的话，我想桶排序应该是最简单最快速的排序算法了。桶排序的原理有点类似于邮局对于信件的分类，把同一个类型的信件放到对应的邮箱里面。而桶排序则是把相同的数放到对应的存储空间里面。这里的存储空间我们目前采用数组代替。

实现过程：先随机给出一组数 {2，3，5，5，6，6，8，7，9} ，然后定义一个一元数组，这里的对应关系就是数字与数组元素下标相对应。所以在定义数组时数组元素个数的取值要比给定的最大数字大。比如这里最大的数字是 9 ，所以我们定义一个一元数组 a[10] ，先把数组元素全部初始化为 0 ，然后统计数字的个数，如第一个数字为 2，则把下标为 2 的数组元素自增 1，以此类推，等输入完毕后再循环打印数组，数组元素为多少则输出多少个数组元素对应的下标。下面给出这个算法的 C 语言实现过程以及时间复杂度分析。

代码如下：

#include<stdio.h>

int main()
{
    int n,m,k;
    printf("请输入数字个数：");
    scanf("%d",&m);
    printf("请输入数字中最大数：");
    scanf("%d",&n);
    int a[n+1] = {0};//将所有元素初始化为 0 
    printf("请输入数字："); 
    for(int i = 0;i < m;i++)
    {
        scanf("%d",&k);
        a[k]++; 
    }
    for(int i = 0;i < n+1;i++)
    {
        while(a[i] >= 1)
        {
            printf("%2d",i);
            a[i]--;
        }
    }
    return 0;
}

可以分析得出它的时间复杂度为 O（M+N），由此可见桶排序在时间上是很占有优势的，但是它也有很多不足之处，比如，空间浪费太多，不能处理浮点数类型等，总之，每一种算法都有其优势和不足，根据情形合理选择适合的才能优化程序。

这里只是相当于简化版的桶排序，在篇幅以及深度方面可能不足，后续会重新更新。下一篇会写冒泡排序。