数据结构算法 之 冒泡排序算法

/**
冒泡排序算法:
n 个元素,前后两个元素比较大小,如果前面元素大于后面元素,则交换位置。 直到排序完成
*/

第一趟排序 :



以此类推 得到 从小到大 序列 :50,60,70,80,85,90

代码实现:

package com.data.structure;

public class TestBubbleSort {

	public static void main(String[] args){
		//学生分数成绩
		int[] scores={90,70,50,80,60,85};
		
		//将分数按照从小到大排列
		sort(scores);
		
		//输出排序后的成绩
		for(int i=0;i<scores.length;i++)
		{
			System.out.print(scores[i]+",");
		}

	}

	public static void sort(int[] arrays){
		//第一个循环排序趟数
		for(int i=0;i<arrays.length-1;i++)
		{
			//第二个循环控制每次要比较的元素次数
			for(int j=0;j<arrays.length-1;j++)
			{
				if(arrays[j]>arrays[j+1])
				{
					int flag=arrays[j];
					arrays[j]=arrays[j+1];
					arrays[j+1]=flag;
				}
			}
		}
	}

}


结果:
50,60,70,80,85,90,

2.我们打印出 每一趟 排序后的结果

package com.data.structure;

public class TestBubbleSort2 {
	
	public static void main(String[] args){
		//学生分数成绩
		int[] scores={90,70,50,80,60,85};
		
		//将分数按照从小到大排列
		sort(scores);

	}

	public static void sort(int[] arrays){
		//第一个循环排序趟数
		for(int i=0;i<arrays.length-1;i++)
		{
			//第二个循环控制每次要比较的元素次数
			for(int j=0;j<arrays.length-1;j++)
			{
				if(arrays[j]>arrays[j+1])
				{
					int flag=arrays[j];
					arrays[j]=arrays[j+1];
					arrays[j+1]=flag;
				}
			}
			
			//输出每趟交换后的分数排列情况
			System.out.print("第"+(i+1)+"趟排序后结果 : ");
			for(int k=0;k<arrays.length;k++)
			{
				System.out.print(arrays[k]+",");
			}
			System.out.println("");
			
		}
	}
	

}


结果:
第1趟排序后结果 : 70,50,80,60,85,90,
第2趟排序后结果 : 50,70,60,80,85,90,
第3趟排序后结果 : 50,60,70,80,85,90,
第4趟排序后结果 : 50,60,70,80,85,90,
第5趟排序后结果 : 50,60,70,80,85,90,

从结果看 第3趟排序后已经排序完成。 这个时候第4,5趟排序可以不用做了。

3.优化一下算法 : 如果每趟排序前后两个元素有交换 则继续下一趟排序,否则终止。 减少排序趟数,提高效率

package com.data.structure;

public class TestBubbleSort3 {
	
	public static void main(String[] args){
		//学生分数成绩
		int[] scores={90,70,50,80,60,85};
		
		//将分数按照从小到大排列
		sort(scores);

	}

	public static void sort(int[] arrays){
		//第一个循环排序趟数
		for(int i=0;i<arrays.length-1;i++)
		{
			boolean isExchanged=false; //每趟排序是否发生了交换
			//第二个循环控制每次要比较的元素个数
			for(int j=0;j<arrays.length-1;j++)
			{
				if(arrays[j]>arrays[j+1])
				{
					int flag=arrays[j];
					arrays[j]=arrays[j+1];
					arrays[j+1]=flag;
					
					isExchanged=true;
				}
			}
			
			//如果没有发生交换,说明已经排序完成
			if(!isExchanged)
			{
				break;
			}
			
			//输出每趟交换后的分数排列情况
			System.out.print("第"+(i+1)+"趟排序后结果 : ");
			for(int k=0;k<arrays.length;k++)
			{
				System.out.print(arrays[k]+",");
			}
			System.out.println("");
			
		}
	}

}


结果:
第1趟排序后结果 : 70,50,80,60,85,90,
第2趟排序后结果 : 50,70,60,80,85,90,
第3趟排序后结果 : 50,60,70,80,85,90,

4.再打印一下 每趟排序过程中经历的比较次数

