算法原理系列：木桶排序
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434785
算法原理系列：木桶排序
木桶排序是一种用标记来替代比较操作的排序手段，适用范围较窄，但效率极高，时间复杂度为O(n)O(n)，在生活中，我们也经常能看到一些木桶排序的实际案例，比如扑克牌排序时，我们把它平摊在空间中，这种记录相对位置的排序方法是最直观的木桶排序。
缘由
先来看看，在计算机视角中，如何利用相对位置进行排序操作。给出数据集：
nums = [9,2,1,4,7,8,6]这样的数据集有明显的特点，nums在指定范围内，所以我们可以建立一个map来映射nums的值和相对位置关系。
map
index: 0 1 2 3 4 5 6 7 8 9
value: 0 1 1 0 1 0 1 1 1 1
扫描value中非零元素，得到的排序就是最终的排序结果代码如下：
public static void bucketSortWithNoDuplicate(int[] data){
int n = data.length;
int[] aux = new int[n];
int[] map = new int[4 * n]; //开辟足够大的空间
for (int i = 0; i < n; i++){
map[data[i]]++;
}
for (int i = 0, k = 0; i < 4 * n; i++){
if (map[i] == 0) continue;
aux[k++] = i;
}
//回写
for (int i = 0; i < n; i++){
data[i] = aux[i];
}
}这是最简单的思路，但该排序方法只针对非重复元素的排序，遇到重复元素就不起作用。
如：
nums = 2 5 5 6 8 5 2 6 1 1 6 5
map
index : 0 1 2 3 4 5 6 7 8 9
value : 0 2 2 0 0 4 3 0 1 0
元素1出现的次数为2次
元素2出现的次数为2次
...
做点变形：map[data[i]+1]++;
map
index : 0 1 2 3 4 5 6 7 8 9 10
value : 0 0 2 2 0 0 4 3 0 1 0
累加：
map
index : 0 1 2 3 4 5 6 7 8 9 10
value : 0 0 2 4 4 4 8 11 11 12 0
物理含义：
元素1出现的下标为1
元素2出现的下标为2
...
这样我们就充分利用了map统计的频次，并决定了元素的起始位置在何方。
最终排序时，借助aux数组：
for (int i = 0; i < n; i++){
aux[map[data[i]]++] = data[i];
}
此时，注意map在取映射时并未+1。这就好比在扑克排序时，预先统计了每张排出现的频次是多少，如2出现3次，3出现2次，则预先给2留三个空位，再给3留5个空位，塞满元素后，也就排序完成。
代码如下：
public static void bucketSortWithDuplicate(int[] data){
int n = data.length;
int[] map = new int[11];
int[] aux = new int[n];
//计算出现频率
for (int i = 0; i < n; i++){
map[data[i]+1]++;
}
//预留空位
for (int i = 1; i < map.length; i++){
map[i] = map[i-1] + map[i];
}
//排序
for (int i = 0; i < n; i++){
aux[map[data[i]]++] = data[i];
}
//回写
for (int i = 0; i < n; i++){
data[i] = aux[i];
}
}低位优先排序
在上述基础上，我们可以实现固定位数的radix排序，如：
nums:
791372584
783336045
313758717
165485572
536175826
619392783
231528160
309593813
830298494
219957039
思路：
从右到左依次扫描每一位，用木桶排序，因为在针对高位排序时，上述排序稳定，所以不会影响相对位置，这样当遍历到最后一位时，就自然整体有序。代码如下：
public static void radixSort(long[] data){
int n = data.length;
int exp = 1;
int radix = 10;
long max = data[0];
while (max/exp != 0){
int[] map = new int[11];
long[] aux = new long[n];
for (int i = 0; i < n; i++){
map[(int)(data[i] / exp % 10) + 1]++;
}
for (int i = 1; i < n; i++){
map[i] += map[i-1];
}
for (int i = 0; i < n; i++){
aux[map[(int)(data[i] / exp % 10)]++] = data[i];
}
for (int i = 0; i < n; i++){
data[i] = aux[i];
}
exp *= radix;
}
}针对不同位数的数组排序，低位优先只要明确了数组中最大数的最长位数，同样能达到排序效果。
高位优先排序
再介绍一种高位优先排序，如，给定字符数组：
输入：
she
sells
seashells
by
the
seashore
the
shells
she
sells
are
surely
seashells
高位排序，先按第一个字符进行木桶排序，所以有：
0 : are
----------
1 : by
----------
2 : she
3 : sells
4 : seashells
5 : sea
6 : shore
7 : shells
8 : she
9 : sells
10: surely
11: seashells
----------
12: the
13: the
所以经过一轮木桶排序后，我们只要能够得到分组后的头index和尾index，便能递归的进行排序操作了。
递归，无非就是当首字母相同时，如index(2~11)之间的元素，进行第二轮木桶排序。代码如下：
private static int R = 256;
private static final int M = 0;
private static String[] aux;
private static int charAt(String s, int d){
if (d < s.length()) return s.charAt(d); else return -1;
}
public static void sort(String[] data){
int N = data.length;
aux = new String[N];
sort(data, 0, N - 1, 0);
}
private static void sort(String[] data, int lo, int hi, int d){
if (hi <= lo + M){
insertionSort(data, lo, hi, d);
return;
}
int[] count = new int[R + 2];
for (int i = lo; i <= hi; i++){
count[charAt(data[i], d) + 2] ++;
}
for (int i = 1; i < count.length; i++){
count[i] += count[i-1];
}
for (int i = lo; i <= hi; i++){
aux[count[charAt(data[i], d) + 1] ++] = data[i];
}
for (int i = lo; i <= hi; i++){
data[i] = aux[i - lo];
}
for (int r = 0; r < R; r++){
sort(data,lo + count[r], lo + count[r + 1] - 1, d+1);
}
}
public static void insertionSort(String[] elements, int lo, int hi, int d){
for (int i = lo + 1; i <= hi; i++){
for (int j = i; j > lo && elements[j].charAt(d) < elements[j-1].charAt(d); j--){
swap(elements, j, j-1);
}
}
}
private static void swap(String[] ele, int i, int j){
String tmp = ele[i];
ele[i] = ele[j];
ele[j] = tmp;
}有些细节很有趣，比如在进行每一轮的木桶排序时，count频率计数是+2开始的，主要原因在于，count1这个位置被用来收集字符串末尾的（count-1+2），而在数据分类时，遇到末尾的情况直接把顺序照搬至aux即可。
练习：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.
非负整数，所以我们可以采用基数排序来，对数组进行排序，所需要的时间复杂度为O(n)O(n)
代码如下：
public int maximumGap(int[] nums) {
if (nums.length <= 1)
return 0;
radixSort(nums);
int max = 0;
for (int i = 1; i < nums.length; i++) {
max = Math.max(nums[i] - nums[i - 1], max);
}
return max;
}
private static void radixSort(int[] nums) {
int exp = 1;
int radix = 10;
//最大的一定是位数最长的！
int max = 0;
for (int i = 0; i < nums.length; i++) {
max = Math.max(max, nums[i]);
}
while (max / exp != 0) {
int[] count = new int[radix + 1];
int[] aux = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
count[nums[i] / exp % 10 + 1]++;
}
for (int i = 1; i < count.length; i++){
count[i] += count[i-1];
}
for (int i = 0; i < nums.length; i++){
aux[count[nums[i] / exp % 10]++] = nums[i];
}
for (int i = 0; i < nums.length; i++){
nums[i] = aux[i];
}
exp *= 10;
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年05月31日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录