算法复习大纲

2023-07-26 22:33:58

JAVA算法复习大纲

JAVA算法复习大纲

JAVA算法复习大纲

排序

选择排序：

5，1，128，96，76，2
（1）1，5，128，96，76，2
（2）1，2，128，96，76，5
（3）1，2，5，96，78，128
（4）1，2，5，78，96，128
（5）1，2，5，78，96，128

选择排序：找到最小的元素，插入到有序区，有序区是没有元素的，插入的时候会交换元素

编程

import java.util.Arrays;

public class xuanzepaixu {
    public static void main(String[] args) {
        int numbs[] = {5,1,128,96,76,2};
        selectionSort(numbs);
        System.out.println(Arrays.toString(numbs));
    }

    public static void selectionSort(int[] numbs){
        for (int i = 0; i < numbs.length-1; i++) {
            int min = i;
            for (int j = i+1; j < numbs.length; j++) {
                if (numbs[j]<numbs[min]){
                    min=j;
                }
            }

            if (i!=min){
                int tmp = numbs[i];
                numbs[i]=numbs[min];
                numbs[min]=tmp;
            }
        }
    }
}

插入排序

123，45，19，23，634，4
（1）45，123，19，23，634，4
（2）19，45，123，23，634，4
（3）19，23，45，123，634，4
（4）19，23，45，123，634，4
（5）4，19，23，45，123，634

插入排序：插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动

编程

import java.util.Arrays;

public class 插入排序 {
    public static void main(String[] args) {
        int numbs[] = {123,45,19,23,634,4};
        InsertionSort(numbs);
        System.out.println(Arrays.toString(numbs));
    }
    public static void InsertionSort(int[] numbs){
        for (int i = 0; i < numbs.length-1; i++) {
            for (int j = i+1; j > 0; j--) {
                if (numbs[j]<numbs[j-1]){
                    int tmp = numbs[j];
                    numbs[j]=numbs[j-1];
                    numbs[j-1]=tmp;
                }
            }
        }
    }
}

冒泡排序

5，1，128，96，76，2

(1) 1,5,96,76,2,128

(2) 1,5,76,2,96,128

(3) 1,5,2,76,96,128

(4) 1,2,5,76,96,128

(5) 1,2,5,76,96,128

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

编程

import java.util.Arrays;

public class 冒泡排序 {
    public static void main(String[] args) {
        int numbs[] = {1,5,96,76,2,128};
        BubbleSort(numbs);
        System.out.println(Arrays.toString(numbs));
    }
    public static void BubbleSort(int[] nums){

        for (int i = 0; i < nums.length-1; i++) {
            for (int j = 0; j < nums.length-1-i; j++) {
                if (nums[j]>nums[j+1]){
                    int tmp = nums[j];
                    nums[j]=nums[j+1];
                    nums[j+1]=tmp;
                }
            }
        }
    }

}

合并排序

假定有 8 个元素，第一步，划分为四对，每一对两个元素，用 merge 算法合并成四个有序的序列；第二步，把四个序列划分成两对，用 merge 算法合并成两个有序的序列；最后，再利用merge算法合并成一个有序的序列。

编程

合并两个有序序列，并返回结果

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 合并排序 {
    public static void main(String[] args) {
        List<Integer> A  = new ArrayList<Integer>();
        A.add(1);
        A.add(3);
        A.add(7);
        A.add(8);
        List<Integer> B  = new ArrayList<Integer>();
        B.add(2);
        B.add(4);
        B.add(5);
        B.add(6);
        List<Integer> C  = merge(A,B);
        System.out.println(C);
    }

    public static List<Integer> merge(List<Integer> A, List<Integer> B){
        List<Integer> C = new ArrayList<>();

        int i=0;
        int j=0;
        int n = A.size();
        int m = B.size();

        while ((i<n)&&(j<m)){
            if (A.get(i)<B.get(j)){
                C.add(A.get(i));
                i++;
            }else{
                C.add(B.get(j));
                j++;
            }
        }

        while (i<n){
            C.add(A.get(i));
            i++;
        }

        while (j<m){
            C.add(B.get(j));
            j++;
        }

        return C;
    }

}

堆建立

4，1，6，3，8，2，10，5，9，11，7

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-z8324APZ-1625552480498)(http://t4king.oss-cn-beijing.aliyuncs.com/uPic/%E5%A0%86%E5%BB%BA%E7%AB%8B(2)].png)

基数排序

例：链表 L 中元素的关键字值分别为：

3097、3673、2985、1358、6138、9135、4782、1367、3684、0139

1. 按关键字中的数字 d1，把 L 中的元素分布到链表情况:

L2	L3	L4	L5	L7	L8	L9
4782	3673	3684	2985	3097	1358	0139
			9135	1367	6138

把 L0 ~L9 的元素顺序链接到 L 后，L 中的元素顺序如下

4782 3673 3684 2985 9135 3097 1367 1358 6138 0139

2. 按关键字中的数字 d2，把 L 中的元素分布到链表情况:

L3	L5	L6	L7	L8	L9
9135	1358	1367	3673	4782	3097
6138				3684
0139				2985

把 L0 ~L9 的元素顺序链接到 L 后，L 中的元素顺序如下
9135 6138 0139 1358 1367 3673 4782 3684 2985 3097

3. 按关键字中的数字 d3，把 L 中的元素分布到链表情况:

L0	L1	L3	L6	L7	L9
3097	9135	1358	3673	4782	2985
	6138	1367	3684
	0139

把 L0 ~L9 的元素顺序链接到 L 后，L 中的元素顺序如下
3097 9135 6138 0139 1358 1367 3673 3684 4782 2985

4. 按关键字中的数字 d4，把 L 中的元素分布到链表情况:

L0	L1	L2	L3	L4	L6	L9
0139	1358	2985	3097	4782	6138	9135
	1367		3673
			3684

把 L0 ~L9 的元素顺序链接到 L 后，L 中的元素顺序如下
0139 1358 1367 2985 3097 3673 3684 4782 6138 9135

Union_Find操作

find(x)：寻找元素 x 所在集合
union(x,y)：把元素 x 和元素 y 所在集合合并成一个集合

Union

利用该数据结构合并两个集合的情况

图 (a) 表示由集合 {1,3,5,8}, {2,7,10}, {4,6}, {9} 所组成的森林
图 (b) 表示由元素 1 所在集合、与元素 7 所在集合合并的情况

该数据结构的缺点
树的高度可能很大，变成退化树，成为线性表

union(x,y)操作：
若 x 和 y 是当前森林中两棵不同树的根结点，
如果 rank(x) > rank(y) 把 x 作为 y 的父亲
如果 rank(x) < rank(y) 把 y 作为 x 的父亲
如果 rank(x) = rank(y) 把 x 作为 y 的父亲，rank(x) + 1

Find

路径压缩

find(x) 操作时，找到 x 的根结点 y 之后，再沿着 x 到 y 的路径，改变路径上所有结点的父指针，使其直接指向 y

(a) 表示集合 {1,2,3,4}, {5,6,7,8}

b) 表示执行 union(4,6) 之后的结果

