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

蓝桥杯学习记录

思路分析
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;		
	}
	
}

测试结果

观察测试数据发现了,测试的数据为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;		
	}
	
}

测试结果

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