package com.data.structure;

public class TestBubbleSort4 {
	
	public static void main(String[] args){
		//学生分数成绩
		int[] scores={90,70,50,80,60,85};
		
		//将分数按照从小到大排列
		sort(scores);

	}

	public static void sort(int[] arrays){
		//第一个循环排序趟数
		for(int i=0;i<arrays.length-1;i++)
		{
			boolean isExchanged=false; //每趟排序是否发生了交换
			int comparingCount=0; //每趟排序比较次数
			//第二个循环控制每次要比较的元素个数
			for(int j=0;j<arrays.length-1;j++)
			{
				if(arrays[j]>arrays[j+1])
				{
					int flag=arrays[j];
					arrays[j]=arrays[j+1];
					arrays[j+1]=flag;
					
					isExchanged=true;
				}
				
				comparingCount++;
			}
			
			//如果没有发生交换,说明已经排序完成
			if(!isExchanged)
			{
				break;
			}
			
			//输出每趟交换后的分数排列情况
			System.out.print("第"+(i+1)+"趟排序后结果 : ");
			for(int k=0;k<arrays.length;k++)
			{
				System.out.print(arrays[k]+",");
			}
			System.out.println(" 比较次数 : "+comparingCount);
			
		}
	}

}


结果:
第1趟排序后结果 : 70,50,80,60,85,90, 比较次数 : 5
第2趟排序后结果 : 50,70,60,80,85,90, 比较次数 : 5
第3趟排序后结果 : 50,60,70,80,85,90, 比较次数 : 5

从结果看 每趟排序 都要比较 5 次。 其实每排完一趟序就已经产生了一个最大值,下一趟排序可以减少一次比较.

5.优化一下算法 : 每下一趟排序减少一次比较次数。 提高效率

package com.data.structure;

public class TestBubbleSort5 {
	
	public static void main(String[] args){
		//学生分数成绩
		int[] scores={90,70,50,80,60,85};
		
		//将分数按照从小到大排列
		sort(scores);

	}

	public static void sort(int[] arrays){
		//第一个循环排序趟数
		for(int i=0;i<arrays.length-1;i++)
		{
			boolean isExchanged=false; //每趟排序是否发生了交换
			int comparingCount=0; //每趟排序比较次数
			//第二个循环控制每次要比较的元素个数   arrays.length-i-1 每下一趟排序减少已经排完的次数
			for(int j=0;j<arrays.length-i-1;j++)
			{
				if(arrays[j]>arrays[j+1])
				{
					int flag=arrays[j];
					arrays[j]=arrays[j+1];
					arrays[j+1]=flag;
					
					isExchanged=true;
				}
				
				comparingCount++;
			}
			
			//如果没有发生交换,说明已经排序完成
			if(!isExchanged)
			{
				break;
			}
			
			//输出每趟交换后的分数排列情况
			System.out.print("第"+(i+1)+"趟排序后结果 : ");
			for(int k=0;k<arrays.length;k++)
			{
				System.out.print(arrays[k]+",");
			}
			System.out.println(" 比较次数 : "+comparingCount);
			
		}
	}

}


结果:
第1趟排序后结果 : 70,50,80,60,85,90, 比较次数 : 5
第2趟排序后结果 : 50,70,60,80,85,90, 比较次数 : 4
第3趟排序后结果 : 50,60,70,80,85,90, 比较次数 : 3

5.优化一下算法 2 : 每一趟排序如果发生了交换,记下最后一次交换的位置 作为下一趟排序比较次数。

package com.data.structure;

public class TestBubbleSort5_2 {
	
	public static void main(String[] args){
		//学生分数成绩
		int[] scores={90,70,50,80,60,85};
		
		//将分数按照从小到大排列
		sort(scores);

	}

