BeadSort重力排序
最近在看好玩的算法, 重力排序是一个根据重力(Gravity)原理的自动排序, 这个排序是自然排序的一种, 非人为操作便可实现. 这种排序非常适合给小孩子解释排序的原理和自然需求.
上面这个图就是重力排序, 首先找出最大的数, 上图中是4, 然后设为m, 就是有m个pole(杆子), 这图就是4个杆子. 然后横着看, 每个row就是当前数字有几便有几个球. 比如row 1 (ary[0] = 2) 是2, 就是两个珠子.
然后让数字随着重力下落即可排序, 具体证明和复杂度wiki有. https://en.wikipedia.org/wiki/Bead_sort 可以看出这种排序用机械实现还可以, 用算法实现效率并不好.
|
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 42 43 44 45 46 47 48 49 50 51 52 53 |
#include <stdio.h> #include <iostream> #include <string.h> using namespace std; #define BEAD(i, j) beads[i*max + j] void beadsort(int *a, int len) { int max = a[0]; for(int i = 1; i < len; i++) { if(a[i] > max) { max = a[i]; } } unsigned int beads[max * len]; //positive int only memset(beads, 0, sizeof(beads)); for (int i = 0; i < len; i++) { for(int j = 0; j < a[i]; j++) { BEAD(i, j) = 1; } } for(int j = 0; j < max; j++) { int sum = 0; for (int i = 0; i < len; i++) { sum += BEAD(i, j);// count the beads BEAD(i, j) = 0; // clear the post } for (int i = len - sum; i < len; i++) { BEAD(i, j) = 1; // gravity down } } for (int i = 0; i < len; i++) { int j; for (j = 0; j < max && BEAD(i, j); j++); // j < max and BEAD(i, j) != null a[i] = j; } } |
上面是一个实现, 具体来说, 最难的地方在于如何实现珠子下落
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
for(int j = 0; j < max; j++) { int sum = 0; for (int i = 0; i < len; i++) { sum += BEAD(i, j);// count the beads BEAD(i, j) = 0; // clear the post } for (int i = len - sum; i < len; i++) { BEAD(i, j) = 1; // gravity down } } |
代码首先计算一个pole上有几个珠子, 然后计算有几个空位, 把空位补上珠子,就是下落后的个数.
最后这个算法的弱点是只能sort正整数, 而且如果数字很离散, 那么效率就太低了