桶排序(Bucket Sort)

在说基数排序之前，先讲一下通排序。

Bucket Sort原理：
如果输入M个数字，这些数字介于0-N(N > 0)之间，在数据输入的时候我们预留了一个大小为数组 Count，称之为桶。

  1. 在输入A的时候对Count[A]进行计数，比如说在这个M个数字中输入了2次25，那么Count[25] = 2。
  2. 遍历Count数组，根据Count[i]的大小输出数字，比如说 Count[1] = 3,那么就输入 1,1,1，如果Count[1] = 0的时候就不输出，整个输出结果就是我们需要的有序数据。
  3. 由于所有数据都需要在桶中占有一个位置（无论存在不存在，不存在该位置计数为0），所以如果我们排序的数字非常大的话，那么需要一个非常大的桶。比如说我们排序的数字最大900000，那么我们就需要一个int[900000]的数组，将会极大的占用内存空间。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    #include <stdio.h>
    //Bucket Sort
    void bucketSort(int *numbers, int length, int max){
        int i;
        int buckets[max + 1];
        for(i = 0; i < max + 1; i++)
            buckets[i] = 0;
        for(i = 0;i < length; i++)
        {
            buckets[numbers[i]]++;        
        }
        int index = 0;
        for(i = 0;i < max + 1; i++)
        {
            int j;
            for(j = 0; j < buckets[i]; j++){
               numbers[index] = i;
               index++; 
            }
        }
    }
    //打印数组
    int printArray(int *array, int length)
    {
        int i;
        for(i = 0; i < length; i++)
            printf("%d ", array[i]);
        printf("\n");
    }
    int main()
    {
        int a[] = {9,1,4,4,8,2,7,10,30,1,19,35,23};
        int length = sizeof(a)/sizeof(int);
        bucketSort(a,length, 35);
        printArray(a, length);
        return 0;
    }

基数排序(Radix Sort)

考虑到Bucket Sort对于内存空间消耗太大，于是我们基于该算法衍生出一种比较优化的算法，即基数排序

  1. 基数排序(Radix Sort)属于分配式排序,又称”桶子法”(Bucket Sort或Bin Sort),将要排序的元素分配到某些”桶”中,以达到排序的作用,基数排序的效率有时候高于其它比较性排序.
  2. 基数排序的方式可以采用LSD（Least sgnificant digital）或MSD（Most sgnificant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好，MSD的方式恰与LSD相反，是由高位数为基底开始进行分配，其他的演算方式则都相同。
  3. 时间复杂度 O(P(N+B)),其中 P是排序趟数，N是要排序的元素个数，B是桶数，一趟分配时间为O(N),一趟收集为O(B),共进行P趟。
  4. 空间复杂度，O(NB) 其中N是要排序的个数，B是桶数

以LSD为，对[209,1,34,4,8,772,7,293,10,30,1,390,19,635,23]进行排序，以10为基数，分为10个桶。

  • 第一躺
    分配
    0：10 30 390
    1：1 1
    2：772
    3：293 23
    4：34 4
    5：635
    6：
    7：7
    8：8
    9：209 19
    收集
    10 30 390 1 1 772 293 23 34 4 635 7 8 209 19
  • 第二趟
  • 入桶
    0：1 1 4 7 8 209
    1：10 19
    2：23
    3：30 34 635
    4：
    5：
    6：
    7：772
    8：
    9：390 293
    出桶
    1 1 4 7 8 209 10 19 23 30 34 635 772 390 293
  • 第三趟
  • 入桶
    0：1 1 4 7 8 10 19 23 30 34
    1：
    2：209 293
    3：390
    4：
    5：
    6：635
    7：772
    8：
    9：
    出桶
    1 1 4 7 8 10 19 23 30 34 293 390 635 772

排序完毕

代码实现

引用

桶式排序与基数排序举例及JAVA代码实现