[数据结构与算法]算法设计与分析——简单的排序算法（冒泡排序，选择排序，插入排序）

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)