递归

阶层

计算阶乘函数 n!
阶乘函数可归纳定义为

递归算法如下：

public class 递归阶层 {
    public static void main(String[] args) {
        int n =5;
        System.out.println(f(n));
    }
    public static int f(int n){
        if(n==0||n==1){
            return 1;
        }
        return n*f(n-1);
    }
}

斐波那契数列

关系式：

F(1)=F(2)=1；

F(n)=F(n-1)+F(n-2) (n≥3)

递归算法如下：

public class 斐波那契数列 {
    public static void main(String[] args) {
        int n = 20;
        int f = f(n);
        System.out.println(f);
    }
    public static int f(int n){
        if (n==1||n==2){
            return 1;
        }
        return f(n-1)+f(n-2);
    }
}

整数幂的计算

int power(int x,int n){
	int y=0;
	if(n==0)y==1;
	else{
		y=power(x,x/2);
		y=y*y;
		if(n%2==1)
		y=y*x;
	}
	return y;

}

递归（2）

数组主元素

 A 是具有 n 个元素的数组，x 是 A 中的一个元素，若 A中有一半以上的元素与 x 相同，就称 x 是数组的主元素。

例：数组 A={1,3,2,3,3,4,3} 中，
元素 3 是该数组的主元素

编程

public int getCandidate(int nums[], int begin, int end ){
    int j = begin,count = 1;
    int c = nums[j];
    while(j<end-1 && count>0) {
        j++;
        if(nums[j]==c) {
            count = count + 1;
        }else {
            count = count - 1;
        }
    }
    if(j==end-1 && count>0) {
        return nums[j];                      //当剩余的时候说明很有可能是组元素，此时我们返回此时下标到验证函数中验证
    }else if(j==end-1 && count == 0 ) {
        return 0;                       //返回0代表没有组元素
    }else {
        return getCandidate(nums,j,end);      //递归调用
    }
}

分治

分治法解最大最小问题的过程

分治法解最大最小问题的过程例子：

合并排序的分治算法

算法的实现

merge_sort(Type A[ ], int low, int high)
      {    int mid;
           if (high > low)
           {    mid = (high – low) / 2;
                 merge_sort(A[ ], low, mid);
                 merge_sort(A[ ], mid + 1, high);
                 merge(A[ ], low, mid, high, high – low);
           }
      }

快速排序

把序列就地划分为两个子序列，使第一个子序列的所有元素都小于第二个子序列的所有元素，不断地进行这样的划分，最后构成 n 个子序列，每个子序列只有一个元素，这时，整个序列就是按递增顺序排序的序列了

枢点元素：

把序列的第一个元素作为枢点元素，重新排列这个序列

void quick_sort(Type A[ ], int low, int high)
{
   int k;
   if (low < high) {
      k = split(A, low, high);
      quick_sort(A, low, k-1);
      quick_sort(A, k+1, high);
   }
}

快速排序下列数字：
8，1，4，9，0，3，5，2，7，6

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-82AfxdOV-1625552480506)(http://t4king.oss-cn-beijing.aliyuncs.com/uPic/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F(1)].png)

线性选择

以下数求出第三大需要几次分区

137，96，88，108，17，87，65，35，76，45，66，18

(a)17，18，88，108，137，87，65，35，76，45，66，96

(b)88，66，45，87，65，35，76，96，108，137

以下数求出第五小需要几次分区

8 1 4 9 0 3 5 2 7 6

(a) 2 1 4 5 0 3 6 9 2 7

(b) 2 1 0 3 4 5

分治（2）选择问题

中值（5个元素为一组）

① 若，直接排序数组，第 k 个元素即为所求元素；否则，转 ②

② 把元素划分为 p = ⌊n / 5 ⌋ 组，每组 5 个元素，不足 5 个元素的那一组不予处理
③ 取每组的中值元素，构成一个规模为 p 的数组 M
④ 对数组 M 递归地执行算法，得到一个中值的中值元素 m
⑤ 把原数组划分成三组，使得大于 m 的元素存放于 P，等于 m 的元素存放于 Q，小于 m 的元素存放于 R
⑥ 如果 | P | > k，对 P 递归地执行算法；否则转 ⑦
⑦ 如果 | P | + | Q | > k，m 就是所选择的元素；否则转8；
⑧ 对 Q 递归地执行算法。