• 数组常见算法

    一、数组排序

    冒泡排序

            本篇我们介绍最基本的排序方法：冒泡排序。

    实现步骤

    1、比较两个相邻元素，如果第一个比第二个大，就交换位置

    2、对每一对相邻元素进行同样的操作，除了最后一个元素

    特点

    每一轮循环后都会把最大的一个数交换到末尾，因此下一轮就可以忽略最后的数。

    总共比较n-1轮，每轮比较n-1-i次

    代码实现

    1. //无序数组
    2. int[] number1= {8,9,7,4,3};
    3. //int[] number1= {1,2,3,4,6};//有序数组 比较次数为：4
    4. System.out.println("排序前"+Arrays.toString(number1));
    5. int count=0;
    6. for(int i=0;n=number1.length();i++){
    7.     boolean isSorted=true;
    8.     for(int k=0;k1-i;k++){
    9.         count++;
    10.         //如果发生元素的交换则代表源数组无序
    11.         if(number1[k]>number1[k+1]){
    12.             number1[k]=number1[k]^number1[k+1];
    13.             number1[k+1]=number1[k]^number1[k+1];    
    14.             number1[k]=number1[k]^number1[k+1];
    15.             isSorted=false;
    16.         }
    17.     }
    18.     //若没有发生元素的交换则说明数组已经有序，则跳出循环，但至少比较一次
    19.     if(isSorted){
    20.         break;
    21.     }
    22. }
    23. System.out.println("比较次数为："+count);
    24. System.out.println("排序后"+Arrays.toString(number1));

    输出结果：

    排序前[8, 9, 7, 4, 3]
    比较次数为：10
    排序后[3, 4, 7, 8, 9] 

     使用Arrays工具类排序

            实际上，Java的标准库已经内置了排序功能，我们只需要调用Arrays.sort()方法就可以实现快速排序：

    1. int ns={3,6,1,8,2,9};
    2. //排序前
    3. System.out.println("排序前："Arrays.toString(ns));
    4. //排序
    5. ns.sort();
    6. //排序后
    7. System.out.println("排序后："Arrays.toString(ns));

    输出结果：

    排序前：[3,6,1,8,2,9]

     排序后：[1,2,3,6,8,9]

    二、无序数组查找

            在一个无序数组中，如果需要进行指定元素的查找，可以通过循环遍历或Arrays工具类两种方式进行查找。

    遍历查找

            我们可以通过对无序数组进行遍历，将数组中的每一个元素与目标元素进行比较，从而确定该数组中是否包含该目标数组：

    整型数组

    1. int[] array= {2,3,1,56,72,19,2,5,1};
    2. int index=-1;
    3. //查找元素第一次出现的位置
    4. try(Scanner input=new Scanner(System.in)){
    5.     System.out.println("请输入要查找的元素");
    6.     int target=input.nextInt();
    7.     //案例1：查找在无序数组中目标元素第一次出现的位置
    8.     for(int i=0;i
    9.         if(array[i]==target){
    10.             index=i;
    11.             System.out.println("%d第一次出现的位置是%d",target,index);
    12.             break;
    13.         }
    14.     }
    15.     System.out.println();
    16.     index=-1;
    17.     //案例2：查找在无序数组中目标元素最后一次出现的位置
    18.     for(int i=array.length-1;i>=0;i--){
    19.         if(array[i]==target) {
    20. 			index=i;
    21.             System.out.printf("%d最后一次出现的位置是%d",target,index);
    22. 			break;
    23. 		 }
    24.     }

    输出：请输入要查找的元素
    输入：1

    输出：
    1第一次出现的位置是2
    1最后一次出现的位置是8

    字符串数组

    1. String[] singerArray = { "李荣浩", "盘尼西林", "王菲", "王贰浪", "鹿先森乐            
    2.                     队","孙燕姿", "G.E.M.邓紫棋", "方大同", "品冠儿子" };
    3. 	int count=0;
    4. 	int index=-1;
    5. 	System.out.println("请输入你要查找的歌手：");
    6. 	try(Scanner input=new Scanner(System.in)){
    7. 		String target=input.next();
    8. 		for(int i=0;i
    9. 			count++;
    10. 			//String字符串的等值比较，必须用equals方法
    11. 			if(singerArray[i].equals(target)) {
    12. 				index=i;
    13. 				break;
    14. 			}	
    15. 		}
    16. 	System.out.printf("%s的位置在%d,查找了%d次",target,index,count);
    17. 	}

    输出：请输入你要查找的歌手：
    输入：孙燕姿
    输出：孙燕姿的位置在5,查找了6次 

    双指针遍历查找--字符串数组

    1. String[] singerArray = { "李荣浩", "盘尼西林", "王菲", "王贰浪", "鹿先森乐        
    2.                     队","孙燕姿", "G.E.M.邓紫棋", "方大同", "品冠儿子" };
    3. int count=0;
    4. int index=-1;
    5. try(Scanner input=new Scanner(System.in)){
    6. 	System.out.println("请输入你要查找的歌手：");
    7. 	String target=input.next();	
    8.     for(int i=0,k=singerArray.length-1;i<=k;i++,k--) {
    9.         count++;
    10.         //从头开始比较
    11.         if(singerArray[i].equals(target)){
    12.             index=i;
    13.             break;
    14.         }
    15.         //从尾部开始比较
    16.         if(singerArray[k].equals(target)){
    17.             index=k;
    18.             break;
    19.         }
    20.     }
    21. System.out.printf("%s的位置在%d,查找了%d次",target,index,count);
    22. }

     输出：请输入你要查找的歌手：
    输入：孙燕姿
     输出：孙燕姿的位置在5,查找了4次

    双指针的查找次数少，效率更高

    三、有序数组查找

    二分查找

    作用

            在一个有序数组中，如果需要进行指定元素的查找，可以采用二分查找(binarySearch)，这样会比通过遍历数组来进行查找的效率高很多。以下是二分查找的代码实现：

    1. int[] num={1,3,5,7,8};
    2. int target=3;
    3. int index=-1;
    4. //数组的首元素和尾元素
    5. int low=0,high=num.length-1;
    6.  
    7. while(low<=high){
    8.     int mid=(low+high)/2;
    9.     //判断mid是否等于target
    10.     if(num[mid]==target){
    11.         index=mid;//如果等于代表查找成功，则循环退出
    12.         break;
    13.     }else if(num[mid]>target){//此时代表目标元素可能在mid的左半区
    14.         hight=mid-1;
    15.     }else if(num[mid]//此时代表目标元素可能在mid的右半区
    16.         low=mid+1;
    17.     }
    18. }
    19. System.out.printf("%d的位置为%d",target,index);

    输出结果：3的位置为1 

    Arrays工具类查找

            在Java的标准库中也为我们内置了二分查找，可以直接通过调用Arrays.binarySearch()的方法进行查找：由于该方法基于二分查找，所以进行排序的数组必须是有序的，所以我们可以先使用Arrays.sort()进行排序，再调用Arrays.binarySearch()进行查找

    1. int[] array={28,12,89,73};
    2. int target=12;
    3. //先排序
    4. Arrays.sort(array);
    5. //在查找
    6. int index=Arrays.binarySearch(array,target);
    7.  
    8. System.out.println("%s的位置在%d",target,index)

    输出结果：12的位置在1  

    四、数组乱序

    算法简述

             题目：将一个数组中所有元素的顺序都打乱。

            那不是直接用Math.random()*100重复50次不就好了吗？不，Math.random()的重复概率很大，不能保证50个数字每个都不同，所以我们为大家介绍一种算法：乱序算法

    实现步骤

    ①假设有一个等待乱序的数组P

    ②从P中随机选取一个未乱序的元素

    ③将该元素与数组P中最后一个元素交换

    ④重复2、3两个步骤直到数组P中所有元素全部完成排序

    代码实现

    1. int[] number= {11,12,13,14,15,16,17};
    2. System.out.println("乱序前："+Arrays.toString(number));
    3. for(int i=number.length-1;i>0;i--){
    4.     //产生随机下标
    5.     int randomIndex=(int)(Math.random()*i);
    6.     //交换元素
    7.     number[i]=number[i]^number[randomindex];
    8. 	number[randomindex]=number[i]^number[randomindex];
    9. 	number[i]=number[i]^number[randomindex];
    10. }
    11. System.out.println("乱序后："+Arrays.toString(number));

    输出结果：

    乱序前：[11, 12, 13, 14, 15, 16, 17]
    乱序后：[12, 16, 17, 15, 11, 13, 14]

    应用

    题目：产生7个不重复的1-33的数字

    1. int[] num=new int[33];
    2. for(int i=0;i
    3.     num[i]=i+1;
    4. }
    5. System.out.println("乱序前："+Arrays.toString(number));
    6. //先乱序
    7. for(int i=num.length;i>0;i--){
    8.     int randindex=(int)(Math.random()*i);
    9.     num[i]=num[randindex]^num[i];
    10.     num[randindex]=num[randindex]^num[i];
    11.     num[i]=num[randindex]^num[i];
    12. }
    13. //存前7个
    14. int[] n=new int[7];
    15. System.arraycopy(num,0,n,0,n.length);
    16. System.out.println("乱序后："+Arrays.toString(number));

    输出结果：

    [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33]
    [21, 12, 8, 26, 16, 5, 25]
     

    五、数组旋转

    算法描述

    数组向右旋转3位：将尾元素通过不断旋转，交换到头部

    数组向左旋转三位：将头元素通过不断旋转，交换到尾部

     

    代码实现 

    向右旋转

    //遍历的顺序:从尾部开始
    //交换的双方:k和k-1

    1. int[] number= {1,2,3,4,5,6,7};
    2. //向右旋转3次
    3. //外层循环控制旋转次数，向右旋转3次
    4. for(int i=0;i<3;i++){
    5.     //内层循环控制旋转方向，每次向右旋转一位
    6.     //遍历的顺序:从尾部开始
    7.     //交换的双方:k和k-1
    8.     for(int k=number.length;k>0;k--){
    9.         number[k]=number[k]^number[k-1];
    10. 		number[k-1]=number[k]^number[k-1];
    11. 		number[k]=number[k]^number[k-1];
    12.     }
    13. }
    14. System.out.println("向右旋转3次："+Arrays.toString(number));

     输出结果：向右旋转3次：[5, 6, 7, 1, 2, 3, 4]

    向左旋转

    //遍历的顺序:从头部开始
    //交换的双方:k和k+1

    1. int[] number= {1,2,3,4,5,6,7};
    2. //外层循环控制旋转次数，向左旋转3次
    3. for(int i=0;i<3;i++) {
    4. //内层循环控制旋转方向，每次向左旋转一位
    5.     for(int k=0;k1;k++){
    6.         number[k]=number[k]^number[k+1];
    7. 		number[k+1]=number[k]^number[k+1];
    8. 		number[k]=number[k]^number[k+1];  
    9.     }
    10. }
    11. System.out.println("向左旋转3次:"+Arrays.toString(number));

    输出结果：向左旋转3次:[4, 5, 6, 7, 1, 2, 3]

    写作不易，如果帮到了你就点赞收藏吧！！

  • 相关阅读:
    力扣每日一题：1752. 检查数组是否经排序和轮转得到
    Linux 学习使用包管理器-实践和项目应用和命令行学习技巧与编程实践
    Flutter知识点
    H5互动小游戏如何提升用户留存
    神经网络模型的基本原理,神经网络模型是干嘛的
    RS485modbus转Profinet网关协议连接富凌DZB300系列变频器配置方法
    【运维】Linux修改Hosts
    【操作系统】聊聊磁盘IO是如何工作的
    信息科技风险管理：合规管理、技术防控与数字化
    AD9361手册解读
  • 原文地址：https://blog.csdn.net/weixin_64975807/article/details/136462475