专栏首页大白技术控的技术自留地桶排序的单链表实现及其变种

桶排序的单链表实现及其变种

《算法导论》中桶排序问题的单链表实现

《算法导论》CLRS 第八章 线性时间排序 8.4 桶排序 桶排序的思想就是把区间[0, 1)划分成n个相同大小的子区间,每一个区间称为桶(bucket)。然后,将n个输入数据分布到各个桶中去。因为输入数均匀且独立均匀分布在[0, 1)上,所以一般不会有很多数落在一个桶中的情况。为得到结果,先对各个桶中的数进行排序,然后按次序把各个桶中的元素列出来即可。 在桶排序算法中,假设输入的是一个含n个元素的数组A,且每个元素满足0≤A[i]<1。另外,还需要一个辅助数组B[0..n-1]来存放链表(桶),并假设可以用某种机制来维护这些表。 BUCKET-SORT(A)

1 n ← length[A]
2 for i ← 1 to n
3     do insert A[i] into list B[⌊n A[i]⌋]
4 for i ← 0 to n - 1
5     do sort list B[i] with insertion sort
6 concatenate the lists B[0], B[1], . . ., B[n - 1] together in order

下图表示出了桶排序作用于有10个数的输入数组上的操作过程。

AC代码:

// 待排序数组arr[1...n]内的元素是随机分布在[0,1)区间内的的浮点数 
#include<iostream>
#define bucket_num 10  // 分配到多少个桶中,可设置 
using namespace std;
struct ListNode
{
    double value;
    ListNode *next;
};

//桶排序主程序
void bucketSort(double* arr, int length)
{
    ListNode key[bucket_num];               // 映射关系: int key <- ElemNum/bucket_num 
    int number = 0;
    ListNode *p, *q;                               //插入节点临时变量
    int counter = 0;
    for(int i = 0; i < bucket_num; i++)
    {
        key[i].value = 0;
        key[i].next = NULL;
    }

    for(int i = 0; i < length; i++)
    {
        ListNode *insert = new ListNode();
        insert->value = arr[i];
        insert->next = NULL;
        number = arr[i] * bucket_num;
        if(key[number].next == NULL)
        {
            key[number].next = insert;
        }
        else
        {
            p = &key[number];
            q = key[number].next;
            while((q != NULL) && (q->value <= arr[i]))
            {
                q = q->next;
                p = p->next;
            }
            insert->next = q;
            p->next = insert;
        }
    }
    for(int i = 0; i < bucket_num; i++)
    {
        p = key[i].next;
        if(p == NULL)
            continue;
        while(p != NULL)
        {
            arr[counter++] = p->value;
            p = p->next;
        }
    }
}

int main()
{
    double arr[] = {0.78, 0.17, 0.39, 0.26, 0.72, 0.34, 0.94, 0.21, 0.12, 0.23};
    int len=sizeof(arr)/sizeof(arr[0]);
    bucketSort(arr, len);
    for(int i = 0; i < len; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

参考:

http://www.cnblogs.com/juventus/archive/2012/06/06/2538834.html

相关链接:

http://www.programset.com/blog/blog/23 (感觉代码不太像 桶排序)

#include<iostream>
#include<list>
#include<algorithm>
using namespace std;
 
void bucketsort(double* a, int n) {
    list<double>* b = new list<double>[n];
    for (int i = 0; i < n; i++) {
        b[int(a[i])].push_back(a[i]);
    }
    for (int i = 0; i < n; i++) {
        b[i].sort();
    }
    for (int i = 0,j=0; i < n; i++) {
        while (b[j].size() < 1)j++;
        a[i] = b[j].front();
        b[j].pop_front();
    }
}
 
int main() {
    double arr[] = {0.1,1.1,2.2,3.5,1.5,2.3,7.5,1.7};
    int n = 8;
    bucketsort(arr, n);
    for (int i = 0; i < 8; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

将2.3改为9.3时,程序会异常而终止...

1 n ← length[A]
2 for i ← 1 to n
3     do insert A[i] into list B[⌊n A[i]⌋]
4 for i ← 0 to n - 1
5     do sort list B[i] with insertion sort
6 concatenate the lists B[0], B[1], . . ., B[n - 1] together in order

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 桶排序(Bucket Sort)的数组实现

    桶排序Bucket Sort从1956年就开始被使用,该算法的基本思想是由E. J. Issac R. C. Singleton提出来。

    Enjoy233
  • C#版 - PAT乙级(Basic Level)真题 之 1013.数素数_牛客网

    在线提交: https://www.nowcoder.com/pat/6/problem/4079 或 PTA(拼题A,原PAT) https://...

    Enjoy233
  • 滴滴2016.09.06校招 在线笔试 - 2道编程题

    一个数组有N个元素,求连续子数组的最大和。例如:[-1,2,1],和最大的连续子数组为[2,1],其和为3。

    Enjoy233
  • 时间复杂度与空间复杂度,看这一篇就够了!

    若存在函数 ,使得当 趋向无穷大时, 的极限值为不等于 0 的常数,则称 是 的同数量级函数,记作 ,称 为算法的渐进时间复杂度,简称 时间复杂度,用大...

    村雨遥
  • 归并排序

    用户6055494
  • 5个数求最值

    输入输入只有一组测试数据,为五个不大于1万的正整数输出输出两个数,第一个为这五个数中的最小值,第二个为这五个数中的最大值,两个数字以空格格开。样例输入

    书童小二
  • 调整数组顺序使奇数位于偶数前面

    输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相...

    用户3003813
  • C语言10大基础算法,学C语言必会源码(珍藏版)

    算法是一个程序和软件的灵魂,作为一名优秀的程序员,只有对一些基础的算法有着全面的掌握,才会在设计程序和编写代码的过程中显得得心应手。本文是近百个C语言算法系列的...

    C语言入门到精通
  • 三个数从小到大排序

    书童小二
  • 一遍文章搞定基数排序-java版

    桶排序的一种,是通过数据的各个位的值,将要排序的元素分配至某些 桶 中,已达到排序的作用

    shengjk1

扫码关注云+社区

领取腾讯云代金券