有一种很神奇的排序方法，基数排序（RadixSort），时间复杂度为O(n)。今天用1分钟的时间通过几张图，尽量让大家明白其中的细节。画外音：居然有一种时间复杂度为O(n)的排序算法？不仅如此，实际上还有更多。举个栗子：假设待排序数组arr={72,11,82,32,44,13,17,95,54,28,79,56}基数排序的两个关键点：（1）基数：被排序后的元素的“个位”、“十位”、“百位”暂且称为“基”。栗子中“碱基”的个数是2（个位和十位）；画外音：来自野史，大神可以帮忙改正。(2)桶：“底”的每一位都有一个取值范围。栗子中“base”的取值范围是0-9，一共有10种，所以需要10个桶来存放排序后的元素；基数排序的算法步骤为：FOR(eachbase){//在循环中，根据某个“基数”Step1：遍历数据集arr，将元素放入对应的bucketbucketStep2：遍历bucket,把元素放回数据集中arr}更具体的，对应上面的栗子，“基数”有一个数字和一个十位数字，所以FOR循环会执行两次。第一次：基于“单位”。画外音：上图中红色标出的部分，个位为“base”。第一步：遍历数据集arr，将元素放入对应的桶中；操作完成后，每个桶都会像上图一样，即个位数相同的元素会在同一个桶中。第二步：遍历桶，将元素放回数据集arr；画外音：注意先进入桶的元素必须先出桶。操作完成后，数据集会像上面那样，即整体按照个位数排序。画外音：个位数小的在前，个位数大的在后。第二次：以“十位数”为准。画外音：上图中红色标出的部分，十位是“底”。第一步：仍然遍历数据集arr，将元素放入相应的桶中；操作完成后，每个桶都会像上图一样，即十位相同的元素在同一个桶中。第二步：还是遍历桶，把元素放回数据集arr中；操作完成后，数据集会像上面的样子，也就是整体也按照十位排序了。旁白：小十在前，大十在后。第一次按照个位从小到大，第二次按照十位从小到大，即：排序结束。魔法不是魔法！！！几个小点：(1)基数的选择可以先从个位开始，也可以从十位开始，结果是一样的；(2)基数排序是一种稳定的排序；(3)时间复杂度可以认为是线性的O(n)；我希望每个人都能在这一分钟有所收获。【本文为专栏作者《58神剑》原创稿件，转载请联系原作者】点此阅读更多该作者好文
