# 经典算法合集一
----
## 选择排序
```java
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 0 ~ N-1 找到最小值，在哪，放到0位置上
// 1 ~ n-1 找到最小值，在哪，放到1 位置上
// 2 ~ n-1 找到最小值，在哪，放到2 位置上
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;//minIndex指示的位置就是第几小的数该放的位置
for (int j = i + 1; j < arr.length; j++) { // i ~ N-1 上找最小值的下标
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
```
## 冒泡排序
```java
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
//冒泡排序是每次将最大的数放在数组末尾
// 0 ~ N-1
// 0 ~ N-2
// 0 ~ N-3
for (int e = arr.length - 1; e > 0; e--) { // 0 ~ e
//e代表结尾位置，每次进行更新
for (int i = 0; i < e; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
}
}
}
}
// 交换arr的i和j位置上的值
public static void swap(int[] arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
//实例解析
//arr[i] = 3, arr[j] = 7
//arr[i] = arr[i] ^ arr[j]; arr[i] = 3 ^ 7
//arr[j] = arr[i] ^ arr[j]; arr[j] = (3 ^ 7) ^ 7 = 3
//arr[i] = arr[i] ^ arr[j]; arr[i] = (3 ^ 7) ^ 3 = 7
//最终 arr[i] = 7, arr[j] = 3
//注意异或运算满足交换律和结合律
}
```
----
# 高精度阶乘：
## 1、代码如下：
```css
import java.util.Scanner;
public class LargeIntegerFactorial {
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
long[] ans = new long[10001000];
long n = sc.nextLong();
ans[0] = 1;
int l = 0;
long num = 0;
for(int i = 1; i<=n;++i)
{
num = 0;
for(int j = 0; j <= l; j++)
{
num = num + ans[j] * i;
ans[j] = num % 10;
num /= 10;
}
while(num != 0)
{
ans[++l] =num % 10;
num /= 10;
}
}
for(int i = l; i >= 0; --i)
{
System.out.print(ans[i]);
}
return;
}
}
```
## 2、代码解析如下：
```css
我们接下来把n设置为4，进行代码的实例演示以及解析
{
long[] ans = new long[10001000];//定义答案数组
n = 4;//设置指定数字为4
ans[0] = 1; //将答案数组的第一位设置为1
int l = 0;//定义变量l，用来记录n！的数字有多少位
long num = 0;//定义变量num
for(int i = 1; i<=n;++i)//核心代码，将在下边进行实例解析
{
num = 0;
for(int j = 0; j <= l; j++)
{
num = num + ans[j] * i;
ans[j] = num % 10;
num /= 10;
}
while(num != 0)
{
ans[++l] =num % 10;
num /= 10;
}
}
```
> {
>
> 当i == 1时，j == 0， j <= l (0 <= 0), num = 0;
> num = num + ans[0] * i = 0 + 1 * 1 = 1;
> ans[0] = num % 10 = 1 % 10 = 1;
> num = num / 10 = 1 / 10 = 0;
> 当i == 2时，j == 0，j <= l (0 <= 0),num = 0;
> num = num + ans[0] * i = 0 + 1 * 2 = 2;
> ans[0] = num % 10 = 2 % 10 = 2;
> num = num / 10 = 2 / 10 = 0;
> 当i == 3时，j == 0，j <= l (0 <= 0),num = 0;
> num = num + ans[0] * i = 0 + 2 * 3 = 6;
> ans[0] = num % 10 = 6 % 10 = 6;
> num = num / 10 = 6 / 10 = 0;
> 当i == 4时，j == 0，j <= l (0 <= 0),num = 0;
> num = num + ans[0] * i = 0 + 6 * 4 = 24;
> ans[0] = num % 10 = 24 % 10 = 4;
> num = num / 10 = 24 / 10 = 2;
> 进入while循环，
> num = 2 != 0;
> ans[++l] = num % 10 = 2 % 10 = 2;(此时l == 1);
> ans[1] = 2;
> num = num / 10 = 2 / 10 = 0;
> 当i == 5时，j == 0，j <= l (0 <= 1),num = 0;
> num = num + ans[0] * i = 0 + 4 * 5 = 20;
> ans[0] = num % 10 = 20 % 10 = 0;
> num = num / 10 = 2;
> 当i == 5时，j == 1，j <= l (1 <= 1),num = 2;
> num = num + ans[1] * i = 2 + 2 * 5 = 12;
> ans[1] = num % 10 = 12 % 10 = 2;
> num = num / 10 = 12 / 10 = 1;
> 进入while循环，
> num = 1 != 0;
> ans[++l] = num % 10 = 1 % 10 = 1;(此时l == 2);
> ans[2] = 1;
> num = num / 10 = 0;
> 结束。
> }
> }
# 100的阶乘的正约数个数
## 解题思路如下：
>首先将100的阶乘求出来，然后进行质因数分解，也就是每次除以质数，在判断该质数用了几次。然后套用公式：n=(p₁^ a₁) * (p₂^ a₂) * (p₃^ a₃)* (p₄ ^ a₄)...
>对于一个大于1正整数n可以分解质因数：n=(p₁^ a₁) * (p₂^ a₂) * (p₃^ a₃)* (p₄ ^ a₄)...
则n的正约数的个数就是(1+a₁)(1+a₂)(1+a₃)(1+a₄)...
假设自然数N等于P的a次乘以q的b次乘以r的C次，P、q、r为不同的质数，则N的约数个数等于（a＋1)*（b＋1）*（C＋1）。
>因数和约数：
约数和因数既有联系，又有区别，这主要表现在以下三个方面。
（1） 约数必须在整除的前提下才存在，而因数是从乘积的角度来提出的。如果数a与数b相乘的积是数c，a与b都是c的因数。
（2） 约数只能对在整数范围内而言，而因数就不限于整数的范围。
例如：6×8=48。既可以说6和8都是48的因数，也可以说6和8都是48的约数。
又如：0.9×8=7.2。虽然可以说0.9和8都是7.2的因数，却不能说0.9和8是7.2的约数。
## 代码如下：
```css
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Scanner;
public class ttt {
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
long[] ans = new long[10001000];
long n = sc.nextLong();
ans[0] = 1;
String str = largeIntegerFactorial(n, ans);
int t = 2;
String mm = "";
int z = 0;
ArrayList chuCun = new ArrayList();
BigInteger a = new BigInteger(str);
while(1 == 1)
{
if(zhiShu(t))
{
mm = mm + t;
if(a.equals(new BigInteger("1")))
{
break;
}
a = a.divide(new BigInteger(mm));
z++;
if(!a.mod(new BigInteger(mm)).equals(new BigInteger("0")))
{
chuCun.add(z+1);//将调用这个质数的次数赋值给集合
z = 0;
t++;
}
mm = "";
}
if(zhiShu(t)==false){
t++;
}
}
BigInteger kk = new BigInteger("1");
String gg = "";
for(int i = 0; i < chuCun.size(); i++)
{
int sss = (int)chuCun.get(i);
gg = gg + sss;
kk = kk.multiply(new BigInteger((gg)));
gg = "";
}
System.out.println(kk);
}
public static boolean zhiShu(int a) {
for(int i=2;i<=a;i++) {
if(i==a) {
return true;
}
if(a%i==0) {
break;
}
}
return false;
}
public static String largeIntegerFactorial(long n, long[] ans)
{
int l = 0;
long num = 0;
for(int i = 1; i<=n;++i)
{
num = 0;
for(int j = 0; j <= l; j++)
{
num = num + ans[j] * i;
ans[j] = num % 10;
num /= 10;
}
while(num != 0)
{
ans[++l] =num % 10;
num /= 10;
}
}
StringBuilder sb = new StringBuilder();
for(int i = l; i >= 0; --i)
{
sb.append(ans[i]);
}
return sb.toString();
}
}
```
暂无评论