? $f(n) = 2f(frac{n}{2})+ n $
? (n = frac{n}{2}) : : (f(frac{n}{2}) = 2f(frac{n}{4}) + frac{n}{4})
? (n=frac{n}{4}) : : (f(frac{n}{4})=2f(frac{n}{8}) + frac{n}{8})
? (cdots)
? (n=frac{n}{2^{m-1}}) : : (f(frac{n}{2^{m-1}}) = 2f(frac{n}{2^m}) + frac{n}{2^{m-1}})
? 即：(f(n) = 2f(frac{n}{2}) + n)
? (=2[2f(frac{n}{4} + frac{n}{4}) + n]) = $ 22f(frac{n}{22}) + 2n$
? (=2^2[f(2f(frac{n}{8}) + frac{n}{4})] + 2n) = (2^3f(frac{n}{2^3}) + 3n)
? (cdots)
? (=2^mf(frac{n}{2^m}) + mn)
? 当数组被分割成仅剩一个元素时，此时分割为(2^mf(1)+mn) 即： (frac{n}{2^m} = 1)
? 则：(m = log_2n)
? 代入得(f(n) = 2^{log_2n}f(1) + n * log_2n = n + nlog_2n)
? 所以归并排序的时间复杂度为：
[O(n) = nlog_2n ]
7.3 代码实现
public static int[] MergeSort(int[] arr) { // 数组中仅有一个元素==已排序 if (arr.length < 2) {return arr; } // 分割数组的下标 int middle = arr.length / 2; // 将数组分割成arr[0] ~ arr[middle-1] 和 arr[middle] ~ arr[length-1] 两部分 int[] left = Arrays.copyOfRange(arr, 0, middle); int[] right = Arrays.copyOfRange(arr, middle, arr.length); /*** 可以拆分为* int[] arr1 = MergeSort(left);* int[] arr2 = MergeSort(right);* 对两个分割后的数组分别再进行归并排序* return merge(arr1, arr2);*/ return merge2(MergeSort(left), MergeSort(right));}/** * 将两个数组进行合并方法 1 */protected static int[] merge1(int[] left, int[] right) { // 合并后的数组 int[] result = new int[left.length + right.length]; // i 进行计数，直到等于left或者right数组的长度 int i = 0; // 循环对left和right数组的首个元素进行比较，把小的放入result数组 // 并重新给left或right数组赋值 while (left.length > 0 && right.length > 0) {if (left[0] <= right[0]) {result[i] = left[0];left = Arrays.copyOfRange(left, 1, left.length);} else {result[i] = right[0];right = Arrays.copyOfRange(right, 1, right.length);}i++; } // 此时left或right数组有一个已经遍历完毕，直接把剩下的元素全部放入result数组 while (left.length > 0) {result[i] = left[0];i++;left = Arrays.copyOfRange(left, 1, left.length); } while (right.length > 0) {result[i] = right[0];i++;right = Arrays.copyOfRange(right, 1, right.length); } return result;}/** * 将两个数组进行合并方法 2 * 个人还是倾向于这个直观的 */private static int[] merge2(int[] left, int[] right) { // 合并后的结果 int[] result = new int[left.length + right.length]; // i,j分别用于遍历left，right数组 int i = 0; int j = 0; // count用于放入result数组时的下标计数 int count = 0; // 循环对left和right数组元素进行比较，并把小的赋值给result[count] // 直到遍历完left或者right数组 while (i < left.length && j < right.length) {if (left[i] < right[j]) {result[count] = left[i];i++;} else {result[count] = right[j];j++;}count++; } // 此时left或right数组有一个已经遍历完毕，直接把剩下的元素全部放入result数组 while (i < left.length) {result[count] = left[i];i++;count++; } while (j < right.length) {result[count] = right[j];j++;count++; } return result;}7.4 图示注：两个图不是同一个算法过程
文章插图
文章插图
8、基数排序? 取得最大整数的位数，从个位开始进行比较放入新的数组，再收集起来，此时数组按照个位有序排列，再进位进行比较收集，以此类推，直到最高位比较完成，此时数组全部有序 。
8.1 算法步骤
- 取得数组最大数的位数
- 根据数组元素个位数的大小放入不同的数组中
- 按照顺序将数组中的元素收集起来，此时新的数组按数组元素的个位数有序
- 数组元素进位（十位、百位...）按照该位的大小重复2、3
- 直到按照最大位数进行元素收集后所有元素有序
8.3 代码实现
private static 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;}// 自动扩容，并保存数据private static int[] arrayAppend(int[] arr, int value) { arr = Arrays.copyOf(arr, arr.length + 1); arr[arr.length - 1] = value; return arr;}// 获取最高位数private static int getMaxDigit(int[] arr) { int maxValue = https://www.isolves.com/it/cxkf/sf/2022-06-08/getMaxValue(arr); return getNumLength(maxValue);}// 获取最大值private static int getMaxValue(int[] arr) { int maxValue = arr[0]; for (int value : arr) {if (maxValue
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 建设成为新时代改革开放的新高地?适应新形势,奋进新征程,实现新突破
- 息屏显示|iOS 16代码实锤：苹果iPhone 14 Pro支持AOD息屏显示
- 事业单位|事业单位的临时工，何时能与正式职工实现同工同酬呢？答案来了
- Java代码质量检查工具及使用案例
- SpringBoot 实现 Office 各种格式在线预览
- JAVA-Servlet忘记实现HttpServlet接口处理
- 详解java中float与double的区别
- 多年前借鉴b/s优势实现基于.net的c/s框架
- 身份证开头代码
- 苹果|苹果“最没存在感”新品要来了：新款HomePod现身iOS 16代码
