5.9 Radix Sort

经典排序算法 - 基数排序 Radix sort，原理类似桶排序，这里总是需要10个桶，多次使用，首先以个位数的值进行装桶，即个位数为1则放入1号桶，为9则放入9号桶，暂时忽视十位数。

示例

待排序数组 [62,14,59,88,16] 简单点五个数字

分配10个桶，桶编号为 0-9，以个位数数字为桶编号依次入桶，变成下边这样

| 0 | 0 | 62 | 0 | 14 | 0 | 16 | 0 | 88 | 59 |
| 0 | 1 | 2  | 3 | 4  | 5 | 6  | 7 | 8  | 9  |

将桶里的数字顺序取出来，输出结果

[62,14,16,88,59]

再次入桶，不过这次以十位数的数字为准，进入相应的桶,变成下边这样，由于前边做了个位数的排序，所以当十位数相等时，个位数字是由小到大的顺序入桶的，就是说入完桶还是有序

| 0 | 14 | 16 | 0 | 0 | 0 | 59 | 62 | 0 | 88 |
| 0 | 1  | 2  | 3 | 4 | 5 | 6  | 7  | 8 | 9  |

因为没有大过100的数字，没有百位数，所以到这排序完毕，顺序取出即可，最后输出结果

[14,16,59,62,88]

文章引用自：http://www.cnblogs.com/kkun/archive/2011/11/23/2260275.html

代码仅供参考

/// <summary>
/// 基数排序
/// 约定:待排数字中没有0,如果某桶内数字为0则表示该桶未被使用,输出时跳过即可
/// </summary>
/// <param name="unsorted">待排数组</param>
/// <param name="array_x">桶数组第一维长度</param>
/// <param name="array_y">桶数组第二维长度</param>
static void radix_sort(int[] unsorted, int array_x = 10, int array_y = 100){
  for (int i = 0; i < array_x/* 最大数字不超过999999999...(array_x个9) */; i++){
    int[,] bucket = new int[array_x, array_y];
    foreach (var item in unsorted){
      int temp = (item / (int)Math.Pow(10, i)) % 10;
      for (int l = 0; l < array_y; l++){
        if (bucket[temp, l] == 0){
          bucket[temp, l] = item;
          break;
        }
      }
    }
    for (int o = 0, x = 0; x < array_x; x++){
      for (int y = 0; y < array_y; y++){
        if (bucket[x, y] == 0) continue;
        unsorted[o++] = bucket[x, y];
      }
    }
  }
}

static void Main(string[] args){
  int[] x = { 999999999, 65, 24, 47, 13, 50, 92, 88, 66, 33, 22445, 10001, 624159, 624158, 624155501 };
  radix_sort(x);
  foreach (var item in x){
    if (item > 0)
      Console.WriteLine(item + ",");
  }
  Console.ReadLine();
}