数列特征,顺便谈谈冒泡排序和选择排序算法的效率问题

Dear 丶 2021-07-25 00:38 221阅读 0赞

**蓝桥杯学习记录**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNzQyMjIz_size_16_color_FFFFFF_t_70]  
**思路分析**  
**1.要输出这个数列的最大值和最小值,所以需要把这个数列排序,而要得到这个数列的和,所以需要重新设计一个方法(循环来求数列的和)**  
**2.有输入有输出**

先采用普通的冒泡排序算法对数列进行排序

package jiChuTest;
    //数列特征
    import java.util.Scanner;
    
    public class Sequence_characteristics { 
    
    	public static void main(String[] args) { 
    		// TODO 自动生成的方法存根
     
    		Scanner cin = new Scanner(System.in);
    		int  n = cin.nextInt();
    		int arr[]=new int [n];
    		for(int i=0;i<n;i++) { 
    			arr[i]=cin.nextInt();
    		}
    		sort(arr);
    		int m =add(arr);
    		System.out.println(m);
    	}
    	public static void sort(int numbers[]) { 
    		int i,j;
    		for(i =0;i<numbers.length;i++){ 
    			for(j=0;j<numbers.length-1;j++)
    			{ 
    				if(numbers[j]>numbers[j+1])
    				{ 
    					int temp= numbers[j];
    					numbers[j]=numbers[j+1];
    					numbers[j+1]=temp;
    				}
    			}
    		}
    		System.out.println(numbers[numbers.length-1]);
    		System.out.println(numbers[0]);
    	}
    // public static void sort(int arr[]) { 
    // for(int k = 0;k<arr.length;k++) { 
    // int minPos = k;
    // for(int j=1+k;j<arr.length;j++) { 
    // if(arr[minPos]>arr[j]) { 
    // minPos = j;
    // 
    // }
    // 
    // }
    // //System.out.println("minPos:"+ minPos);
    // int temp = arr[k];
    // arr[k] =arr[minPos];
    // arr[minPos]=temp;
    // }
    // System.out.println(arr[arr.length-1]);
    // System.out.println(arr[0]);
    //
    // }
    	public static int add(int number[]) { 
    
    		int sum=0;
    		for(int i = 0;i<number.length;i++) { 
    			sum += number[i];
    		}
    		
    		return sum;		
    	}
    	
    }

**测试结果**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNzQyMjIz_size_16_color_FFFFFF_t_70 1]  
观察测试数据发现了,测试的数据为10000个,数据量大,冒牌排序算法的效率就显得很低了,它需要和每一个数作比较.

package jiChuTest;
    //数列特征
    import java.util.Scanner;
    
    public class Sequence_characteristics { 
    
    	public static void main(String[] args) { 
    		// TODO 自动生成的方法存根
     
    		Scanner cin = new Scanner(System.in);
    		int  n = cin.nextInt();
    		int arr[]=new int [n];
    		for(int i=0;i<n;i++) { 
    			arr[i]=cin.nextInt();
    		}
    		sort(arr);
    		int m =add(arr);
    		System.out.println(m);
    	}
    // public static void sort(int numbers[]) { 
    // int i,j;
    // for(i =0;i<numbers.length;i++){ 
    // for(j=0;j<numbers.length-1;j++)
    // { 
    // if(numbers[j]>numbers[j+1])
    // { 
    // int temp= numbers[j];
    // numbers[j]=numbers[j+1];
    // numbers[j+1]=temp;
    // }
    // }
    // }
    // System.out.println(numbers[numbers.length-1]);
    // System.out.println(numbers[0]);
    // }
    	public static void sort(int arr[]) { 
    		for(int k = 0;k<arr.length;k++) { 
    			int minPos = k;
    		for(int j=1+k;j<arr.length;j++) { 
    			if(arr[minPos]>arr[j]) { 
    				minPos = j;
    				
    			}
    		
    		}
    		//System.out.println("minPos:"+ minPos);
    		int temp = arr[k];
    		arr[k] =arr[minPos];
    		arr[minPos]=temp;
    	}
    		System.out.println(arr[arr.length-1]);
    		System.out.println(arr[0]);
    
    	}
    	public static int add(int number[]) { 
    
    		int sum=0;
    		for(int i = 0;i<number.length;i++) { 
    			sum += number[i];
    		}
    		
    		return sum;		
    	}
    	
    }

**测试结果**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNzQyMjIz_size_16_color_FFFFFF_t_70 2]

**思考**  
在做算法题的时候可能会有多种实现的途径,要选择最适合的算法,最适合显得很笼统,但是一般我们可以选择牺牲空间来换取时间的方式.

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNzQyMjIz_size_16_color_FFFFFF_t_70]: /images/20210724/7bd98e650ab24081991765b024e2cac5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNzQyMjIz_size_16_color_FFFFFF_t_70 1]: /images/20210724/49d458196b24490888ab564c2b718c2b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNzQyMjIz_size_16_color_FFFFFF_t_70 2]: /images/20210724/867f60092fbb45e9bf263de3a7ce949b.png