手机网站开发常用工具学校网站源码html

手机网站开发常用工具,学校网站源码html,wordpress自适应相册,北京网络营销岗位数量1. 基数排序的基本原理 1.1 核心思想 基数排序的核心思想是分配式排序#xff0c;它通过键值的各个位值#xff0c;将要排序的元素分配到不同的桶中#xff0c;然后按顺序收集这些元素#xff0c;重复这个过程直到所有位都处理完毕。 1.2 两种实…1. 基数排序的基本原理1.1 核心思想基数排序的核心思想是分配式排序它通过键值的各个位值将要排序的元素分配到不同的桶中然后按顺序收集这些元素重复这个过程直到所有位都处理完毕。1.2 两种实现方式基数排序主要有两种实现方法最低位优先法LSD - Least Significant Digit first从最低位个位开始排序然后依次处理十位、百位等直到最高位。最高位优先法MSD - Most Significant Digit first从最高位开始排序然后递归地对每个子序列进行排序。LSD方法更常用因为它实现简单且稳定而MSD方法在某些情况下效率更高但实现更复杂。2. 基数排序的工作步骤基数排序的执行过程可以分为以下几个步骤确定最大位数找到待排序数组中的最大值确定需要排序的轮数即最大位数创建桶创建10个桶0-9用于存放每个位上的数字按位分配从最低位开始将每个元素按当前位的数字放入对应的桶中收集元素按桶的顺序0-9将元素收集回原数组重复处理对下一位重复步骤3-4直到处理完所有位2.1 具体示例以数组[53, 3, 542, 748, 14, 214]为例第一轮个位排序个位为0无个位为1无个位为2542个位为353, 3个位为414, 214个位为5无个位为6无个位为7无个位为8748个位为9无收集后数组变为[542, 53, 3, 14, 214, 748]第二轮十位排序十位为03十位为114, 214十位为2无十位为3无十位为4542, 748十位为553其余为无收集后数组变为[3, 14, 214, 542, 748, 53]第三轮百位排序百位为03, 14, 53百位为1无百位为2214百位为3无百位为4无百位为5542百位为6无百位为7748其余为无最终排序结果为[3, 14, 53, 214, 542, 748]3. Java实现以下是基数排序的完整Java实现代码import java.util.Arrays; public class RadixSort { /** * 基数排序主方法LSD方式 * param arr 待排序数组 */ public static void radixSort(int[] arr) { if (arr null || arr.length 1) { return; } // 1. 获取数组中的最大值确定最大位数 int max getMax(arr); // 2. 从个位开始对每一位进行计数排序 for (int exp 1; max / exp 0; exp * 10) { countingSortByDigit(arr, exp); } } /** * 获取数组中的最大值 * param arr 数组 * return 最大值 */ private static int getMax(int[] arr) { int max arr[0]; for (int i 1; i arr.length; i) { if (arr[i] max) { max arr[i]; } } return max; } /** * 按指定位数进行计数排序 * param arr 待排序数组 * param exp 当前位数1表示个位10表示十位100表示百位... */ private static void countingSortByDigit(int[] arr, int exp) { int n arr.length; int[] output new int[n]; // 输出数组 int[] count new int[10]; // 计数数组0-9共10个数字 // 初始化计数数组 Arrays.fill(count, 0); // 统计每个桶中的元素个数 for (int i 0; i n; i) { int digit (arr[i] / exp) % 10; count[digit]; } // 将计数数组转换为位置数组 // count[i]现在包含小于等于i的元素个数 for (int i 1; i 10; i) { count[i] count[i - 1]; } // 从后往前遍历原数组确保排序的稳定性 for (int i n - 1; i 0; i--) { int digit (arr[i] / exp) % 10; output[count[digit] - 1] arr[i]; count[digit]--; } // 将排序结果复制回原数组 System.arraycopy(output, 0, arr, 0, n); } /** * 测试方法 */ public static void main(String[] args) { // 测试用例1 int[] arr1 {53, 3, 542, 748, 14, 214}; System.out.println(原始数组1: Arrays.toString(arr1)); radixSort(arr1); System.out.println(排序后数组1: Arrays.toString(arr1)); // 测试用例2 int[] arr2 {170, 45, 75, 90, 802, 24, 2, 66}; System.out.println(\n原始数组2: Arrays.toString(arr2)); radixSort(arr2); System.out.println(排序后数组2: Arrays.toString(arr2)); // 性能测试 testPerformance(); } /** * 性能测试对10万个随机数进行排序 */ private static void testPerformance() { int size 100000; int[] arr new int[size]; // 生成随机数 for (int i 0; i size; i) { arr[i] (int)(Math.random() * 1000000); } long startTime System.currentTimeMillis(); radixSort(arr); long endTime System.currentTimeMillis(); System.out.println(\n排序 size 个随机数耗时: (endTime - startTime) 毫秒); // 验证排序正确性 boolean isSorted true; for (int i 1; i arr.length; i) { if (arr[i] arr[i - 1]) { isSorted false; break; } } System.out.println(排序验证: (isSorted ? 正确 : 错误)); } }4. 基数排序的变体实现4.1 使用二维桶的实现方式除了使用计数排序的变体外还可以直接使用二维数组作为桶来实现基数排序public static void radixSortWithBucket(int[] arr) { if (arr null || arr.length 1) { return; } // 获取最大值和最大位数 int max arr[0]; for (int num : arr) { if (num max) { max num; } } int maxLength String.valueOf(max).length(); // 创建10个桶0-9 int[][] bucket new int[arr.length]; int[] bucketCount new int[10]; // 记录每个桶中元素的数量 // 从个位开始逐位排序 for (int i 0, exp 1; i maxLength; i, exp * 10) { // 将元素分配到桶中 for (int j 0; j arr.length; j) { int digit (arr[j] / exp) % 10; bucket[digit][bucketCount[digit]] arr[j]; bucketCount[digit]; } // 从桶中收集元素 int index 0; for (int k 0; k 10; k) { if (bucketCount[k] ! 0) { for (int l 0; l bucketCount[k]; l) { arr[index] bucket[k][l]; } bucketCount[k] 0; // 清空计数为下一轮做准备 } } } }4.2 支持负数的基数排序标准的基数排序只支持非负整数。如果需要支持负数可以先分离正负数分别排序后再合并public static void radixSortWithNegative(int[] arr) { if (arr null || arr.length 1) { return; } // 分离正数和负数 ListInteger positiveList new ArrayList(); ListInteger negativeList new ArrayList(); for (int num : arr) { if (num 0) { positiveList.add(num); } else { negativeList.add(-num); // 转为正数处理 } } // 将List转换为数组 int[] positiveArr positiveList.stream().mapToInt(i - i).toArray(); int[] negativeArr negativeList.stream().mapToInt(i - i).toArray(); // 分别排序 if (positiveArr.length 0) { radixSort(positiveArr); } if (negativeArr.length 0) { radixSort(negativeArr); } // 合并结果负数按降序正数按升序 int index 0; for (int i negativeArr.length - 1; i 0; i--) { arr[index] -negativeArr[i]; // 转回负数 } for (int num : positiveArr) { arr[index] num; } }5. 基数排序的性能分析5.1 时间复杂度基数排序的时间复杂度为 *O(d(nk))**其中d最大数字的位数n待排序元素的数量k基数十进制中k10具体分析每轮排序需要遍历所有元素一次时间复杂度为O(n)每轮需要处理k个桶时间复杂度为O(k)总共需要进行d轮排序因此总时间复杂度为O(d*(nk))5.2 空间复杂度基数排序需要额外的空间来存储输出数组O(n)计数数组/桶O(k) 因此空间复杂度为O(nk)。5.3 稳定性基数排序是一种稳定的排序算法。在分配元素到桶中时如果两个元素在当前位上的数字相同它们会按照原来的顺序放入桶中在收集时也按照先进先出的原则因此相等元素的相对顺序不会改变。6. 基数排序的优缺点6.1 优点时间复杂度较低当d较小时时间复杂度接近O(n)比大多数比较排序算法O(n log n)更快稳定性好保持相等元素的相对顺序适用于需要稳定排序的场景适合整数排序特别适合对整数进行排序尤其是位数不多的情况可扩展性强可以轻松扩展到其他进制如二进制、十六进制6.2 缺点空间消耗大需要额外的O(nk)空间仅适用于整数标准实现只适用于整数对于浮点数或字符串需要特殊处理对负数需要特殊处理需要先将负数转换为正数排序后再转换回来依赖位数当最大数的位数很大时性能会下降7. 基数排序的应用场景7.1 适用场景整数排序特别是当整数范围不大且位数较少时多关键字排序如按年、月、日排序日期字符串排序可以按字符的ASCII码或Unicode码进行排序卡片排序机最初就是为打孔卡片设计的排序方法7.2 不适用场景浮点数排序需要特殊处理数据范围极大当最大数的位数非常多时内存受限环境需要较多额外空间