基本思想:桶排序将一个区间划分为N个相同大小的子区间,也就是桶。然后将输入数分别放到各个桶中。为了得到输出结果,先对每个桶中的数进行排序,然后遍历每个桶,按照次序把各个桶中的元素列出来即可。


----------
排序算法:桶排序
时   间:2018年1月16日
时间复杂度:O(n + k)
空间复杂度:O(n + k)
稳  定  性:稳定
by Ingran

----------

#include <iostream>
#include <time.h>

typedef struct Bucket_Node
{
    int date;
    struct Bucket_Node *Next;
}Node;

void Free_List(Node *head)
{
    Node *N = head;
    while (head != NULL)
    {
        N = head->Next;
        delete head;
        head = N;
    }
}

void Bucket_Sort(int A[], int len)
{
    Node *Bucket[10] = { 0 };//初始化十个空桶
    Node *temp = NULL, *pre_temp = NULL;
    for (int i = 0; i < len; i++)
    {
        int a = A[i] / 100;
        if (Bucket[a] == 0)//把数据放入空桶中
        {
            Bucket[a] = new Node;
            Bucket[a]->date = A[i];
            Bucket[a]->Next = NULL;
        }
        else                       //对非空链表(非空桶)插入排序
        {
            pre_temp = temp = Bucket[a];
            while (A[i] > temp->date)//比较数组中的元素与桶中元素的大小
            {
                pre_temp = temp;
                temp = temp->Next;
                if (temp == NULL)
                    break;
            }

            if (temp == NULL)//插入到最后的位置
            {
                temp = new Node;
                temp->date = A[i];
                temp->Next = NULL;
                pre_temp->Next = temp;
            }
            else if (temp == Bucket[a])//插入到第一个位置
            {
                temp = new Node;
                temp->date = A[i];
                temp->Next = Bucket[a];
                Bucket[a] = temp;
            }
            else                 //插入到中间
            {
                temp = new Node;
                temp->date = A[i];
                temp->Next = pre_temp->Next;
                pre_temp->Next = temp;
            }
        }
    }

    Node *Input = NULL;
    for (int i = 0; i < 10; i++)
    {
        Input = Bucket[i];
        while (Input != NULL)
        {
            std::cout << Input->date<<"  ";
            Input = Input->Next;
        }
        Free_List(Bucket[i]);
        
    }
}



int main()
{
    int *a = nullptr;
    int n = 0;
    srand((unsigned)time(NULL));
    std::cout << "请输入随机数的个数:" << std::endl;
    std::cin >> n;
    a = new int[n];

    for (int i = 0; i < n; i++)
    {
        a[i] = rand() % 1001;
        std::cout << a[i] << "  ";
    }
    
    std::cout << std::endl;
    Bucket_Sort(a, n);

    system("pause");
    return 0;
}