这是主函数
#include<iostream.h>

#include <stdlib.h> 

#include <string> 

#include <time.h> 
#include "mylist.h" 



using namespace std;



//箱子排序

//归并的思想

//如果待排序的数组有n个元素，则创建n个箱子。然后将输入数组
//中的第一个元素放入第一个箱子中。从输入数组中的第二个元素
//开始按顺序搜索输入数组中的元素；如果该元素大于第一个箱子
//中的最后一个元素，则将其放入到第一个箱子的后面。否则放入
//第二个箱子里。之后的所有大于第二个箱子里最后一个元素的元
//素放入第二个箱子里。依次类推，每当新取出的元素小于当前正
//正在使用的箱子里最后一个元素时，将下一个箱子作为当前箱子
//直到所有的元素都放入到箱子里。并记录下最后使用的箱子的次
//次序。最终所有使用了的箱子里的元素都是有序的。
//然后把使用过的箱子归并为一个有序的序列。归并过程可以这样
//首先把前两个箱子中的有序序列归并到第二个箱子里，然后再把
//第二个箱子归并到第三个箱子里。直到把所有箱子里的元素都归
//并到最后使用的一个箱子里。

 


//标记排序的思想


//如果待排序的数组有n个元素，每个元素含有一个可以映射到
//0 - n的属性码。则创建n个箱子，使用链表这种动态申请内存
//的结构可以节省内存。箱子放入有序数组中，箱子数组的顺序
//和输入数组的每一个元素的属性码按顺序对应。然后把输入数
//组中的元素删除到箱子中。或着记录属性码。此时箱子数组中
//有序的存储（标记）了各个不同值的元素。再把箱子中的元素
//按顺序倒回输入数组,或者根据标记的属性码值将输入数组重新
//排序。

//对于输入数组中存储的是复杂结构的情况十分有效。在这种情
//况下即使输入数组中的元素的属性值都是一样的。浪费的内存
//相对于有效使用了的内存是很小的。箱子中应该存储的是输入
//数组的属性值，而不是输入数组，这样能节省内存。

//说他来自于标记排序。是因为这和用一个辅助数组记录输入数
//组中各元素的名次，然后再插入到相应位置是一样的思想。


//箱子排序的效率与箱子的实现方式有很大的关系，不太容易分
//析。此外归并思想比标记思想的算法更具通用性。

//归并思想的实现

//将La中的元素归并到Lb中,前提La，Lb中的元素都是有序的
//且随着下标的增大而变大
int  merger(LIST * La,LIST * Lb)
{
    NODE *pa,*pbf,*pbs;
    pa = La->head;
    pbf = Lb->head;

    //如果La表的第一个元素小于Lb的第一个元素
    //则替换La和Lb的第一个元素。
    //这是因为，若将La中的某节点插入到Lb的第
    //一个元素之前，需要调整Lb的表头指针；若
    //不是插在Lb的第一元素之前，又不需要调整
    //表头指针。这样就不能构造循环。
    //又，不可能使La中的所有元素都插在Lb的表
    //头前。所以就让La的所有节点都插在Lb的表
    //头之后。这样就都不需要调整表头指针。
    //在交换完成后还需要恢复La和Lb的头指针的
    //指向及pa和pbf的指向。
    //替换将间接地引起一个问题。
    //这个问题的原因是：当Lb只有一个元素，而
    //La有多于一个元素，且同时出现La的第一个
    //元素小于Lb的第一个元素和Lb中的第一元素
    //大于La中第一个之后的某个或几个元素时。
    //此时一开始pbs就会指向Lb的空尾。则会执行
    //交换Lb的空尾和pa指向的链表。设置这种交换
    //是为了节省时间的，却有这个问题。
    //这个问题在这里解决会大量增加元素移动的
    //次数。
    //解决之道就是保证Lb中的元素个数多于La中
    //的元素个数。此时Lb中当然就有多于一个元
    //素了。
    if ( first_min(&(pa->data),&(pbf->data)) )
    {
        pbs = pa->next;
        pa->next = pbf->next;
        pbf->next = pbs;
        La->head = pbf;
        Lb->head = pa;
        pa = La->head;
        pbf = Lb->head;
    }

    //让pbs指向Lb中当前判断的节点
    //pbf指向该节点之前使插入更加容易
    pbs = pbf->next;

    //选择La中表头元素的插入位置，并更新La表头的指向
    while (La->size > 0)
    {
        //如果pbs没有到Lb的结尾，则在判断是否应插入到
        //pbs之前。如果pbs到达结尾if里边的判断是无效的

        while ( pbs != Lb->tail && !first_min(&(pa->data),&(pbs->data)) )
        {
            pbf = pbs;
            pbs = pbs->next;
        }

        //如果pbs没有到达结尾，将pa插入到pbs之前
        //更新两链表信息。
        //并使pbs指向pa，因为新加入的元素pa也需要参与比较
        if (pbs != Lb->tail)
        {
            La->head = pa->next;
            pa->next = pbs;
            pbf->next = pa;
            pbs = pa;
            La->size--;
            Lb->size++;
            pa = La->head;

        }

        //如果pbs到达了Lb的结尾，则交换Lb的空尾和pa指向的
        //所有节点。
        else
        {
            La->tail = La->head = Lb->tail;
            Lb->size += La->size;
            La->size = 0;
            pbf->next = pa;
        }
    }
 return 0;
}


