我把我发明的排序算法归于箱子排序，或者桶排序。但是与传统的桶排序绝对不一样。
几天前我在一个编程论坛里看到一篇置顶贴，内容是对常见排序算法的分析。我把帖子下了下来，通看了一遍。发现其中所述纰漏颇多。昨天考试完毕，趁有闲时间，接着整理自己的算法代码和解析的知识库。对照多方资料，将冒泡排序 （及其优化版 双向冒泡 逆向冒泡）、标记排序 （使用附加数组版和就地版）、插入排序、选择排序 （及其优化版）、归并排序 （递归与二路归并版）、堆排序  （使用大(小)根堆、最大堆、最小堆版）、希尔排序 （插入式，和其它）、快速排序这些资料整理完毕。
忽然想到另一种排序。这种排序是我在机械工业出版社出版的一本翻译的国外的数据结构与算法的书中了解到的。说句实话翻译的太差，名字就叫“数据结构与算法c++描述”。
从图书馆借来看了不到四分之一，实在看不下去了。因为翻译的逻辑错误太多。看着前面用一种方式把问题理解了，然后看到后面又发现自己的理解矛盾重重，重新回去看。原来翻译的人其实想说的是另一个意思。郁闷，只好浏览一下目录及前言，就把书还了。
这本书里就介绍了一种箱子排序的算法。为了把箱子排序算法整理出来，跑去参阅我已经收藏了的这本书的英文版。
发现此书所述的箱子排序的用武之地实在太少，如果想反驳这句话，请先看这本书。然后就想出了下面的算法，并把原书中所述的箱子排序的概念抽象为“标记排序的思想”。标记排序是我对计数排序和计数后就地插入的统称，我认为它们是一样的。请不要把标记排序当作某一算法的称呼，而到处传播。并且我认为所有已存在的箱子排序思想都是“标记排序的思想”。我能把很多东西看作是一样的。
宋广吉先生把“逆向冒泡”搞成“交换法”并在收录于其所著的书中到处传播。我认为这不是好事，能找出东西之间的共性，就可以触类旁通，就可以少记一些冗余的东西。
等到我的“空间分析”这一科的成绩出来了。我就把我的考试用的一篇“多种插值算法分析”发出来。其内容会让阅读者觉得，图像处理、游戏中的三维建模、地理学方面的地理模型DEM、DTM之间有许多相通的东西，有许多算法可以无改变的用于这三种情形。

记得学数据结构时，上机练习链表。别人把书中的代码抄写下来运行。而我写了个控制台的“密码管理”。拥有“建立用户”，“为用户创建密码”，“查找更新密码库”的功能。当一个用户打开它的密码文件时，他的所有密码存到一个链表中，以便搜索。遇到个小问题，问老师，老师居然说：你是不是在网上下的啊。我心说，你可以这样想，不能这样说。说话是要用想地。而不能像最近吵的很热的一个官员一样。他面对第三方的一个仲裁人员时说出了“你是站在政府这边，还是人民这边”。这就是说话不用脑子的表现，这不是把人民和政府放到了对立的两方，和政府的宣称极大的不一致吗？
说了这么多别的话，现在回到正题。为了防止我发明的算法与别人的撞堆。今天又搜了一下排序。发现那个置顶贴，居然是转帖，却没有说。原创地址是
http://www.matrix67.com/blog/archives/149
题名叫：从零开始学算法：十种排序算法介绍。
个人认为他根本没有介绍到十种算法，因为有些算法我认为是一样的。
查看许多之后，很好，没有撞堆。下面就把代码与分析贴出来。使用了归并的思想，但对大元素排序时远高于归并等其它排序算法，与快速排序不相上下。
因为使用了链表。对简单数组排序时，虽然没有移动元素，但是节点插入时更改指针的次数较多。所以不要把这个算法对简单数组的排序和其它排序算法对简单数组的排序的运行时间相比较。
这个算法使用了我自己写的一个链表，没有封装为类。
为什么要使用自己的链表而不使用STL？
因为STL中的容器的大多数实现都使用了连续的内存，插入删除时不可避免的造成元素移动。此外不可能直接操作容器类中的私有数据。所以即使使用传统的节点方式实现的容器，也不可避免元素的移动。
为什么没有把自己的链表封装为类？
我写过一个链表类。代码还存储在我的机器上。这是我最初学c++时写的，效果虽说不错。仍然有不能操作类中私有数据的限制。那么仍然无法避免移动元素。把排序算法作为类的成员是可以解决的。但是基本的到处都可用的算法封装为类，反而会降低其通用性。
此外我想在此，让那些说我的这个结构化链表没有用处，用STL就可以了的人，了解一下c语言实现的链表的用处。
梯子高，呵呵。

[quote]
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include "mylist.h"

using std::cout;
using std::endl;

//箱子排序

//归并的思想

//如果待排序的数组有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;
        }
    }
}


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) < get_size(tmp_bin_s))
        {
            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 = 30000;
    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时钟的时间来排序" <<endl;
    /*
    for (i=0;i<SIZE;i++)
        cout<<a[i]<<" ";
    cout<<endl;*/
}


[/quote]

我前边已经说清楚了，不要把这个算法对简单数组的排序和其它排序算法对简单数组的排序的运行时间相比较。
顺便说一下，本论坛的编程比赛以执行时间判别算法效率的方式十分不科学。