欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

排序之冒泡排序

程序员文章站 2022-05-12 17:55:46
...

冒泡排序


 该排序通过将数组嵌套循环,
 将相邻的两个对象进行比较,正序排序为例,如果a[0]的对象大于a[1]的对象,
 则将两个对象位置交换,将小的对象置前,直到数组结束,排序的过程中每次循环时,指针始终
 指向是当前最大的对象,将次对象与后面的对象相比较,当小于后一位对象时,置换,指针依然指向
 当前最大的对象。当一次循环结束时,已将最大的对象移至
 数组尾部。以此类推完成排序。

 

class Sort{
	private long[] a;
	private int nElement;
	public Sort(long[] array){
		this.a = array;
	}
	
	
	public static void main(String[] args) {
		long[] array = new long[]{5,3,1,7,9,2,0};
		Sort b = new Sort(array);
		b.bubbleSort();
		System.out.println(b);
	}
	
	
	public void bubbleSort(){
		int out,in;
		int step = 0;
		System.out.println("bubble---");
		for(out = a.length -1 ; out > 0; out --){
			
			for(in = 0; in < out; in++){
				if(a[in+1] < a[in]){
					long temp = a[in];
					a[in] = a[in+1];
					a[in+1] = temp;
					step++;
				}
			}
		}
		
		System.out.println(step);
	}
	

	public String toString(){
		StringBuilder b = new StringBuilder();
		for(long l : a){
			b.append(l);
			b.append(",");
		}
		return b.toString();
	}
}

 

  例:

 

对数组 {5,3,1,7,9,2,0} 进行排序 a[0] > a[1]
 loop1:3,5,1,7,9,2,0, 将前两个对象比较,a[0] 和 a[1] 位置对换,此时数组的指针a[1]
 loop2: 3,1,5,7,9,2,0, 进行比较,a[1] > a[2] 继续将大对象置后。
 loop3: 3,1,5,7,9,2,0, 第三次比较,a[2] < a[3] 位置没有调换,指针继续向后移,依然指向当前最大的对象。
 loop4  3,1,5,7,9,2,0,
 loop5: 3,1,5,7,2,9,0,
 loop6: 3,1,5,7,2,0,9, 第一轮循环结束,最大的对象已经移至最后一位,
 
 此数组用了 21 次比较 (N*(N-1)/2) 完成 排序,置换操作13次。

 内层每循环一次,指针都向后移动一位,当前后两个对象大小不符条件时,发生对换,
 指针始终指向的是当前最大的对象。
 (注意,内层循环终止位置  应该截止到已完成排序的位置。)
 

相关标签: 冒泡排序