算法Homework

内容一 几种排序的比较

分别针对随机生成的若干组整数序列（比 如规模为1000个数，10000个数，100000 个数）进行排序，排序算法使用四种方法， 至少包括以下三种经典方法：插入排序算 法、合并排序算法和快速排序算法、近些年提出的比较新颖的排序算法统计各种情况下排序所耗费的时间改为降序10个数，在使用快速排序进行排序时，尝试给出数组的演化情况稳定性与空间性能

选择的第四个排序

侏儒排序

侏儒排序（英语：Gnome Sort）或愚人排序（英语：Stupid Sort）最初在2000年由伊朗计算机工程师Hamid Sarbazi-Azad提出，他称之为“愚人排序”。此后Dick_Grund也描述了这一算法，称其为“侏儒排序”。此算法类似于插入排序，但是移动元素到它该去的位置是通过一系列类似冒泡排序的移动实现的。从概念上讲侏儒排序非常简单，甚至不需要嵌套循环。

解释

下面是侏儒排序的伪代码

procedure gnomeSort(a[]): pos := 0 while pos < length(a): if (pos == 0 or a[pos] >= a[pos-1]): pos := pos + 1 else: swap a[pos] and a[pos-1] pos := pos - 1

样例

给定一个未排序的数组a = [5, 3, 2, 4]，侏儒排序在while循环中执行以下步骤。粗体表示pos变量当前所指的元素。

当前数组下一步操作[5, 3, 2, 4]a[pos] < a[pos-1]，交换[3, 5, 2, 4]a[pos] >= a[pos-1]，pos自增[3, 5, 2, 4]a[pos] < a[pos-1]，交换；pos > 1，pos自减[3, 2, 5, 4]a[pos] < a[pos-1]，交换；pos <= 1，pos自增[2, 3, 5, 4]a[pos] >= a[pos-1]，pos自增[2, 3, 5, 4]a[pos] < a[pos-1]，交换；pos > 1，pos自减[2, 3, 4, 5]a[pos] >= a[pos-1]，pos自增[2, 3, 4, 5]a[pos] >= a[pos-1]，pos自增[2, 3, 4, 5]pos == length(a)，完成

随机数可能用到的拓展知识：

Arrays.stream(ints) 将基本类型数组转换为基本类型流。 int[ ] => IntStream .boxed() 将基本类型流转换为对象流。 => Stream< Integer > .collect(Collectors.toList()) 将对象流收集为集合。 => List< Integer >

.toArray(Integer[ ]::new) 将对象流转换为对象数组。=> Integer[ ]

.mapToInt(Integer::valueOf) 将对象流转换成基本类型流。=> IntStream .toArray() 将基本类型流转换为基本类型数组。 => int[ ]

list.stream() 将列表装换为对象流。List< Integer > => Stream< Integer >

实验过程：

一. 测试性能

1.随机数类，里面有两个方法用于生成随机数

第一个是真随机：int类型里所有整数随机，用于真正测试排序性能

第二个是100以内的随机数：（因为用第一个测试的时候发现生成的数字的位数都太长了，看着费劲）用于简单验证排序的正确性

