整理，面试的时候问了很多。排序的时间复杂度为O(n)，除了基数排序（RadixSort），还有计数排序（CountingSort）。今天1分钟，通过几张图，尽量让大家理解计数和排序。计数排序的适用范围？待排序的元素在一定范围内[MIN,MAX]。画外音：很多业务场景都符合这个场景，比如uint32的数字排序在[0,2^32]之间。计数排序的空间复杂度？计数排序需要一个大小为O(MAX-MIN)的辅助空间来存储所有元素出现的次数（“count”）。画外音：计数和排序的核心是用空间换取时间。计数排序的关键步骤？第一步：扫描待排序数据arr[N]，使用计数数组counting[MAX-MIN]统计每个arr[N]中出现的元素；第二步：扫描计数数组counting[]，恢复arr[N]，排序结束；举个栗子：假设要排序的数组，arr={5,3,7,1,8,2,9,4,7,2,6,6,2,6,6}很容易发现待排序的元素在[0,10]之间，counting[0,10]可以用来存储计数。第一步：统计计数扫描未排序数组arr[N]，对出现的每个元素进行计数。扫描后计数数组counting[0,10]会变成上图所示，如粉色所示，元素6在arr[N]中出现了4次，而在counting[0,10]中，下标的6的位置计数为4。第二步：恢复数组扫描计数数组counting[0,10]，通过对每个元素的计数，恢复arr[N]。如上图粉红色所示，计数下标6的count[0,10]为4，排序顺序为连续4个6。从计数下标MIN到MAX，一一还原。当arr[N]被填满时，排序结束。魔法不是魔法！！！计数排序（CountingSort），总结：计数排序，时间复杂度为O(n)；当需要排序的元素个数较多，但取值范围很窄时，计数排序非常节省空间；希望大家在这一分钟有所收获。【本文为专栏作者《58神剑》原创稿件，转载请联系原作者】点此阅读更多该作者好文
