生活_傻大方

  1. 首页 > 人文 > >

排序算法面试官：手撕十大排序算法，你会几种？( 五 )


桶排序（Bucket Sort） 桶排序是计数排序的升级版 。 它利用了函数的映射关系 ， 高效与否的关键就在于这个映射函数的确定 。 为了使桶排序更加高效 ， 我们需要做到这两点：

  • 在额外空间充足的情况下 ， 尽量增大桶的数量
  • 使用的映射函数能够将输入的N个数据均匀的分配到K个桶中
同时 ， 对于桶中元素的排序 ， 选择何种比较排序算法对于性能的影响至关重要 。
（1）算法步骤
步骤1：人为设置一个BucketSize ， 作为每个桶所能放置多少个不同数值（例如当BucketSize==5时 ， 该桶可以存放｛1,2,3,4,5｝这几种数字 ， 但是容量不限 ， 即可以存放100个3）；步骤2：遍历输入数据 ， 并且把数据一个一个放到对应的桶里去；步骤3：对每个不是空的桶进行排序 ， 可以使用其它排序方法 ， 也可以递归使用桶排序；步骤4：从不是空的桶里把排好序的数据拼接起来；
注意 ， 如果递归使用桶排序为各个桶排序 ， 则当桶数量为1时要手动减小BucketSize增加下一循环桶的数量 ， 否则会陷入死循环 ， 导致内存溢出；
（2）过程演示
排序算法面试官：手撕十大排序算法，你会几种？
本文插图
（3）代码实现
/** * 桶排序 * * @param array * @param bucketSize * @return */ public static ArrayList BucketSort(ArrayList array, int bucketSize) { if (array == null || array.size() &lt 2) return array int max = array.get(0), min = array.get(0) // 找到最大值最小值 for (int i = 0 i &lt array.size() i++) { if (array.get(i) &gt max) max = array.get(i) if (array.get(i) &lt min) min = array.get(i) } int bucketCount = (max - min) / bucketSize + 1 ArrayList&ltArrayList&gt bucketArr = new ArrayList&lt&gt(bucketCount) ArrayList resultArr = new ArrayList&lt&gt() for (int i = 0 i &lt bucketCount i++) { bucketArr.add(new ArrayList()) } for (int i = 0 i &lt array.size() i++) { bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i)) } for (int i = 0 i &lt bucketCount i++) { if (bucketSize == 1) { // 如果待排序数组中有重复数字时 for (int j = 0 j &lt bucketArr.get(i).size() j++) resultArr.add(bucketArr.get(i).get(j)) } else { if (bucketCount == 1) bucketSize-- ArrayList temp = BucketSort(bucketArr.get(i), bucketSize) for (int j = 0 j &lt temp.size() j++) resultArr.add(temp.get(j)) } } return resultArr }
基数排序（Radix Sort）
基数排序也是非比较的排序算法 ， 对每一位进行排序 ， 从最低位开始排序 ， 复杂度为O(kn),为数组长度 ， k为数组中的数的最大的位数；
基数排序是按照低位先排序 ， 然后收集；再按照高位排序 ， 然后再收集；依次类推 ， 直到最高位 。 有时候有些属性是有优先级顺序的 ， 先按低优先级排序 ， 再按高优先级排序 。 最后的次序就是高优先级高的在前 ， 高优先级相同的低优先级高的在前 。 基数排序基于分别排序 ， 分别收集 ， 所以是稳定的 。
（1）算法步骤
步骤1：取得数组中的最大数 ， 并取得位数；步骤2：arr为原始数组 ， 从最低位开始取每个位组成radix数组；步骤3：对radix进行计数排序（利用计数排序适用于小范围数的特点）；
（2）过程演示
排序算法面试官：手撕十大排序算法，你会几种？
本文插图
（3）代码实现
/** * 基数排序 */public class RadixSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝 ， 不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length) int maxDigit = getMaxDigit(arr) return radixSort(arr, maxDigit) } /** * 获取最高位数 */ private int getMaxDigit(int[] arr) { int maxValue = http://news.hoteastday.com/a/getMaxValue(arr) return getNumLenght(maxValue) } private int getMaxValue(int[] arr) { int maxValue = arr[0] for (int value : arr) { if (maxValue < value) { maxValue = value } } return maxValue } protected int getNumLenght(long num) { if (num == 0) { return 1 } int lenght = 0 for (long temp = num temp != 0 temp /= 10) { lenght++ } return lenght } private int[] radixSort(int[] arr, int maxDigit) { int mod = 10 int dev = 1 for (int i = 0 i < maxDigit i++, dev *= 10, mod *= 10) { // 考虑负数的情况 ， 这里扩展一倍队列数 ， 其中 [0-9]对应负数 ， [10-19]对应正数 (bucket + 10) int[][] counter = new int[mod * 2][0] for (int j = 0 j < arr.length j++) { int bucket = ((arr[j] % mod) / dev) + mod counter[bucket] = arrayAppend(counter[bucket], arr[j]) } int pos = 0 for (int[] bucket : counter) { for (int value : bucket) { arr[pos++] = value } } } return arr } /** * 自动扩容 ， 并保存数据 * * @param arr * @param value */ private int[] arrayAppend(int[] arr, int value) { arr = Arrays.copyOf(arr, arr.length + 1) arr[arr.length - 1] = value return arr }}



上一篇：青年红萝卜生产用上无人机械

下一篇：老王撩机华为Mate40“PK”iPhone12，2020年下半年最强王者之争