import java.util.Random; import java.util.stream.IntStream; /** * @author SJ * @date 2020/10/14 */ public class RandomUtil { //真正的int类型的全范围random public static int[] generateRandomNum(int length){ Random random = new Random(); IntStream ints = random.ints(length); //int流转为 int数组 return ints.toArray(); } //int范围内随机生成的数字都太长了，写一个100以内的随机数 public static int[] randomBetween100(int length){ int[] nums=new int[length]; for (int i = 0; i < nums.length; i++) { nums[i]=(int)(Math.random()*100); } return nums; } } 把四种排序算法封装成了一个类 import java.util.Arrays; /** * @author SJ * @date 2020/10/14 */ public class SortCompare { //插入排序 /** * 假设第一个有序，从前往后遍历依次将得到的数字插入前面的有序序列中 * 不需要辅助空间 */ public static void insertSort(int[] test) { int[] nums = Arrays.copyOf(test, test.length); for (int i = 1; i < nums.length; i++) { int current = nums[i];//记录待插入数据 int preIndex = i - 1;//记录有序数组最后一个数字的位置 //挪位 while (preIndex >= 0 && current < nums[preIndex]) { nums[preIndex + 1] = nums[preIndex]; preIndex--; } nums[preIndex + 1] = current; } System.out.println(Arrays.toString(nums)); } //归并排序 /** * 二路归并排序 * 包含1.两个有序数组合并成一个有序数组 * 2.递归 */ //设定辅助数组长度 private static int[] temp; public SortCompare(int length) { temp = new int[length]; } //不要在merge函数里构造新数组，因为merge函数会被多次调用，影响性能 private static void merge(int[] nums, int left, int right) { ; for (int i = left; i <= right; i++) { temp[i] = nums[i]; } int middle = (left + right) / 2; int l = left; int r = middle + 1; for (int i = left; i <= right; i++) { //左边数组里的数字已经合并完，右边还有剩余 if (l == middle + 1 && r < right + 1) nums[i] = temp[r++]; //右边数组里的数字已经合并完，左边还有剩余 else if (r == right + 1 && l < middle + 1) nums[i] = temp[l++]; else if (temp[l] <= temp[r]) nums[i] = temp[l++]; else { nums[i] = temp[r++]; } } } private static void Sort(int[] nums, int left, int right) { if (left < right) { Sort(nums, left, (left + right) / 2); Sort(nums, (left + right) / 2 + 1, right); merge(nums, left, right); } } public static void mergeSort(int[] test) { int[] nums = Arrays.copyOf(test, test.length); Sort(nums, 0, nums.length - 1); System.out.println(Arrays.toString(nums)); } //快速排序 /** * 快速排序 * 以数列第一个基准数，记录下基准数的值，并挖坑，从后往前找比基准数小的转移到坑中， * 从前往后找比基准数大的填入新坑 * 最后low与high相遇时将基准数填入该处 * 即完成一趟快排。 * 一趟快排的结果是：基准数前面的数字都比它小，基准数后面的数字都比它大 * 然后递归即可 */ private static void quicksort(int[] nums, int low, int high) { int base = nums[low]; int l = low; int h = high; while (l < h) { while (l < h && nums[h] >= base) h--; if (nums[h] < base) nums[l++] = nums[h]; while (l < h && nums[l] <= base) l++; if (nums[l] > base) nums[h--] = nums[l]; } nums[l] = base; //一开始没加退出条件，陷入死循环了 栈溢出 if (low < l) quicksort(nums, low, h - 1); if (high > h) quicksort(nums, l + 1, high); } public static void quickSortUtil(int[] test) { int[] nums = Arrays.copyOf(test, test.length); quicksort(nums, 0, nums.length - 1); System.out.println(Arrays.toString(nums)); } //侏儒排序 /** * 在把大的往后挪的同时 * 指针所指的数字的前面那些总是是有序的，中途有交换所以会打乱前面的排序，所以指针会向前挪作调整 */ public static void stupidSort(int[] test) { int[] nums = Arrays.copyOf(test, test.length); int pos = 0; while (pos < nums.length) { //如果指针所指的数字大于或者等于前一个，证明有序，指针往后挪 if (pos == 0 || nums[pos] >= nums[pos - 1]) pos++; //如果前面的数字比自己大，证明无序，就与前面的交换，然后调整 else { int temp = nums[pos];//辅助空间就要这一个temp nums[pos] = nums[pos - 1]; nums[pos - 1] = temp; pos--; } } System.out.println(Arrays.toString(nums)); } } 测试

首先用简单数据测试一下写得各个方法有没有问题

import java.util.Arrays; import java.util.Scanner; /** * @author SJ * @date 2020/10/14 */ public class TestValidity { public static void main(String[] args) { //如果想在同一个main方法里测试，测试的时候需要注意，要用同一个数组测试不同的排序方法，需要在每个方法里新建副本，用副本测试 //因为java数组是传引用，在每个方法里排序，会直接作用到原数组，再用这个排好序的数组测试下面的排序方法就没有意义了 //也可以选择在junit里测 System.out.println("用小数据测试一下排序代码的正确性："); System.out.println("输入数组要测试的数组长度；"); Scanner scanner=new Scanner(System.in); int i = scanner.nextInt(); int[] nums=RandomUtil.randomBetween100(i); System.out.println("随机生成的数组为："); System.out.println(Arrays.toString(nums)); System.out.println("输入数组为："+Arrays.toString(nums)); System.out.println("插入排序结果："); SortCompare.insertSort(nums); System.out.println("输入数组为："+Arrays.toString(nums)); System.out.println("合并排序结果："); //把合并排序的辅助数组new在外面了，可以提高性能 SortCompare sortCompare = new SortCompare(i); SortCompare.mergeSort(nums); System.out.println("输入数组为："+Arrays.toString(nums)); System.out.println("快速排序结果："); SortCompare.quickSortUtil(nums); System.out.println("输入数组为："+Arrays.toString(nums)); System.out.println("侏儒排序结果："); SortCompare.stupidSort(nums); } }

结果：

"C:\Program Files\Java\jdk1.8.0_131\bin\java.exe"... 用小数据测试一下排序代码的正确性： 输入数组要测试的数组长度； 20 随机生成的数组为： [53, 82, 88, 47, 55, 4, 86, 38, 88, 0, 38, 51, 60, 70, 42, 32, 77, 40, 73, 38] 输入数组为：[53, 82, 88, 47, 55, 4, 86, 38, 88, 0, 38, 51, 60, 70, 42, 32, 77, 40, 73, 38] 插入排序结果： [0, 4, 32, 38, 38, 38, 40, 42, 47, 51, 53, 55, 60, 70, 73, 77, 82, 86, 88, 88] 输入数组为：[53, 82, 88, 47, 55, 4, 86, 38, 88, 0, 38, 51, 60, 70, 42, 32, 77, 40, 73, 38] 合并排序结果： [0, 4, 32, 38, 38, 38, 40, 42, 47, 51, 53, 55, 60, 70, 73, 77, 82, 86, 88, 88] 输入数组为：[53, 82, 88, 47, 55, 4, 86, 38, 88, 0, 38, 51, 60, 70, 42, 32, 77, 40, 73, 38] 快速排序结果： [0, 4, 32, 38, 38, 38, 40, 42, 47, 51, 53, 55, 60, 70, 73, 77, 82, 86, 88, 88] 输入数组为：[53, 82, 88, 47, 55, 4, 86, 38, 88, 0, 38, 51, 60, 70, 42, 32, 77, 40, 73, 38] 侏儒排序结果： [0, 4, 32, 38, 38, 38, 40, 42, 47, 51, 53, 55, 60, 70, 73, 77, 82, 86, 88, 88] Process finished with exit code 0

测试通过，输入的数组都是一样的，排序结果也一样，没啥问题。

接下来分别生成1000、10000、100000个随机数来比较各个排序方法所需要的运行时间。

（把排序里面的输出部分的代码注释掉了）

import java.util.Scanner; /** * @author SJ * @date 2020/10/14 */ public class TestPerformance { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (true) { System.out.println("请输入随机生成的数组长度："); int i = scanner.nextInt(); int[] nums = RandomUtil.generateRandomNum(i); long start = System.currentTimeMillis(); SortCompare.insertSort(nums); long end = System.currentTimeMillis(); System.out.println("插入排序用时：" + (end - start) + "毫秒"); SortCompare sortCompare = new SortCompare(i); long start2 = System.currentTimeMillis(); SortCompare.mergeSort(nums); long end2 = System.currentTimeMillis(); System.out.println("合并排序用时：" + (end2 - start2) + "毫秒"); long start3 = System.currentTimeMillis(); SortCompare.quickSortUtil(nums); long end3 = System.currentTimeMillis(); System.out.println("快速排序用时：" + (end3 - start3) + "毫秒"); long start4 = System.currentTimeMillis(); SortCompare.stupidSort(nums); long end4 = System.currentTimeMillis(); System.out.println("侏儒排序用时：" + (end4 - start4) + "毫秒"); } } }

结果：

"C:\Program Files\Java\jdk1.8.0_131\bin\java.exe"... 请输入随机生成的数组长度： 1000 插入排序用时：5毫秒 合并排序用时：0毫秒 快速排序用时：1毫秒 侏儒排序用时：7毫秒 请输入随机生成的数组长度： 10000 插入排序用时：26毫秒 合并排序用时：5毫秒 快速排序用时：2毫秒 侏儒排序用时：94毫秒 请输入随机生成的数组长度： 100000 插入排序用时：1423毫秒 合并排序用时：12毫秒 快速排序用时：9毫秒 侏儒排序用时：6918毫秒 请输入随机生成的数组长度： 1000000

当数据量级达到100万的时候，因为先跑的是插入排序，所以我的电脑没反应了…一直在计算（我不想等就直接退出了），可见插入排序面对大量数据效率很低。

再测一组：

"C:\Program Files\Java\jdk1.8.0_131\bin\java.exe" ... 请输入随机生成的数组长度： 1000 插入排序用时：4毫秒 合并排序用时：1毫秒 快速排序用时：0毫秒 侏儒排序用时：6毫秒 请输入随机生成的数组长度： 10000 插入排序用时：21毫秒 合并排序用时：3毫秒 快速排序用时：2毫秒 侏儒排序用时：93毫秒 请输入随机生成的数组长度： 100000 插入排序用时：1418毫秒 合并排序用时：11毫秒 快速排序用时：9毫秒 侏儒排序用时：6395毫秒 请输入随机生成的数组长度：

二. 快排的实现步骤

private static int count=0; private static void quicksort(int[] nums, int low, int high){ ... //在递归开始之前添了一句话 System.out.println("第"+(++count)+"趟基准数为："+base+",排序结果为:"+Arrays.toString(nums)); ... }

测试：

import java.util.Arrays; /** * @author SJ * @date 2020/10/14 */ public class TestQuickSort { public static void main(String[] args) { int[] nums=RandomUtil.randomBetween100(10); System.out.println("生成的随机数组为："+ Arrays.toString(nums)); SortCompare.quickSortUtil(nums); } }

结果：

"C:\Program Files\Java\jdk1.8.0_131\bin\java.exe" 生成的随机数组为：[24, 95, 7, 96, 33, 62, 34, 11, 72, 92] 第1趟基准数为：24,排序结果为:[11, 7, 24, 96, 33, 62, 34, 95, 72, 92] 第2趟基准数为：11,排序结果为:[7, 11, 24, 96, 33, 62, 34, 95, 72, 92] 第3趟基准数为：7,排序结果为:[7, 11, 24, 96, 33, 62, 34, 95, 72, 92] 第4趟基准数为：96,排序结果为:[7, 11, 24, 92, 33, 62, 34, 95, 72, 96] 第5趟基准数为：92,排序结果为:[7, 11, 24, 72, 33, 62, 34, 92, 95, 96] 第6趟基准数为：72,排序结果为:[7, 11, 24, 34, 33, 62, 72, 92, 95, 96] 第7趟基准数为：34,排序结果为:[7, 11, 24, 33, 34, 62, 72, 92, 95, 96] 第8趟基准数为：33,排序结果为:[7, 11, 24, 33, 34, 62, 72, 92, 95, 96] 第9趟基准数为：62,排序结果为:[7, 11, 24, 33, 34, 62, 72, 92, 95, 96] 第10趟基准数为：95,排序结果为:[7, 11, 24, 33, 34, 62, 72, 92, 95, 96] [7, 11, 24, 33, 34, 62, 72, 92, 95, 96] Process finished with exit code 0

三.改为逆序

所有改的地方都做了标注

import java.util.Arrays; /** * @author SJ * @date 2020/10/14 */ public class ReverseSort { //插入排序 public static void insertSort(int[] test) { int[] nums = Arrays.copyOf(test, test.length); for (int i = 1; i < nums.length; i++) { int current = nums[i]; int preIndex = i - 1; //current < nums[preIndex]改成大于 while (preIndex >= 0 && current > nums[preIndex]) { nums[preIndex + 1] = nums[preIndex]; preIndex--; } nums[preIndex + 1] = current; } System.out.println(Arrays.toString(nums)); } //归并排序 private static int[] temp; public ReverseSort(int length) { temp = new int[length]; } private static void merge(int[] nums, int left, int right) { ; for (int i = left; i <= right; i++) { temp[i] = nums[i]; } int middle = (left + right) / 2; int l = left; int r = middle + 1; for (int i = left; i <= right; i++) { if (l == middle + 1 && r < right + 1) nums[i] = temp[r++]; else if (r == right + 1 && l < middle + 1) nums[i] = temp[l++]; //temp[l] <= temp[r] else if (temp[l] >= temp[r]) nums[i] = temp[l++]; else { nums[i] = temp[r++]; } } } private static void Sort(int[] nums, int left, int right) { if (left < right) { Sort(nums, left, (left + right) / 2); Sort(nums, (left + right) / 2 + 1, right); merge(nums, left, right); } } public static void mergeSort(int[] test) { int[] nums = Arrays.copyOf(test, test.length); Sort(nums, 0, nums.length - 1); System.out.println(Arrays.toString(nums)); } //快速排序 private static int count=0; private static void quicksort(int[] nums, int low, int high) { int base = nums[low]; int l = low; int h = high; while (l < h) { //nums[h] >= base 改成<= while (l < h && nums[h] <= base) h--; //nums[h]<base 改成> if (nums[h]>base) nums[l++] = nums[h]; //nums[l] <= base 改成>= while (l < h && nums[l] >= base) l++; //nums[l]>base 改成< if (nums[l] < base) nums[h--] = nums[l]; } nums[l] = base; if (low<l) quicksort(nums, low, l - 1); if (high>h) quicksort(nums, l + 1, high); } public static void quickSortUtil(int[] test) { int[] nums = Arrays.copyOf(test, test.length); quicksort(nums, 0, nums.length - 1); System.out.println(Arrays.toString(nums)); } //侏儒排序 public static void stupidSort(int[] test) { int[] nums = Arrays.copyOf(test, test.length); int pos = 0; while (pos < nums.length) { //nums[pos] >= nums[pos - 1] 改成<= if (pos == 0 || nums[pos] <= nums[pos - 1]) pos++; else { int temp = nums[pos];//辅助空间就要这一个temp nums[pos] = nums[pos - 1]; nums[pos - 1] = temp; pos--; } } System.out.println(Arrays.toString(nums)); } }

测试：

import java.util.Arrays; /** * @author SJ * @date 2020/10/14 */ public class TestReverse { public static void main(String[] args) { int[] nums=RandomUtil.randomBetween100(10); System.out.println("随机生成的数组为："+ Arrays.toString(nums)); System.out.println("插入："); ReverseSort.insertSort(nums); System.out.println("归并："); ReverseSort reverseSort = new ReverseSort(10); ReverseSort.mergeSort(nums); System.out.println("快速："); ReverseSort.quickSortUtil(nums); System.out.println("侏儒："); ReverseSort.stupidSort(nums); } }

测试结果：

"C:\Program Files\Java\jdk1.8.0_131\bin\java.exe" ... 随机生成的数组为：[69, 57, 89, 83, 29, 17, 66, 91, 21, 76] 插入： [91, 89, 83, 76, 69, 66, 57, 29, 21, 17] 归并： [91, 89, 83, 76, 69, 66, 57, 29, 21, 17] 快速： [91, 89, 83, 76, 69, 66, 57, 29, 21, 17] 侏儒： [91, 89, 83, 76, 69, 66, 57, 29, 21, 17] Process finished with exit code 0

四.稳定性

排序算法的稳定性是指在待排序的序列中，存在多个相同的元素，若经过排序后这些元素的相对词序保持不变，即$x_m=x_n$，排序前m在n前，排序后m依然在n前，则称此时的排序算法是稳定的。

插入排序：

从插入排序可以看出，其原理是在一个已经排好序的序列中依次插入一个新的元素。如果碰到相等的元素，就把新元素插入相等元素的后面，即他们原来的顺序没有变化，因此插入排序是稳定的。

如果line20改成

while (preIndex >= 0 && current <= nums[preIndex])

则不稳定。

合并排序：

从归并算法可以看出，其原理是将待排序列递归地划分为短序列，直到每部分都只包含一个元素，然后再合并，合并时如果两个元素相等也会按照元素之前的顺序，把下标小的元素先放入结果列表中，依然没有破环相同元素之间原本的顺序，因此归并算法也是稳定的。

如果line61改成

else if (temp[l] < temp[r])

则不稳定

快速排序：

快速排序是不稳定的，如“ 5 3 3 4 3 8 9 10 11”第一次切分，主元5要和元素3交换，即改变了3和另两个相等元素之间的顺序。

侏儒排序：

前面的数字比自己大才交换位置，相等的话不交换。

如果line147改成

if (pos == 0 || nums[pos] > nums[pos - 1])

则不稳定。

五.空间性能

插入：O（1）

归并：O(n)

快速：在递归调用前，仅会使用固定的额外空间。然而，如果需要产生$O(nlgn)$嵌套递归调用，它需要在他们每一个存储一个固定数量的信息。因为最好的情况最多需要$O(lgn)$次的嵌套递归调用，所以它需要$O(lgn)$的空间。最坏情况下需要$O(n)$次嵌套递归调用，因此需要$O(n)$的空间。

侏儒：O(1)

内容二 众数问题

**在一个包含n个元素的多重集合S中，每个 元素在S中出现的次数称为该元素的重数， 多重集合S中重数最大的元素称为众数

举例来说，多重集合S={1,2,3,3,3,3,4,4,5}, 则多重集合S的众数是3，元素3的重数为4

现要求对随机生成的由n个自然数组成的 多重集合S, 编程计算S的众数及其重数

思路：

排序（调用系统中的排序算法，效率较高，自己写的话可以用归并）如果某个数字为众数，那么排序后他会占主体部分，所以用index定位到中间是又很大概率能找到，假设找打的数为a左右扫描，找出该数字的左右边界下边，就是这一堆a左边到哪，右边到哪，并计算该数字的重数，并将它初始化为Mode，以后找到重数更多的遍覆盖掉它分治，计算a左走两边数组的长度（不含a），如果长度都比a的重数少就可以确定里面肯定没有众数，如果长度比a大就递归步骤3

产生随机数我们还是调用上面编写的工具类，不过把产生随机数的范围改成0-20；

public static int[] randomBetween100(int length){ int[] nums=new int[length]; for (int i = 0; i < nums.length; i++) { nums[i]=(int)(Math.random()*20); } return nums; } import java.util.Arrays; /** * @author SJ * @date 2020/10/10 */ public class FindMode { public static void main(String[] args) { int[] nums = RandomUtil.randomBetween100(30); System.out.println("生成的随机数组为："+Arrays.toString(nums)); findMode(nums); } public static void findMode(int[] nums) { Arrays.sort(nums); Mode mode = fun(nums, 0, nums.length - 1); System.out.println("众数是：" + mode.value + "重数是：" + mode.num); } public static Mode fun(int[] nums, int left, int right) { int index = (right + left) / 2; int leftbound = findLeftIndex(nums, index, 0); int rightbound = findRightIndex(nums, index, right); //初始化一个众数对象（也有可能不是，后期找到更好的值回把它覆盖掉），value是中间那个数，重数也是中间那个数的重数 int middleNums = rightbound - leftbound + 1; Mode currentMode = new Mode(nums[index], middleNums); //这就将整个数组分成了三段，中间众数段，众数左边那段，和众数右边那段 //如果众数左边那段的长度还不如当前众数的重数大，那么众数肯定不在里面 //如果比当前的重数大，就进去找找 if ((leftbound - left) > middleNums && left < leftbound) { int temp = fun(nums, left, leftbound - 1).num; //如果找到的新的更优质的众数，就覆盖原来的 if (temp > middleNums) { currentMode.num = temp; currentMode.value = fun(nums, left, leftbound - 1).value; } } if ((right - rightbound) > currentMode.num && rightbound < right) { int temp; temp = fun(nums, rightbound + 1, right).num; if (temp > middleNums) { currentMode.num = temp; currentMode.value = fun(nums, rightbound + 1, right).value; } } return currentMode; } public static int findLeftIndex(int[] nums, int index, int left) { int leftBound = index; for (int i = index - 1; i >= left; i--) { if (nums[i] == nums[index]) leftBound = i; else break; } return leftBound; } public static int findRightIndex(int[] nums, int index, int right) { int rightBound = index; for (int i = index + 1; i <= right; i++) { if (nums[i] == nums[index]) rightBound = i; else break; } return rightBound; } //众数，有两个属性，一个是值，一个是重数 public static class Mode { public int value; public int num = 0; public Mode(int value, int num) { this.value = value; this.num = num; } } }

测试结果：

"C:\Program Files\Java\jdk1.8.0_131\bin\java.exe" ... 生成的随机数组为：[3, 5, 19, 17, 5, 16, 11, 1, 11, 9, 10, 2, 10, 12, 1, 6, 14, 7, 10, 11, 15, 10, 10, 5, 10, 1, 13, 16, 10, 12] 众数是：10重数是：7 Process finished with exit code 0

时间复杂度，1.花在排序上，调的系统的排序算法，复杂度不会超过$O(nlgn)$ ,具体没研究过。

​ 2.递归的深度最差是$O(lgn)$，每次都是线性时间左右扫描

空间复杂度：new Mode对象上了，不过就new了一次，没有用到额外的数组

内容三 最近点对

对平面上给定的N个点，给出所有点对的最短距离

即，输入是平面上的N个点，输出是N点中具有最短距离的两点

要求随机生成N个点的平面坐标，应用穷举法编程计算出所有点对的最短距离

要求随机生成N个点的平面坐标，应用分治法编程计算出所有点对的最短距离

穷举法：两层循环，枚举出平面上所有点对的距离，得到最小的,时间复杂度 $O(n^2)$，辅助空间$O(1)$

分治法：按x轴排序，先大致分成两半找，假设中心点是A（$x_0,y_0$）假设两边找到的最小距离是d，那么中间交叉的部分在距离$x=x_0-d$、与$x=x_0+d$ 这两条垂线中间找（此时按y轴排序用穷举法)。至于为什么，详见http://www.360doc.com/content/19/0303/18/32937624_818850914.shtml

触底：所划分的区域内有不大于3个点。

import java.util.*; /** * @author SJ * @date 2020/10/14 */ public class FindShortestDistance { static class Point { private Integer x; private Integer y; public Point(int x, int y) { this.x = x; this.y = y; } //计算两点之间距离 public int getDistance(Point a){ return (int) (Math.pow((this.x-a.x),2)+Math.pow((this.y-a.y),2)); } @Override public String toString() { return "(" + x + ", " + y + ')'; } } //生成num个随机点放在list内 public static List<Point> generateRandomPoint(int num){ List<Point> list=new ArrayList<>(); int[] xs=RandomUtil.randomBetween100(num); int[] ys=RandomUtil.randomBetween100(num); for (int i = 0; i < num; i++) { list.add(new Point(xs[i], ys[i])) ; } return list; } //穷举法 public static double findShortestDistance(List<Point> points){ //将最短距离初始化为list中第0个点和第一个点之间的距离 int distance= points.get(0).getDistance(points.get(1)); for (int i = 0; i < points.size(); i++) { for (int j = i+1; j <points.size() ; j++) { //list内下标为i的点与下标为j的点之间的距离 int tempDistance=points.get(i).getDistance(points.get(j)); if (tempDistance<distance){ distance=tempDistance; } } } return Math.sqrt(distance); } //list排序 public static void sortByX(List<Point> points) { Collections.sort(points, new Comparator<Point>() { @Override public int compare(Point o1, Point o2) { return o1.x.compareTo(o2.x); } }); } private static void sortByY(List<Point> points) { Collections.sort(points, new Comparator<Point>() { @Override public int compare(Point o1, Point o2) { return o1.y.compareTo(o2.y); } }); } //分治法 public static double findShortestDistance2(List<Point> points,int low,int high){ //只剩两个点 if (high-low==1) return Math.sqrt(points.get(high).getDistance(points.get(low))); //还剩3个点 else if (high-low==2){ double a=Math.sqrt(points.get(low).getDistance(points.get(low+1))); double b=Math.sqrt(points.get(low+1).getDistance(points.get(high))); double c=Math.sqrt(points.get(low).getDistance(points.get(high))); return Math.min(Math.min(a,b),c); } else { int mid=(low+high)/2; double leftMin=findShortestDistance2(points,low,mid); double rightMin=findShortestDistance2(points,mid+1,high); double min=Math.min(leftMin,rightMin); //重点来了 //1.找到横坐标与中点横坐标距离在min以内的的点，不包括min List<Point> candidate=new ArrayList<>(); for (int i = low; i <=high; i++) { if (Math.abs(points.get(i).x-points.get(mid).x)<min) candidate.add(points.get(i)); } //找出这些点后根据纵坐标排序 sortByY(candidate); //在这个小范围内用穷举法 for (int i = 0; i < candidate.size(); i++) { for (int j = i+1; j <candidate.size(); j++) { if ((candidate.get(j).y-candidate.get(i).y)>min) break; double temp=Math.sqrt(candidate.get(j).getDistance(candidate.get(i))); if (temp<min) min=temp; } } return min; } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.println("输入点的数目："); int num = scanner.nextInt(); //生成num个随机点存在pointList中 List<Point> pointList=generateRandomPoint(num); System.out.println("生成的随机点对为："); for (Point point : pointList) { System.out.print(point+" "); } System.out.println(); //使用穷举法计算 double shortestDistance = findShortestDistance(pointList); System.out.println("穷举所得最短距离为："+shortestDistance); //使用分治法计算 sortByX(pointList); double shortestDistance2 = findShortestDistance2(pointList, 0, pointList.size() - 1); System.out.println("分治法所得最短距离为："+shortestDistance2); } }

测试结果：

"C:\Program Files\Java\jdk1.8.0_131\bin\java.exe"... 输入点的数目： 10 生成的随机点对为： (12, 1) (3, 11) (12, 8) (10, 7) (14, 6) (3, 18) (1, 8) (9, 18) (15, 14) (5, 11) 穷举所得最短距离为：2.0 分治法所得最短距离为：2.0 Process finished with exit code 0

复杂度分析：分治法：取决于选择的排序算法，我用的是Java提供的Collections.sort()，其内部采取的是归并排序,时间复杂度是$O(nlogn)$。递归，区间深度不超过$O(logn)$.总得来说时间复杂度$O(nlogn)$。

除了存对象用的List，辅助空间还有计算交叉部分的距离时用的list，下面这里。

内容四 子序列最大和

给出一个整数序列，选出其中连续且非空的一段使得这段和最大

要求：使用分治法解决

思路：

我们来分析一下这个问题， 我们先把数组平均分成左右两部分。

此时有三种情况：

最大子序列全部在数组左部分最大子序列全部在数组右部分最大子序列横跨左右数组

对于前两种情况，我们相当于将原问题转化为了规模更小的同样问题。

横跨左右数组的用枚举法：左边的选择从middle-1开始挨着盘得往左累加，把最累加最大得结果记下来；

右边的从middle+1开始也是同样的方法。最后三个部分加起来就是第三中情况的结果。

随机数还是调用那个类，范围从-25到+25

public static int[] randomBetween100(int length){ int[] nums=new int[length]; for (int i = 0; i < nums.length; i++) { nums[i]=(int)(Math.random()*(-50)+25); } return nums; } import java.util.Arrays; import java.util.Scanner; /** * @author SJ * @date 2020/10/14 */ public class MaxSum { public static int findMaxSum(int[] nums, int left, int right) { //只剩一个数字 if (right == left) return nums[left]; //只剩两个值 else if (right - left == 1) { return Math.max(Math.max(nums[left], nums[right]), (nums[right] + nums[left])); } int mid = (left + right) / 2; //左边序列最大和 int leftMax = findMaxSum(nums, left, mid - 1); //右边序列最大和 int rightMax = findMaxSum(nums, mid + 1, right); //找交叉项 int rightSum = 0; int tempRightMax = nums[mid + 1]; for (int i = mid + 1; i <= right; i++) { rightSum += nums[i]; if (rightSum > tempRightMax) tempRightMax = rightSum; } int leftSum = 0; int tempLeftMax = nums[mid - 1]; for (int i = mid - 1; i >= left; i--) { leftSum += nums[i]; if (leftSum > tempRightMax) tempLeftMax = leftSum; } //跨界序列最大和 int middleMax = tempLeftMax + nums[mid] + tempRightMax; return Math.max(Math.max(leftMax, rightMax), middleMax); } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (true) { System.out.println("输入点序列长度："); int length = scanner.nextInt(); int[] nums = RandomUtil.randomBetween100(length); System.out.println("生成的随机序列为：" + Arrays.toString(nums)); int max = findMaxSum(nums, 0, nums.length - 1); System.out.println("最大和为：" + max); } } }

结果：

"C:\Program Files\Java\jdk1.8.0_131\bin\java.exe"... 输入点序列长度： 5 生成的随机序列为：[0, 15, -4, 19, 7] 最大和为：37 输入点序列长度： 6 生成的随机序列为：[12, 23, -7, 10, -12, -11] 最大和为：38 输入点序列长度： 7 生成的随机序列为：[2, 9, 19, 3, 23, 0, 8] 最大和为：53 输入点序列长度： 10 生成的随机序列为：[-18, 17, 24, 12, -4, 20, 4, -5, 19, -20] 最大和为：87 输入点序列长度：

时间复杂度为 $O(nlgn)$, 空间复杂度为 $O(1)$

内容五 快速幂问题

题目描述：

输入正整数𝑥, 𝑝 (𝑥 ≤ 10^9 , 𝑝 ≤ 10^18)

要求输出 $x^{p}mod(10^9+7)$

样例输入 3 5

样例输出 243

拓展1

基本数据类型的特点，最大值和最小值。 1、 基本类型：int 二进制位数：32 包装类：java.lang.Integer 最小值：Integer.MIN_VALUE= -2147483648 （-2的31次方） 最大值：Integer.MAX_VALUE= 2147483647 （2的31次方-1） 2、 基本类型：short 二进制位数：16 包装类：java.lang.Short 最小值：Short.MIN_VALUE=-32768 （-2的15此方） 最大值：Short.MAX_VALUE=32767 （2的15次方-1） 3、 基本类型：long 二进制位数：64 包装类：java.lang.Long 最小值：Long.MIN_VALUE=-9223372036854775808 （-2的63次方） 最大值：Long.MAX_VALUE=9223372036854775807 （2的63次方-1）

4、

基本类型：float 二进制位数：32 包装类：java.lang.Float 最小值：Float.MIN_VALUE=1.4E-45 （2的-149次方） 最大值：Float.MAX_VALUE=3.4028235E38 （2的128次方-1） 5、 基本类型：double 二进制位数：64 包装类：java.lang.Double 最小值：Double.MIN_VALUE=4.9E-324 （2的-1074次方） 最大值：Double.MAX_VALUE=1.7976931348623157E308 （2的1024次方-1）

int和long只能写10个数字，short只能写5个数字，多了就会报错。

float的小数点后6位，double的小数点后16位。

拓展2

参考：https://www.geeksforgeeks.org/modulo-1097-1000000007/

为什么需要取模：

采用Mod的原因是为了防止整数溢出。C / C ++中最大的整数数据类型是64位无符号long long int，可以处理从0到（2 ^ 64 – 1）的整数。但是在某些问题中，产出增长率非常高，这种高范围的无符号长久可能不足。 假设在64位变量’A’中存储2 ^ 62，在另一个64位变量’B’中存储2 ^ 63。当我们将A和B相乘时，系统不会给出运行时错误或异常。它只是进行一些伪计算并存储伪结果，因为结果的位大小是在乘法溢出后得出的。

在某些问题中，需要计算模逆的结果，并且该数字很有用，因为它是质数。同样，这个数字应该足够大，否则在某些情况下模块化逆向技术可能会失败。

由于这些原因，问题解决者需要通过对一些数N取模来给出答案。 N的值取决于某些标准：

它应该足够大以适合最大的整数数据类型，即确保没有结果溢出。它应该是质数，因为如果我们将一个数的mod乘以质数，则结果通常是隔开的，即与非质数的mod数相比，结果是非常不同的结果，这就是质数通常用于mod的原因。

10 ^ 9 + 7满足这两个条件。它是第一个10位数的质数，也适合int数据类型。实际上，任何小于2 ^ 30的质数都可以，以防止可能的溢出。

模数的使用方式：模数 的一些分布特性如下：

（a + b）％c =（（a％c）+（b％c））％c（a * b）％c =（（a％c）*（b％c））％c（a – b）％c =（（a％c）–（b％c））％c（a / b）％c =（（a％c）/（b％c））％c

因此，模是分布在+，*和–上，而不是分布在/上。[有关详细信息，请参阅模数除法] 注意：（a％b）的结果将始终小于b。 在计算机程序的情况下，由于变量限制的大小，我们**在每个中间阶段执行模M，**这样就不会发生范围溢出。

例： 一个= 145785635595363569532135132 b = 3151635135413512165131321321 c = 999874455222222200651351351 m = 1000000007 打印（a * b * c）％m。 方法1： 首先，将所有数字相乘，然后取模： （a * b * c）％m =（459405448184212290290339339835148809 515332440033400818566717735644307024625348601572）％ 1000000007 a * b * c即使在unsigned long long中也不适合 int由于哪个系统掉了大部分 有效数字。因此，它给出了错误的答案。 （a * b * c）％m = 798848767 方法2： 在每个中间步骤取模： 我= 1 i =（i * a）％m // i = 508086243 i =（i * b）％m // i = 144702857 i =（i * c）％m // i = 798848767 我= 798848767 方法2总是给出正确的答案。

拓展3

从效率上看，使用移位指令有更高的效率，因为移位指令占2个机器周期，而乘除法指令占4个机器周期。从硬件上看，移位对硬件更容易实现，所以会用移位，移一位就乘2,这种乘法当然考虑移位了。

位移运算：https://www.jianshu.com/p/927009730809

拓展4

快速幂问题：https://oi-wiki.org/math/quick-pow/

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bwOqgmr4-1603267560977)(C:\Users\admin\AppData\Roaming\Typora\typora-user-images\image-20201015094014653.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QZP0RKP8-1603267560982)(C:\Users\admin\AppData\Roaming\Typora\typora-user-images\image-20201015094014653.png)]

思路：计算$x^p$与mod同时操作

import java.util.Scanner; /** * @author SJ * @date 2020/10/15 */ public class CalculateMod { public static final int MODULE = 1000000007; //x^p x是int，p的范围是long public static long calculate(long x, long p) { x = Math.floorMod(x, MODULE); long res = 1L; for (; p != 0; p >>= 1) { //判断改二进制位上的数组是否为1 ，如过为1就乘上系数 if ((p & 1) != 0) res = Math.floorMod(res * x, MODULE); //不为1就自乘 x = x * x; x = Math.floorMod(x, MODULE); } return res; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); long x = scanner.nextLong(); long p = scanner.nextLong(); long calculate = calculate(x, p); System.out.println(calculate); } }

结果：

"C:\Program Files\Java\jdk1.8.0_131\bin\java.exe"... 3 5 243 Process finished with exit code 0

算法复杂度,我们只需要计算$O(logn)$次乘法，空间$O(1)$

内容六

思路：像这种一对一对的东西首先想到了合并排序，因为合并排序合并的过程就遍历了所有的数对。现在只要判断是否存在一个和为S的数对就行。

分成子问题后，有序了，可以用二分搜索查找。

import java.util.Arrays; import java.util.Scanner; /** * @author SJ * @date 2020/10/15 */ public class HasSum { public HasSum(int length) { temp=new Integer[length]; } public static Integer[] temp ; public static boolean merge(int[] nums, int left, int right, int sum) { for (int i = left; i <= right; i++) { temp[i] = nums[i]; } int middle = (left + right) / 2; int l = left; int r = middle + 1; for (int i = left; i <= right; i++) { //左边合并完成，右边还有剩余 if (l == middle + 1 && r < right + 1) nums[i] = temp[r++]; //右边合并完成，左边还有剩余 else if (r == right + 1 && l < middle + 1) nums[i] = temp[l++]; else if (temp[l] <= temp[r]) { nums[i] = temp[l++]; //用二分搜索 int index = Arrays.binarySearch(temp, r, right, sum - nums[i]); if (index >= 0) { // System.out.println(nums[i] + "," + temp[index]); return true; } } else { nums[i] = temp[r++]; int index = Arrays.binarySearch(temp, l, middle, sum - nums[i]); if (index >= 0) { // System.out.println(nums[i] + "," + temp[index]); return true; } } } return false; } public static boolean mergeSort(int[] nums, int left, int right, int sum) { boolean leftCount = false; boolean rightCount = false; boolean mix = false; if (left == right) return false; else if (left < right) { leftCount = mergeSort(nums, left, (left + right) / 2, sum); rightCount = mergeSort(nums, (left + right) / 2 + 1, right, sum); mix = merge(nums, left, right, sum); } return leftCount || rightCount || mix; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int length = scanner.nextInt(); new HasSum(length); int[] nums = new int[length]; // int[] nums={3,5,7,2,1}; int sum = scanner.nextInt(); for (int i = 0; i < length; i++) { nums[i] = scanner.nextInt(); } boolean b = mergeSort(nums, 0, nums.length - 1, sum); if (b) System.out.println("YES"); else System.out.println("NO"); } }

结果：

"C:\Program Files\Java\jdk1.8.0_131\bin\java.exe"... 5 7 3 6 7 2 1 YES Process finished with exit code 0

inarySearch(temp, l, middle, sum - nums[i]); if (index >= 0) { // System.out.println(nums[i] + “,” + temp[index]); return true; }

} } return false; } public static boolean mergeSort(int[] nums, int left, int right, int sum) { boolean leftCount = false; boolean rightCount = false; boolean mix = false; if (left == right) return false; else if (left < right) { leftCount = mergeSort(nums, left, (left + right) / 2, sum); rightCount = mergeSort(nums, (left + right) / 2 + 1, right, sum); mix = merge(nums, left, right, sum); } return leftCount || rightCount || mix; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int length = scanner.nextInt(); new HasSum(length); int[] nums = new int[length];

// int[] nums={3,5,7,2,1}; int sum = scanner.nextInt(); for (int i = 0; i < length; i++) { nums[i] = scanner.nextInt(); } boolean b = mergeSort(nums, 0, nums.length - 1, sum); if (b) System.out.println(“YES”); else System.out.println(“NO”);

}

}

结果： ```java "C:\Program Files\Java\jdk1.8.0_131\bin\java.exe"... 5 7 3 6 7 2 1 YES Process finished with exit code 0

时间复杂度$O(nlgn)$ 空间O(n)