2022-07-15 第三小组 赖哲栋 学习笔记

本文主要是介绍2022-07-15 第三小组 赖哲栋 学习笔记，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

• • 1. 数据结构
  • 2. 算法查找
    • 2.1 线性查找
    • 2.2 二分法查找
• 3. 算法排序
  • • 3.1 冒泡排序
    • 3.2 冒泡排序的简便排序
    • 3.3 选择排序
    • 3.4 插入排序
  • 4.数组的扩容

1. 数据结构

1. 数组是最基本的数据结构：是一张表，线性表(数据元素之间是一对一的关系)，除了第一个和最后一个之外，其余的元素都是收尾连接的
2. 链表
3. 树
4. 图

案例：

​ 找出一个数在数组中的位置
​ 在数组中是否存在，如果存在，返回下标；如果不存在，返回数组不存在

		int[] arr = new int[]{1, 2, 3, 4, 5, 6};
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入一个数：");
        int s = sc.nextInt();
        a:for(;;){
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == s) {
                System.out.println("你要找的数是:" + s + "在目标数组中的下标是" + i);
                break a;

            }
        }
            System.out.println("你要找的数是:" + s + "在目标数组中不存在");
            break a;

2. 算法查找

2.1 线性查找

线性查找又称顺序查找，是一种最简单的查找方法，它的基本思想是从第一个记录开始，逐个比较记录的关键字，直到和给定的K值相等，则查找成功；若比较结果与文件中n个记录的关键字都不等，则查找失败。

        int[] arr = new int[]{1, 2, 3, 4, 5, 6};
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入一个数：");
        int s = sc.nextInt();
		//设置标识
        int index = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == s) {
                //if语句执行时，index会改变;不执行时，index为-1
                index = i;
                break;
            }
        }
        if (index != -1) {
            System.out.println("你要找的数是:" + s + "在目标数组中的下标是" + index);
        } else {
            System.out.println("你要找的数是:" + s + "在目标数组中不存在");
        }

2.2 二分法查找

二分法查找也叫折半查找，使用二分法查找数字的前提是这个数组必须有顺序

        int[] arr = new int[]{1, 2, 3, 4, 5, 6};
        Scanner sc = new Scanner(System.in);
        System.out.println("输入你要查找的数字：");
        int target = sc.nextInt();
        //最左边的下标
        int left = 0;
        //最右边的下标
        int right = arr.length - 1;
		//查询的数字不在数组范围内
        if (target < arr[left] || target > arr[right]) {
            System.out.println(target + "在目标数组中不存在!");
        } else {
            //用来保存找到的下标的值
            int res = -1;
            while (left <= right) {
                //找出中间位置
                int middle = (left + right) / 2;
                if (arr[middle] == target) {
                    //中间的数恰巧是我们要找的数
                    res = middle;
                    break;
                } else if (arr[middle] > target) {
                    //说明我们要找的数在数组的前半区
                    /*
                     *   如果在前半区
                     *   维护left和right
                     *   left是不需要动的
                     *   right应该移动到中间位置
                     * */
                    right = middle - 1;
                } else {
                    //条件实际上就是arr[middle]<target
                    /*
                     *   如果在后半区
                     *   维护left和right
                     *   right是不需要动的
                     *   left应该移动到中间位置
                     * */
                    left = middle + 1;
                }
            }
            System.out.println("你要找的数是:"+target+"在目标数组中的下标是"+res);
        }

3. 算法排序

3.1 冒泡排序

拿未排序第一个数和后面的数一一比较大小，小的往前放，大的往后移