void BinSort(int * a, int n)
{

    LIST *bin;
    LIST *tmp_bin,*tmp_bin_f,*tmp_bin_s;
    int i,j=0;

    bin = new LIST[n];

    //初始化各个链表
    for (i = 0; i < n ; i++)
    {
        init_list(&(bin[i]));
    }

    //第一个元素存入第一个箱子
    insert_tail(&(bin[0]),a);

    //逐个元素放入箱子
    for (i = 1; i < n ; i++)
    {
        if (a[i]>=a[i-1])
            insert_tail(&(bin[j]),a+i);
        else
        {
            j++;
            insert_tail(&(bin[j]),a+i);
        }
    }

    //归并所有使用了的箱子
    //保证Lb中的元素个数多于La中的元素个数
    //是为了解决归并函数引起的问题。
    tmp_bin_f  = bin;
    for (i = 1; i <= j; i++)
    {
        tmp_bin_s = bin+i;
        if (get_size(tmp_bin_f) < 2)
        {
            tmp_bin = tmp_bin_f;
            tmp_bin_f = tmp_bin_s;
            tmp_bin_s = tmp_bin;
        }
        merger(tmp_bin_s,tmp_bin_f);
    }

    for (i = 0; i < n ; i++)
    {
        delete_head(tmp_bin_f,a+i);
    }


    for (i = 0; i < n ; i++)
    {
        release_list(&(bin[i]));
    }

    delete [] bin;

}

int main()
{
    const unsigned SIZE = 1000;
    int i;
    int *a = new int[SIZE];
    clock_t start,end;
    srand(time(0));
    for(i = 0;i < SIZE;i++)
        a[i] = rand();
    start = clock();
    BinSort(a,SIZE);
    end = clock();
    cout <<"我们用了 "<< (end -start) <<"个CPU时钟的时间来排序\n"
      <<"下面将输出排序的结果：" <<endl;
    system("pause");

    for (i=0;i<SIZE;i++)
    {
        cout.width(8);
        cout.setf(std::ios::left);
        cout << a[i];
    }
    cout<<endl;
 return 0;
}





这是mylist中的
#ifndef MYLIST_H_
#define MYLIST_H_ 1

/* 
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.
*/

/**
 *作者 tr0217 （尧思齐 齐尧）
 *
 *此文件可以在TC2.0、vc6.0和gcc5.4.3中编译成功
 */

/*此文件文件包含了list_def.h，所以此文件不可在没有list_def.h时使用*/

/*******************************************
 *                                         *
 *              警告！！！！               *
 *                                         *
 *******************************************/

/*
 * 警告：请仔细阅读下面一段话！！！！
 *
 *此文件可以在TC2.0、vc6.0和gcc5.4.3中编译成功
 */

/**
 *     为了可扩展使用，下面的结点结构中用TYPE指定数据
 * 类型，使用时请按照需要在list_def.h中把TYPE定义为合
 * 适的类型，并且提供三个原型如下的函数
 *    void  assign(TYPE * a,const TYPE * b);
 *    int   is_equal(const TYPE * a,const TYPE * b);
 *    void  print_data(const TYPE * b);
 * 第一个用来为TYPE类型的数据赋值，第二个判断两个TYPE
 * 类型的数据是否相等，第三个用来打印(显示)TYPE类型的
 * 数据。
 *     在list_def.h文件中，已经使用把TYPE定义为int类型
 * (#define TYPE int);也按int类型提供了上述三个函数,如
 * 需要其它类型只需做出适当的修改。
 *     特别说明，也可把"TYPE定义为自己定义的结构体等其
 * 它自定义类型。
 *     本链表为单向链表，非常有效。可以用作队列，堆栈
 * 等一些非常有用的数据结构。
**/

 

#include <stdio.h>
#include <stdlib.h>
/*不可缺少的宏定义和函数文件*/
#include "list_def.h"


typedef  struct _NODE
{
    TYPE    data;
    struct _NODE *next;
}NODE;


typedef  struct _LIST
{
    NODE *head, *tail;
    unsigned  size;
}LIST;


