Java教程

算法设计与分析——简单的排序算法(冒泡排序,选择排序,插入排序)

本文主要是介绍算法设计与分析——简单的排序算法(冒泡排序,选择排序,插入排序),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Comparable接口

在实际应用中,我们对一些数据进行排序,通常不会是某个单独的数字,比如根据学生的年龄对学生排序、根据商品的价格对商品进行排序等等,这时我们排序操作的就是一个对象,Java提供了一个接口Comparable就是用来定义排序规则的。

实例:定义一个学生类Student,具有姓名name和年龄age两个属性,通过Comparable接口提供比较规则。

package learn;

class Student implements Comparable<Student>{
	public String name;
	public int age;
	
	
	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public int getAge() {
		return age;
	}

	public void setAge(int age) {
		this.age = age;
	}
	
	@Override
	public String toString() {
		return "Student [name=" + name + ", age=" + age + "]";
	}

	@Override
	public int compareTo(Student o) {
		// TODO Auto-generated method stub
		return this.getAge()-o.getAge();
	}

	
}
public class ComparableApp {
	public static void main(String args[]) {
		Student s1=new Student();
		Student s2=new Student();
		s1.setName("111");
		s1.setAge(20);
		s2.setName("222");
		s2.setAge(19);
		System.out.print(compare(s1,s2));
	}
	public static Comparable compare(Comparable c1,Comparable c2) {
		Comparable c=new Student();
		int result=c1.compareTo(c2);
		//如果result<0,c2>c1
		//如果result>0,c2<c1
		if(result<0) {
			c=c2;
		}
		else if(result>=0) {
			c=c1;
		}
		return c;
	}
}

1.冒泡排序

(1)比较相邻的元素,如果第一个元素比后一个元素大,就交换这两个元素的位置

(2)对每一对相邻元素做同样的工作,最终最后位置的元素就是最大值

总结:第一次冒泡,最大值放在最后一位

第二次冒泡,第二大值放在倒数第二位

依次下去

每冒泡一次元素就会少一个

public class maopapapp {
	public static void main(String args[]) {
		int [] test= {6,5,4,3,2,1};
		System.out.print("初始状态:");
		for(int k=0;k<test.length;k++) {
			System.out.print(test[k]+" ");
		}
		System.out.println();
		for(int i=0;i<test.length;i++) {
			for(int j=0;j<test.length-i-1;j++) {
				if(test[j]>test[j+1]) {
					int temp=test[j];
					test[j]=test[j+1];
					test[j+1]=temp;
				}
			}
			System.out.print("第"+(i+1)+"次冒泡:");
			for(int k=0;k<test.length;k++) {
				System.out.print(test[k]+" ");
			}
			System.out.println();
		}
	}
}

**时间复杂度:**O(N^2)

最坏情况下,要排序的元素逆序

元素比较的次数为:(N-1)+(N-2)+(N-3)+…+2+1=N*(N-1)/2

元素交换的次数为:(N-1)+(N-2)+(N-3)+…+2+1=N*(N-1)/2

总执行次数:N*(N-1)/2+N*(N-1)/2=N^2-N

2.选择排序

(1)每一次遍历找出最小值所在的位置

(2)将最小值放在第一个位置,以此类推

public class xuanzeapp {
	public static void main(String args[]) {
		int[] test= {6,5,4,3,2,1};
		
		System.out.print("初始数组为:");
		for(int k=0;k<test.length;k++) {
			System.out.print(test[k]+" ");
		}
		System.out.println();
		
		for(int i=0;i<test.length-1;i++) {
			int minindex=i;
			for(int j=i+1;j<test.length;j++) {
				if(test[j]<test[minindex]) {
					minindex=j;
				}
			}
			
			int temp=test[minindex];
			test[minindex]=test[i];
			test[i]=temp;
			
			System.out.print("第"+(i+1)+"次选择排序结果:");
			for(int k=0;k<test.length;k++) {
				System.out.print(test[k]+" ");
			}
			System.out.println();
		}
	}
}

**时间复杂度:**O(N^2)

最坏情况下,要排序的元素逆序

数据比较次数:(N-1)+(N-2)+(N-3)+…+2+1=N*(N-1)/2

数据交换次数:N-1

总执行次数:N*(N-1)/2+N-1

3.插入排序

(1)假设第一个数有序,第二个数与前面一个数比较,若比第一个数小,则将第二个数与第一个数交换位置

(2)第一步后前面两个数已经有序,第三个数与第二个数比较,若比第二个数小,则将第二个数与第一个数交换位置,再与前一个数比较

(3)依次类推

public class charuapp {
	public static void main(String args[]) {
		int [] test= {9,8,7,6,5,4,3,2,1};
		System.out.print("初始状态:");
		for(int k=0;k<test.length;k++) {
			System.out.print(test[k]+" ");
		}
		System.out.println();
		for(int i=1;i<test.length;i++) {
			for(int j=i;j>0;j--) {
				if(test[j]<test[j-1]) {
					int temp=test[j];
					test[j]=test[j-1];
					test[j-1]=temp;
				}
			}
			System.out.print("第"+i+"次插入排序:");
			for(int k=0;k<test.length;k++) {
				System.out.print(test[k]+" ");
			}
			System.out.println();
		}
	}
}

**时间复杂度:**O(N^2)

最坏情况下,要排序的元素逆序

数据比较次数:(N-1)+(N-2)+(N-3)+…+2+1=N*(N-1)/2

数据交换次数:(N-1)+(N-2)+(N-3)+…+2+1=N*(N-1)/2

总执行次数:N*(N-1)

这篇关于算法设计与分析——简单的排序算法(冒泡排序,选择排序,插入排序)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!