数据结构(十一)桶排序

左手的ㄟ右手 2022-05-31 04:15 178阅读 0赞

**1、算法流程**

上面的计数排序其实是桶排序的一个特例，当数据的范围是0～n，我们如果划分了n个桶，那么就是计数排序。我们现在假设数据范围是0~1的数，算法流程如下：

(1)划分桶；

(2)把每个数据插入对应的桶中，插入每个桶的时候，用插入排序；

(3)链接所有的不为空的桶排序结果。

**2、代码实现**

//假设数据范围是0~1,我们切分了5个桶
    float * bucket_sort(float *data,int length,int split=4){
        class node{
        public:
            node(){
                next=NULL;
            };
            node(float tvalue){
                next=NULL;
                value=tvalue;
            };
            ~node(){};
            float value;
            node *next;
        };
        struct link{
            node* head;
    
        };
    
    
        link * bucket_link=new link[split];
        for (int i = 0; i <split ; ++i) {
            bucket_link[i].head=NULL;
        }
        //填充每个桶数据，并用插入排序好
        for (int i = 0; i <length ; ++i) {//链表从小到大排序
            node *&head=bucket_link[int(data[i]*split)].head;
            node *p=new node(data[i]);
            if (!head)
                head=p;
            else
            {
                node * point=head;
                node *pre=NULL;
                while (point)
                {
                    if(point->value>p->value)
                        break;
                    pre=point;
                    point=point->next;
                }
                if(pre)
                {
                    node *temp=pre->next;
                    pre->next=p;
                    p->next=temp;
                }
    
                else
                {
                    head=p;
                    p->next=point;
                }
    
               // p->next=point;
            }
        }
    
        //合并桶中数据
        float *sort_result=new float[length];
        int count=0;
    
        for (int i = 0; i <split ; ++i) {
    
            node *head=bucket_link[i].head;
            while (head)
            {
                sort_result[count]=head->value;
                count++;
                node *temp=head;
                head=head->next;
                delete temp;
            }
    
        }
    
        delete[]bucket_link;
    
    
        return sort_result;
    
    
    }
    
    int test_sort() {
    
        float fdata[10]={0.5,0.1,0.6,0.7,0.8,0.4,0.2,0.2,0.10,0.13};
        float*sort_data=bucket_sort(fdata,10);
    
        for(int i=0;i<10;i++)
        {
            std::cout<<sort_data[i]<<std::endl;
        }
        delete[] sort_data;
    
    
        return 0;
    }