# 算法原理系列：木桶排序

## 缘由

`nums = [9,2,1,4,7,8,6]`

```map
index: 0 1 2 3 4 5 6 7 8 9
value: 0 1 1 0 1 0 1 1 1 1

```    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

...

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

...

for (int i = 0; i < n; i++){
aux[map[data[i]]++] = data[i];
}

```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];
}
}```

## 低位优先排序

```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

```    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;
}```

## 练习：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.

```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;
}
}```

0 条评论

• ### 挑战程序竞赛系列（21）：3.2反转

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 挑战程序竞赛系列（32）：4.5 A*与IDA*

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 挑战程序竞赛系列（36）：3.3线段树和平方分割

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### LeetCode第五天

leetcode 第五天 2018年1月6日 22.(566) Reshape the Matrix ? ? JAVA class Solution { ...

• ### LeetCode 215. Kth Largest Element in an Array分析

显然最简单的思想就是排序，然后取出倒数第k个元素就可以了，我们可以直接调用内部的排序函数。

• ### P3809 【模版】后缀排序

题目背景 这是一道模版题。 题目描述 读入一个长度为 nn 的由大小写英文字母或数字组成的字符串，请把这个字符串的所有非空后缀按字典序从小到大排序，然后按顺序输...

• ### 高仿京东金融的数值滚动尺

以前博客讲的大部分都是静态的自定义View的编写,其实无非就是“画画”画出一个好看的效果,而这篇博客写的是写一个动态的自定义控价,这里不仅需要"画",还要各种事...

• ### 位操作运算有什么奇技淫巧?(附源码)

比如说16位二进制数A：1001 1001 1001 1000，如果来你想获A的哪一位的值,就把数字B：0000 0000 0000 0000的那一位设置为1.