LeetCode 164 Maximum Gap 桶排序与基数排序

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

先看题，简单地说就是给一个未排序的数组，排一下续，然后算出相邻2个数的最大值。

熟悉我的人都知道，我就是个懒蛋，于是就有了下面的代码：

public int maximumGap(int[] nums) {
    if (nums==null||nums.length<2)
        return 0;
    Arrays.sort(nums);
    int max = 0;
    for (int i = 0; i < nums.length-1 ; i++)
        max = Math.max(max, Math.abs(nums[i + 1] - nums[i]));
    return max;
}

虽然过了 仔细一看题目啊 不对啊 要求线性的时间复杂度和空间复杂度啊。

妥妥的桶排序，或者基数排序啊。

桶排序是什么意思呢？

就是准备n个桶，两个桶的间距是固定的，然后把要排序的数按照顺序先扔到特定桶里，

在桶内再使用别的方法排序或者递归排序。

简单的说{1,4,3,5,2,6,9,8,7,10},假如有5个桶，每个桶间距是2，那么首先把数字扔到桶里

1号桶[1,3) :1,2

2号桶[3,5) :4,3
3号桶[5,7) :5,6
4号桶[7,9) :8,7
5号桶[9,11):9,10

桶内排序之后：
1号桶[1,3) :1,2
2号桶[3,5) :3,4
3号桶[5,7) :5,6
4号桶[7,9) :7,8
5号桶[9,11):9,10

在把每个桶里面的数字按照顺序顺次连接起来，这样排序就完成了。
那么，问题来了，谁来决定有多少个桶，和桶的范围呢？
其实是由数组内最大值，最小值，和数组长度决定的，
令 数组中最大值=max，最小值=min，数组长度=len
则 桶的范围 bucketRange = int((max - min - 1) / (len - 1)) + 1

   桶的个数 bucketLen = (max - min) / bucketRange + 1



为啥 这样呢？ 微积分和离散数学自己算去。



至于基数排序，就是10个桶，按照数位依次排序，可以从低位向高位（LSD），

也可以从高位向低位排序（MSD）

百度这个例子已经给的很好了，而且附有代码，直接复制粘贴过来

原链接：百度-基数排序



第一步


以LSD为例，假设原来有一串数值如下所示：

73, 22, 93, 43, 55, 14, 28, 65, 39, 81

首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：

0

1 81

2 22

3 73 93 43

4 14

5 55 65

6

7

8 28

9 39




第二步


接下来将这些桶子中的数值重新串接起来，成为以下的数列：

81, 22, 73, 93, 43, 14, 55, 65, 28, 39

接着再进行一次分配，这次是根据十位数来分配：

0

1 14

2 22 28

3 39

4 43

5 55

6 65

7 73

8 81

9 93




第三步


接下来将这些桶子中的数值重新串接起来，成为以下的数列：

14, 22, 28, 39, 43, 55, 65, 73, 81, 93

这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。


第一步


以LSD为例，假设原来有一串数值如下所示：

73, 22, 93, 43, 55, 14, 28, 65, 39, 81

首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：

0

1 81

2 22

3 73 93 43

4 14

5 55 65

6

7

8 28

9 39




第二步


接下来将这些桶子中的数值重新串接起来，成为以下的数列：

81, 22, 73, 93, 43, 14, 55, 65, 28, 39

接着再进行一次分配，这次是根据十位数来分配：

0

1 14

2 22 28

3 39

4 43

5 55

6 65

7 73

8 81

9 93




第三步


接下来将这些桶子中的数值重新串接起来，成为以下的数列：

14, 22, 28, 39, 43, 55, 65, 73, 81, 93

这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。

LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。













LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。

相对于nlgn的直接排序算法，如果数量级过大，使用桶排序或者基数排序这两种现行排序，还是很有必要的。