int[] arr = new int[]{1, 34, 55, 22, 43, 32};
        //从小到大
        /*
            冒泡排序需要两层循环嵌套：for
            外层for循环控制的是需要各个数之间比较几轮
            内能for循环控制的是每个数的真正的比较
        */
        for (int i = 0; i < arr.length - 1; i++) {
            //已经控制好了比较的次数
            //比较的次数 = 数组的长度-1
            for (int j = 0; j < arr.length - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    //如果前面的比后面的大，换位
                    int temp = 0;
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            System.out.print("第"+(i+1)+"轮的比较结果是");
            for (int i1:arr) {
                System.out.print(i1+"、");
            }
            System.out.println(" ");
        }

3.2 冒泡排序的简便排序

只能从小到大排序

 int[] arr = new int[]{1, 34, 55, 22, 43, 32};
        Arrays.sort(arr);
        for (int i:arr
             ) {
            System.out.println(i);
        }

3.3 选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。

 /*
            第一轮
                i=0, minIndex=0，里层for循环j=1;j<7
                j=1,if(arr[0]>arr[1])不成立，则继续执行
                j=2,if(arr[0]>arr[2])不成立，则继续执行
                j=3,if(arr[0]>arr[3])不成立，则继续执行
                j=4,if(arr[0]>arr[4])不成立，则继续执行
                j=5,if(arr[0]>arr[5])成立，minIndex=j
                j=6,if(arr[0]>arr[4])不成立，则继续执行
                里层for循环结束
                temp = arr[5];
                arr[minIndex] = arr[0]
                arr[i] = temp
             第二轮
                i=1  minIndex =1  里层for循环j=2;j<7
        */
        int[] arr = new int[]{1,63,56,36,27,-8,44};
        for (int i = 0; i <arr.length ; i++) {
            // 假设最小的下标
            int minIndex = i;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[minIndex]>arr[j]){ //找到了最小值
                    minIndex = j; //保存最小值的下标
                }
            }
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
            System.out.print("第"+(i+1)+"次比较结果是:");
            for (int i1:arr) {
                System.out.print(i1+"、");
            }
            System.out.println( );
        }

3.4 插入排序

/*
           第一轮
                i=0,current = arr[1],int preIndex = 0,
                while(0>=0 && 25 < arr[0]){}不成立,while循环不执行
           第二轮
                i=1,current = arr[2],int preIndex = 1,
                while(1>=0 && 25 < arr[1]){}不成立,while循环不执行
           第二轮
                i=2,current = arr[3],int preIndex = 2,
                while(2>=0 && 25 < arr[2]){
                    arr[3] = arr[2]
                    2--
                }
        */
        int[] arr = new int[]{1, 25, 48, 12, 10, -8, 127, 56};
        //定义参照物
        int current;
        for (int i = 0; i < arr.length; i++) {
            current = arr[i+1];
            //定义上一个元素的下标
            int preIndex = i;
            //当上一个数的下标有效并且不小于0
            //还要保证当前的数比它上一位数小
            //这种时候，才能然当前述向前移位
            while(preIndex >=0 && current < arr[preIndex]){
                //前面的数后移一位
                arr[preIndex + 1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex + 1] = current;
        }

4.数组的扩容

		int[] nums = new int[]{3,4,6};
        //定义一个新的临时数据
        int[] temp = new int[6];
        for (int i = 0; i < nums.length; i++) {
            temp[i] = nums[i];
        }
        nums =temp;
        System.out.println(Arrays.toString(nums));

案例:

思路1：
创建一个等长的数组
把当前输入的每一个元素倒着添加到新数组里
新数组赋值给老数组

    int[] arr = new int[]{1, 25, 48, 12, 10, -8, 127, 56};
	int[] newArr = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            newArr[i] = arr[arr.length - 1 - i];
            //新数组赋值给你老数组
        }
        arr = newArr;
        for (int i : arr) {
            System.out.println(i);
        }


思路2
利用交换的方法
    for (int i = 0; i < arr.length / 2; i++) {
            //temp存储的是最后一位
            int temp = arr[arr.length - 1 - i];
            arr[arr.length-1-i] = arr[i];
            arr[i] = temp;
        }
        for (int i:arr
             ) {
            System.out.println(i);
        }

这篇关于2022-07-15 第三小组 赖哲栋 学习笔记的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！