排序，面试问的问题比较多，考察基本功。时间复杂度为O(n)的排序常见的有三种：基数排序计数排序桶排序今天用1分钟的时间，尽量让大家理解桶排序。画外音：百度“桶排序”，很多文章都是错误的，本文内容与《算法导论》中的桶排序一致。桶排序的适用范围是待排序的元素可以均匀分布在一定范围[MIN,MAX]之间。画外音：很多业务场景都符合这个场景，需要排序的元素在一定范围内，分布均匀。桶排序需要两个辅助空间：第一个辅助空间是桶空间B第二个辅助空间是桶中的元素列表空间一般来说，空间复杂度是O(n)。桶排序有两个关键步骤：扫描待排序数据A[N]，对于元素A[i]，放入对应的桶X中，A[i]放入桶X中，如果桶X中已经有几个元素，使用插入排序，将arr[i]放在桶中合适的位置画外音：桶X中的所有元素总是有序的；插入排序是稳定的，所以桶中元素的顺序也是稳定的；当arr[N]中的所有元素按照上述步骤放入相应的桶中后，即完成全排序。桶排序伪代码为：bucket_sort(A[N]){fori=1ton{将A[i]放入对应的桶B[X]中；使用插入排序将A[i]插入到B[X]的正确位置；}将B[X]中的所有元素按顺序合并，排序完成；}例如：假设待排序数组是均匀的distributedbetween[0,99]:{5,18,27,33,42,66,90,8,81,47,13,67,9,36,62,22}可以设置10个桶，申请额外空间bucket[10]作为辅助空间。其中，每个桶bucket[i]用于存储[10*i,10*i+9]的元素列表。如上图所示：待排序数组为unsorted[16]，桶空间为buket[10]。扫描完所有元素后，将元素放入对应的桶中。插入排序是用来保证它们总是有序的，比如标记为红色的元素66、67、62最终会进入一个桶中，使用插入排序来保持桶中的顺序。最后按顺序输出每个桶，排序完成。魔法不是魔法！！！桶排序（BucketSort），总结：桶排序是一种排序桶排序，复杂度为O(n)。是一种稳定的排序桶排序，适用于数据均匀分布在一个区间内的场景【本文为专栏作者《58神剑》原创稿件，转载请联系原作者】点此阅读更多好文该作者的文章