/**
 *初始化链表，定义一个链表后必须初始化，
 *警告！一个链表只允许调用一次
 **/
void init_list(LIST *list)
{
    list->tail = list->head = (NODE*)malloc(sizeof(NODE));
    list->head->next = NULL;
    list->size = 0;
}

/*释放链表所占用的资源，在链表使用结束后必须调用*/
void release_list(LIST *list)
{
    NODE *p1,*p2;
    
    p1 = p2 = list->head;
    while(p1->next != NULL)
    {
        p2 = p1->next;
        free(p1);
        p1 = p2;
    }
}

/*为又一次的使用更新链表*/
void update_list(LIST *list)
{
    release_list(list);
    init_list(list);    
}


/*获取链表的长度,可用来测试链表是否为空*/
unsigned get_size(LIST *list)
{
    return list->size;
}

/*显示链表中的元素*/
void print_list(const LIST *list)
{
    NODE *p;
    
    p = list->head;
    while(p != list->tail)
    {
        print_data(&(p->data));
        p = p->next;
    }
}

/*在链表头添加元素*/
void insert_head(LIST *list,const TYPE * data)
{
    NODE *p;
    
    p = (NODE*)malloc(sizeof(NODE));
    assign(&(p->data) ,data);
    p->next = list->head;
    list->head = p;
    list->size++;    
}

/*在链表尾添加元素*/
void insert_tail(LIST *list,const TYPE * data)
{
    NODE *p;
    
    assign(&(list->tail->data) ,data);
    p = (NODE*)malloc(sizeof(NODE));
    list->tail->next = p;
    list->tail = p;
    list->tail->next = NULL;
    list->size++;    
}

/**
 *删除链表头部元素到data中
 *如果删除的元素不需要存储传入NULL即可
 **/
void delete_head(LIST *list,TYPE * data)
{
    NODE *p;

    if(data != NULL)
        assign(data,&(list->head->data));
    p = list->head->next;
    free(list->head);
    list->head = p;
    list->size--; 
}

/**
 *删除链表尾部元素到data中
 *如果删除的元素不需要存储传入NULL即可
 *使用该函数前一定要测试链表是否为空
 *该函数效率不高，且无法优化
 *一定要尽量避免使用该函数
 **/
void delete_tail(LIST *list,TYPE * data)
{
    NODE *p = list->head;
    unsigned i = 1;

    while(i < list->size)
    {
        p = p->next;
        i++;
    }
    free(list->tail);
    list->tail = p;
    if(data != NULL)
        assign(data,&(p->data));
    list->size--; 
}

/**
 *查找某元素是否在链表中，
 *如果在，则返回其指针；位置应从1开始
 *否则返回NULL，本函数同样效率不高，且无法优化
 *由于使用单向链表，只能用顺序查找法，
 *使用该函数应十分小心，将该函数放到等号的左边，
 *即作为左值，可以改变链表中index
 *处的值。如果没有此意图，请注意。
 **/
NODE * find(LIST *list,const TYPE *data)
{
    int flag = 1;
    NODE *p = list->head;

    while(flag||p != list->tail)
    {
        if(is_equal(&(p->data),data))
        {
            flag = 0;            
        }
        else p = p->next;
    }
    
    if(p == list->tail)
        p = NULL;
    return p;
}

/**
 *返回链表中第index个位置处的元素的指针
 *使用该函数应十分小心，将该函数放到等号的左边，
 *即作为左值，可以改变链表中index
 *处的值。如果没有此意图，请注意。
 *i值从1开始，index<= list->size
 **/
TYPE *  get_at(LIST *list,unsigned index)
{
    NODE *p = list->head;
    unsigned i = 1;

    while(i < index)
    {
        p = p->next;
        i++;
    }

    return &(p->data);
}

#endif
这是list_def中的
#ifndef LIST_DEF_H_
#define LIST_DEF_H_ 1
/*定义TYPE为合适的类型*/
#define TYPE  int

/*提供所需的赋值函数*/
inline void assign(TYPE * a,const TYPE * b)
{
    *a = *b;
}

/*提供所需的判断相等函数*/
inline int is_equal(const TYPE * a,const TYPE * b)
{
    if(*a == *b)
        return 1;
    else return 0;
}

/*提供所需的判断相等函数*/
inline int first_max(const TYPE * a,const TYPE * b)
{
    if(*a > *b)
        return 1;
    else return 0;
}

/*提供所需的判断相等函数*/
inline int first_min(const TYPE * a,const TYPE * b)
{
    if(*a < *b)
        return 1;
    else return 0;
}

/*提供所需的打印(显示)函数*/
inline void print_data(const TYPE * b)
{
    printf("%-10d",*b);
}

 

#endif