线性时间排序算法-桶排序

vlambda
2021-05-06

线性时间排序算法-桶排序

桶排序有个条件是输入数据要服从均匀分布. 均匀分布为何物? 均匀分布分为连续型均匀分布与离散型均匀分布.

连续型均匀分布

如果连续型随机变量X满足概率密度函数为

线性时间排序算法-桶排序

则称X在[a, b]上服从连续均匀分布.图像为:

线性时间排序算法-桶排序

离散型均匀分布

离散型均匀分布是离散型概率分布，其中有限个数值拥有相同的概率。离散型均匀分布的另一种说法为“有限个结果，各结果的概率均相同”。例如均匀的骰子就是离散型均匀分布的例子，可能的值为1, 2, 3, 4, 5, 6，而每一个数字的概率都是1/6。图像为:

线性时间排序算法-桶排序

如果还是不懂, 请把小筑之前的数理统计2章内容搞定.咱们接着说桶排序

排序过程

桶排序是假设输入是由一个随机过程产生, 该过程将元素均匀、独立分布在[0,1)区间上. 将[0, 1)区间划分为n个相同大小的子区间, 我们就称为桶. 然后将n个输入数分别放在各个桶中. 因为输入数据是均匀、独立地分布在[0, 1)区间上, 所以一般情况不会出现很多数落在同一个桶中的情况. 然后我们对每个桶中的数进行排序, 最后遍历每个桶, 把每个桶中元素遍历出来即可. 桶排序原理看图:

线性时间排序算法-桶排序

Python代码

# coding=utf-8import mathfrom insert_sort import insert_sort # 这里引用了之前的插入排序

def Bucket_Sort(A): """ 桶排序 """ n = len(A) B = [[] for _ in range(0, n)] # 这就是桶 for i in range(0, n): B[math.floor(n*A[i])].append(A[i]) C = [j for i in range(0, n) for j in insert_sort(B[i])] return C

if __name__ == '__main__':    import numpy # 这里导入numpy生成均匀分布 random_list = list(map(lambda x: round(x, 2), numpy.random.uniform(0, 1, 10))) print(Bucket_Sort(random_list))

C语言版

#include <stdio.h>#include <stdlib.h>#include "func_sort.h"
//定义一个链表, 负责存储桶中的元素typedef struct node{ float ele; struct node* next;} Node;

void Bucket_Sort(float* A, int size, int bucket_size){  //分配桶空间大小, 就是个二维数组只不过用二级指针表示 Node** bucket = (Node**)malloc(bucket_size * sizeof(Node*)); for (int i = 0; i < bucket_size; ++i) {    //为桶中每个链表分配的空间 bucket[i] = (Node*)malloc(sizeof(Node)); if (bucket[i] != NULL) { //初始化桶中元素 bucket[i]->ele = 0; bucket[i]->next = NULL; } else { return; } }
 for (int i = 0; i < size; ++i) {    //分配要放入桶中结点空间 Node* node = (Node*)malloc(sizeof(node)); if (node != NULL) { //将数组的元素放入桶中 node->ele = A[i]; node->next = NULL; } else { return; } //这就是hash函数,可以分配到指定的桶索引 int index = 10 * A[i];
 Node* p = bucket[index]; if (p->ele == 0) { //如果桶是空的则插入 bucket[index]->next = node; } else {      //若不空则一个一个找，插到比node元素大的前面，就是插入排序 while ((p->next != NULL) && (p->next->ele <= node->ele)) p = p->next; node->next = p->next; p->next = node; } //桶元素数量加1 (bucket[index]->ele)++; } //打印排好序的数据 for (int i = 0; i < bucket_size; ++i) { for (Node* k = bucket[i]->next; k != NULL; k = k->next) { printf("%.2f ", k->ele); } } printf("\n");  //释放内存  free(bucket);}
//main.c#include <stdio.h>#include "func_sort.h"

int main(){ float A[] = { 0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68 }; int size = sizeof(A) / sizeof(float); Bucket_Sort(A, size, 10); return 0;}
//func_sort.h#include<stdio.h>void insert_sort(int* a, int n);void Bucket_Sort(float* r, int size, int bucket_size);

桶排序C语言版用到了链表的数据结构, 链表的插入删除等操作以后咱们再聊. 代码每步已经注释好了, 有点基础都应该可以看懂.

总结

对于桶排序来说即使数据不是均匀分布的. 也可以在线性时间完成. 只要满足桶的大小的平方和与总的元素呈线性关系即可. 咱们今天就到这里.

如果喜欢本文请关注:

算法小筑

介绍计算机算法， C/C++及Python, 英语等等.

63篇原创内容

Official Account

vlambda博客
学习文章列表