桶排序

综述

桶排序是计数排序的升级版.它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定.
桶排序 (Bucket sort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排).

算法描述

1.设置一个定量的数组当作空桶;
2.遍历输入数据,并且把数据一个一个放到对应的桶里去;
3.对每个不是空的桶进行排序;
4.从不是空的桶里把排好序的数据拼接起来.

示意图

桶排序静态示意图

性质

排序类别:非交换排序
是否是稳定排序:稳定
是否是原地排序:否
时间复杂度:O(N^2)
空间复杂度:O(N+K)

---

Python实现

def bucket_sort1(array):
    buckets = [0] * ((max(array) - min(array)) + 1)
    for i in range(len(array)):
        buckets[array[i] - min(array)] += 1
    res = []
    for i in range(len(buckets)):
        if buckets[i] != 0:
            res += [i + min(array)] * buckets[i]
    return res


dest = [5, 2, 7, 4, 8, 1, 6, 3]
result = bucket_sort1(dest)
print('最后的结果是:', result)

'''
最后的结果是: [1, 2, 3, 4, 5, 6, 7, 8]
'''


# 只是针对正整数
def bucket_sort2(array):
    if not array:
        return False
    max_len = max(array) + 1
    book = [0 for x in range(0, max_len)]
    for i in array:
        book[i] += 1
    return [i for i in range(0, max_len) for j in range(0, book[i])]


dest = [5, 2, 7, 4, 8, 1, 6, 3]
result = bucket_sort2(dest)
print('最后的结果是:', result)

'''
最后的结果是: [1, 2, 3, 4, 5, 6, 7, 8]
'''


# 可对负数排序
def bucket_sort3(array):
    if not array:
        return False
    offset = min(array)
    max_len = max(array) - offset + 1
    book = [0 for x in range(0, max_len)]
    for i in array:
        book[i - offset] += 1
    return [i + offset for i in range(0, max_len) for j in range(0, book[i])]


# 可对小数排序
def bucket_sort4(array):
    if not array:
        return False
    # 保留两位小数
    accuracy = 100.
    offset = int(min(array) * accuracy)
    max_len = int(max(array) * accuracy - offset + 1)
    book = [0 for x in range(0, max_len)]
    for i in array:
        book[int(i * accuracy - offset)] += 1
    return [(i + offset) / accuracy for i in range(0, max_len) for j in range(0, book[i])]

C语言实现

#include<stdio.h>
#include<stdlib.h>
#include<string.h>


/*
*桶排序，时间复杂度为O(n),但是她具有极大的限制，必须已知数组arr在[0,MAX]；
求数组的最大值
*
*/
int get_max(int *arr,int length)
{
    int max = 0;
    for(int i = 1; i < length; i++)
        if(arr[i] > arr[max])
            max = i;
    return arr[max];
}

/*
*建立一个MAX大小的数组，原数组的值作当前数组的下标
*/
void bucket_sort(int *arr,int length)
{
    int max = get_max(arr,length);
    int *buckets = (int *)malloc(sizeof(int) *max);
    if(buckets == NULL) return;
    memset(buckets,0,sizeof(int)*max);
    int i=0, j=0;
    for(i = 0; i < length; i++)
        buckets[arr[i++]]++;
    for(i = 0,j = 0; i < max; ++i)
        while(buckets[i]--)
            arr[j++] = i;
}


void print_array(int *arr, int len)
{
    for(int i=0;i<len;i++)
        printf("%d ", arr[i]);
    printf("\n");
}


int main()
{
    int a[] = {5, 2, 7, 4, 8, 1, 6, 3};
    bucket_sort(a, 8);
    print_array(a, 8);
    return 0;
}