「经典算法合集」

# 经典算法合集一

----

## 选择排序

```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();

    }

}

```