注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

简约男人

简约,不能简单

 
 
 

日志

 
 
关于我

一个过分渴望被理解的人其实就是一个软弱的人, 勇往直前的力量来自斩钉截铁的决心,不是来自别人的理解.

网易考拉推荐

自创的箱子排序  

2009-10-03 11:30:38|  分类: 算法学习 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

#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;
        }
    }
 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.h

#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.h

#ifndef LIST_DEF_H_
#define LIST_DEF_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中编译成功
 */

/*mylist.c文件包含了此文件,所以mylist.c不可在没有此文件时使用*/

/*******************************************
 *                                         *
 *              警告!!!!               *
 *                                         *
 *******************************************/
/*
 * 警告:请根据自定义的数据类型改写下列函数及宏定义!!!!
 */


/**
 *     为了可扩展使用,下面的结点结构中用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定义为自己定义的结构体等其
 * 它自定义类型。
 *     本链表为单向链表,非常有效。可以用作队列,堆栈
 * 等一些非常有用的数据结构。
**/

 

/*定义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

  评论这张
 
阅读(729)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017