#!/usr/bin/env python
# -*- coding: UTF-8 -*-
from datetime import datetime
import testdata
# 基数排序
# 基数排序不需要进行元素的比较与交换。而计数排序则是打表或是哈希思想最简单的实现。

# 计数排序的核心思想是，构建一个足够大的数组 hashArray[]，数组大小需要保证能够把所有元素都包含在这个数组上
# 1.在对序列 T 进行排序时，只要依次读取序列 T 中的元素，并修改数组 hashArray[] 中把元素值对应位置上的值即可。这一句有一些绕口。
# 打个比方，我们要把 T[0] 映射到 hashArray[] 中，就是 hashArray[T[0]] = 1. 也就是 hashArray[2314] = 1.
# 如果序列 T 中有两个相同元素，那么在 hashArray 的相应位置上的值就是 2。
# 2.在基数排序里，我们需要一个很大的二维数组，二维数组的大小是 （10 * n）。10 代表的是我们每个元素的每一位都有 10 种可能，也就是 10 进制数。
# 在上图中，我们是以每个数的个位来代表这个数，于是，5428 就被填充到了第 8 个桶中了。下次再进行填充的时候，就是以十位进行填充，比如 5428 在此时，就会选择以 2 来代表它。
# 3.在寻求优化的路上，我们想到一种可以压缩空间的方法，且时间复杂度并没有偏离得太厉害。那就是设计了两个辅助数组，一个是 count[]，一个是 bucket[]。
# count 用于记录在某个桶中的最后一个元素的下标，然后再把原数组中的元素计算一下它应该属于哪个“桶”，并修改相应位置的 count 值。直到最大数的最高位也被添加到桶中，或者说，当所有的元素都被被在第 0 个桶中，基数排序就结束了


# TODO


if __name__ == '__main__':
    arr = testdata.arr2
    time1 = datetime.now()
    # radixsort(arr)
    time2 = datetime.now()
    timeDef = (time2 - time1).microseconds   # 单位微秒
    print("用时：" + str(timeDef) + "微妙")
    print(arr)