江苏龙网

  1. 主页 > 生活百科 > >

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

面试官


（2）过程演示

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

文章插图
 
（3）代码实现
public class CountingSort implements IArraySort {@Overridepublic int[] sort(int[] sourceArray) throws Exception {// 对 arr 进行拷贝，不改变参数内容int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);int maxValue = https://www.isolves.com/sh/zc/2020-07-26/getMaxValue(arr);return countingSort(arr, maxValue);}private int[] countingSort(int[] arr, int maxValue) {int bucketLen = maxValue + 1;int[] bucket = new int[bucketLen];for (int value : arr) {bucket[value]++;}int sortedIndex = 0;for (int j = 0; j < bucketLen; j++) {while (bucket[j] > 0) {arr[sortedIndex++] = j;bucket[j]--;}}return arr;}private int getMaxValue(int[] arr) {int maxValue = arr[0];for (int value : arr) {if (maxValue < value) {maxValue = value;}}return maxValue;}}桶排序（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<Integer> BucketSort(ArrayList<Integer> array, int bucketSize) {if (array == null || array.size() < 2)return array;int max = array.get(0), min = array.get(0);// 找到最大值最小值for (int i = 0; i < array.size(); i++) {if (array.get(i) > max)max = array.get(i);if (array.get(i) < min)min = array.get(i);}int bucketCount = (max - min) / bucketSize + 1;ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);ArrayList<Integer> resultArr = new ArrayList<>();for (int i = 0; i < bucketCount; i++) {bucketArr.add(new ArrayList<Integer>());}for (int i = 0; i < array.size(); i++) {bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));}for (int i = 0; i < bucketCount; i++) {if (bucketSize == 1) { // 如果待排序数组中有重复数字时for (int j = 0; j < bucketArr.get(i).size(); j++)resultArr.add(bucketArr.get(i).get(j));} else {if (bucketCount == 1)bucketSize--;ArrayList<Integer> temp = BucketSort(bucketArr.get(i), bucketSize);for (int j = 0; j < 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 {@Overridepublic 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 = https://www.isolves.com/sh/zc/2020-07-26/getMaxValue(arr);return getNumLenght(maxValue);}private int getMaxValue(int[] arr) {int maxValue = arr[0];for (int value : arr) {if (maxValue


推荐阅读


上一篇：EC6价格能打，筹备电池资产公司，满血复活的蔚来如何加电？

下一篇：淘宝卖美妆需要什么资质 淘宝开店卖化妆品需要什么条件