	public static void sort(int[] arrays){
		int len=arrays.length-1;
		int childLen=len;
		
		//第一个循环排序趟数
		for(int i=0;i<len;i++)
		{
			boolean isExchanged=false; //每趟排序是否发生了交换
			int comparingCount=0; //每趟排序比较次数
			int lastExchangedPosition=0;//最后一次交换的位置
			//第二个循环控制每次要比较的元素个数   arrays.length-i-1 每下一趟排序减少已经排完的次数
			for(int j=0;j<childLen;j++)
			{
				if(arrays[j]>arrays[j+1])
				{
					int flag=arrays[j];
					arrays[j]=arrays[j+1];
					arrays[j+1]=flag;
					
					lastExchangedPosition=j;
					isExchanged=true;
				}
				
				comparingCount++;
			}
			
			//如果没有发生交换,说明已经排序完成
			if(!isExchanged)
			{
				break;
			}
			
			childLen=lastExchangedPosition;//保存上一次 最后交换的位置
			
			//输出每趟交换后的分数排列情况
			System.out.print("第"+(i+1)+"趟排序后结果 : ");
			for(int k=0;k<arrays.length;k++)
			{
				System.out.print(arrays[k]+",");
			}
			System.out.println(" 比较次数 : "+comparingCount);
			
		}
	}

}


结果:
第1趟排序后结果 : 70,50,80,60,85,90, 比较次数 : 5
第2趟排序后结果 : 50,70,60,80,85,90, 比较次数 : 4
第3趟排序后结果 : 50,60,70,80,85,90, 比较次数 : 2


6.Java 中我们来实现对象排序, 新建一个学生类,然后根据学生的 成绩高低排序对象

package com.data.structure;

public class TestBubbleSort6 {
	
	public static void main(String[] args){
		//学生分数成绩
		Student[] students={
				new Student("小明",90),
				new Student("李虎",70),
				new Student("胡杨",50),
				new Student("王蒙",80),
				new Student("丁杰",60),
				new Student("梁辉",85)
			};
		
		//将分数按照从小到大排列
		sort(students);
		
		//输出排序后的学生信息
		for(int i=0;i<students.length;i++)
		{
			Student s=students[i];
			System.out.print(s.getName()+"="+s.getScore()+" , ");
		}

	}

	public static void sort(Object[] objs){
		
		int len=objs.length-1;
		int childLen=len;

		for(int i=0;i<len;i++)
		{
			boolean isExchanged=false; 
			int lastExchangedPosition=0;//最后一次交换的位置
			for(int j=0;j<childLen;j++)
			{
				Comparable comparable=(Comparable)objs[j];
				if(comparable.compareTo(objs[j+1])>0)
				{
					Object flag=objs[j];
					objs[j]=objs[j+1];
					objs[j+1]=flag;
					
					lastExchangedPosition=j;
					isExchanged=true;
				}
			}
			
			if(!isExchanged)
			{
				break;
			}
			
			childLen=lastExchangedPosition;//保存上一次 最后交换的位置
		}
	}

}

class Student implements Comparable
{
	private String name; //姓名
	private int score;   //成绩
	
	public Student(String name, int score) {
		this.name = name;
		this.score = score;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public int getScore() {
		return score;
	}
	public void setScore(int score) {
		this.score = score;
	}
	
	//当前的对象 和 下一个对象比较   > 0 交换, <0 不交换
	public int compareTo(Object obj)
	{
		//以成绩来比较大小
		Student s=(Student)obj;
		if(this.score>s.getScore())
		{
			return 1;
		}
		else if(this.score<s.getScore())
		{
			return -1;
		}
		
		return 0;
	}
	
}


结果:
胡杨=50 , 丁杰=60 , 李虎=70 , 王蒙=80 , 梁辉=85 , 小明=90 ,


至简 VereMVC 框架


至简 Java


设计模式 Java 实战


剖析 Java 并发编程


Java 深入浅出 数据结构算法


Java NIO 精髓实战


Java JVM 虚拟机 代码与图解


至简 SQL 基础 MySQL


至简 SQL Oracle


透析 JDBC


至简 Java Web 案例驱动


至简框架 Java


Java 集群架构实战


至简 HTML CSS JavaScript


集合 XML JSON 解析互换原理


Android 循序渐进 实战


至简 Python


Python 设计模式


Python 深入浅出 数据结构算法


至简 Python VereWeb 案例驱动

数据结构算法 之 冒泡排序算法