---恢复内容开始---
算法说明
珠排序是分布排序的一种。
说实在的，这个排序看起来特别的巧妙，同时也特别好理解，不过不太容易写成代码，哈哈。
这里其实分析的特别好了，我就不画蛇添足啦。 大家看一下这个分析，特别特别简单的。
然后我对于下面的代码做一下描述：
1、找到数组的最大值（20-23行代码）
2、创建珠排序的容器，并且进行初始化（28-34行代码）
3、进行排序（39-44行代码），这里是珠排序的核心，也不太好解释，所以还是举例子啦。
例如排序的数组是int[] arr = { 2, 3, 4, 2, 7, 4, 1, 2, 3, 8 };
那么，通过代码我们发现，第一层循环的是arr数组，第二层循环的其实是arr数组中的值。那么
当i=0;num=2时，有：
j=0时，grid[0][0] = '*';
j=1时，grid[0][1] = '*';
接着
当i=1;num=3时，有：
j=0时，grid[1][0] = '*';
j=1时，grid[1][1] = '*';
j=2时，grid[0][2] = '*';
注意啦，j=0和1时，levelcount[j]都是为1的。 而j=2时，levelcount[j]为0.
继续……
当i=2;num=4时，有：
j=0时，grid[2][0]='*';
j=1时，grid[2][1]='*';
j=2时，grid[1][2] = '*';
j=3时，grid[0][3] = '*'
...
....
.....
以此类推，最终得出最终排序的结果
再次感叹，这种排序真的很巧妙啊。
当然啦，这种排序主要应用于数不大的数组中， 例如学习成绩之类的。
代码
使用的是java
说实在的，代码是从这里copy的。写起来比较蛋疼，所以我就没有写，给这个代码中添加了注释。
package hark.sort.distributionsort;
/*
* 珠排序
*/
public class BeadSort {
public static void main(String[] args) {
BeadSort now = new BeadSort();
int[] arr = { 5, 9, 6, 2, 7, 4, 1, 2, 3, 8 };
System.out.print("Unsorted: ");
now.display1D(arr);
int[] sort = now.beadSort(arr);
System.out.print("Sorted: ");
now.display1D(sort);
}
int[] beadSort(int[] arr) {
// 寻找数组最大值
int max = 0;
for (int i = 0; i < arr.length; i++)
if (arr[i] > max)
max = arr[i];
// 创建空的排序数组
// 即将grid中所有元素设为_
// 将levelcount所有元素设为0
char[][] grid = new char[arr.length][max];
int[] levelcount = new int[max];
for (int i = 0; i < max; i++) {
levelcount[i] = 0;
for (int j = 0; j < arr.length; j++)
grid[j][i] = '_';
}
// 珠排序的核心其实在这段代码，比较巧妙
// 其实大家把值代入试一下就有感觉了
// 注意一下levelcount这个数组，这个数组用来存储多维数组grid中，*的最小索引
for (int i = 0; i < arr.length; i++) {
int num = arr[i];
for (int j = 0; num > 0; j++) {
grid[levelcount[j]++][j] = '*';
num--;
}
}
System.out.println();
display2D(grid);
//在这里对于二维数组进行统计（计算*的数量）。 *的数量，即是当前索引数字的大小
int[] sorted = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
int putt = 0;
for (int j = 0; j < max && grid[arr.length - 1 - i][j] == '*'; j++)
putt++;
sorted[i] = putt;
}
return sorted;
}
void display1D(int[] arr) {
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
void display1D(char[] arr) {
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
void display2D(char[][] arr) {
for (int i = 0; i < arr.length; i++)
display1D(arr[i]);
System.out.println();
}
}
时间复杂度和空间复杂度都是O(n*m) ，n是数组大小，m是最大值大小。 当然啦，m其实是可以省掉的，省掉就是O(n)啦
参考
http://rosettacode.org/wiki/Sorting_algorithms/Bead_sort#Java
http://www.cnblogs.com/kkun/archive/2011/11/23/2260301.html
---恢复内容结束---