第二课 冒泡排序

引用

笔记--冒泡排序

1.冒泡排序类

package com.flysnow.chap03;

/**
 * 冒泡排序
 * @author 飞雪无情
 * @since:2010-3-25
 */
public class ArrayBub {
	private long[] a;
	private int nElems;
	public ArrayBub(int max){
		a=new long[max];
		nElems=0;
	}
	/**
	 * 插入元素
	 * @param value
	 */
	public void insert(long value){
		a[nElems]=value;
		nElems++;
	}
	/**
	 * 打印元素
	 */
	public void display(){
		for(int i=0;i<nElems;i++){
			System.out.print(a[i]+" ");
		}
		System.out.println();
	}
	/**
	 * 冒泡排序
	 */
	public void bubbleSort(){//性能O(N^2)
		for(int out=nElems-1;out>0;out--){//外循环，控制趟数
			for(int in=0;in<out;in++){//内循环，控制一趟比较次数
				if(a[in]>a[in+1]){//交换位置
					swap(in,in+1);
				}
			}
		}
	}
	/**
	 * 交换
	 * @param one 数组索引
	 * @param two 数组索引
	 */
	private void swap(int one, int two) {
		long temp=a[one];
		a[one]=a[two];
		a[two]=temp;
	}
}

2.冒泡排序测试

package com.flysnow.chap03;

import java.util.Random;

/**
 * 冒泡排序测试
 * @author 飞雪无情
 * @since:2010-3-25
 */
public class BubbleSortApp {
	public static void main(String[] args){
		ArrayBub bub=new ArrayBub(100);
		Random random=new Random();
		for(int i=0;i<10;i++){//添加10个随机数
			bub.insert((long)(random.nextFloat()*100));
		}
		bub.display();//未排序
		bub.bubbleSort();//排序
		bub.display();//排序后
	}
}

3.总结
算法思想:

• 第一趟，从队列的最左边开始，比较0号和1号的数据，如果0号的数据大于1号的，则交换位置，否则什么都不做。然后右移一个位置，比较1号和2号的数据，和刚才一样，一次类推走完第一趟。
• 第二趟，也是从最左边开始，比较0号和1号数据。。。一直到n-1号数据
• ........
• 直到比较到0号数据.

评论

4 楼 飞雪无情 2010-04-12  

zhangshixi 写道

飞雪无情 写道

zhangshixi 写道

这个算法是在Java数据结构和算法书上的吧？其中下面的外层循环条件有误，当对有序的数组进行反方向排序时，会出现最后两个数据项的排列错误。
# public void bubbleSort(){//性能O(N^2) 
#         for(int out=nElems-1;out>1;out--){//外循环，控制趟数 
#             for(int in=0;in<out;in++){//内循环，控制一趟比较次数 
#                 if(a[in]>a[in+1]){//交换位置 
#                     swap(in,in+1); 
#                 } 
#             } 
#         } 
#     } 
应改为out>=1或者out>0

嗯。。我测试了，对于有序数组时反向时的确存在问题，因为少比较了一趟。

恩，呵呵~我也是测试出来的。希望共同学习。

嗯。对于有序数组反序是冒泡排序最糟糕的情况，也是性能最差的情况，因为需要循环n-1趟，针对这种情况冒泡排序已经不合适了，用栈最好。。压进去，弹出来。正好反序。性能O(1)..

3 楼 zhangshixi 2010-04-12  

飞雪无情 写道

zhangshixi 写道

这个算法是在Java数据结构和算法书上的吧？其中下面的外层循环条件有误，当对有序的数组进行反方向排序时，会出现最后两个数据项的排列错误。
# public void bubbleSort(){//性能O(N^2) 
#         for(int out=nElems-1;out>1;out--){//外循环，控制趟数 
#             for(int in=0;in<out;in++){//内循环，控制一趟比较次数 
#                 if(a[in]>a[in+1]){//交换位置 
#                     swap(in,in+1); 
#                 } 
#             } 
#         } 
#     } 
应改为out>=1或者out>0

嗯。。我测试了，对于有序数组时反向时的确存在问题，因为少比较了一趟。

恩，呵呵~我也是测试出来的。希望共同学习。

2 楼 飞雪无情 2010-04-12  

zhangshixi 写道

这个算法是在Java数据结构和算法书上的吧？其中下面的外层循环条件有误，当对有序的数组进行反方向排序时，会出现最后两个数据项的排列错误。
# public void bubbleSort(){//性能O(N^2) 
#         for(int out=nElems-1;out>1;out--){//外循环，控制趟数 
#             for(int in=0;in<out;in++){//内循环，控制一趟比较次数 
#                 if(a[in]>a[in+1]){//交换位置 
#                     swap(in,in+1); 
#                 } 
#             } 
#         } 
#     } 
应改为out>=1或者out>0

嗯。。我测试了，对于有序数组时反向时的确存在问题，因为少比较了一趟。

1 楼 zhangshixi 2010-04-12  

这个算法是在Java数据结构和算法书上的吧？其中下面的外层循环条件有误，当对有序的数组进行反方向排序时，会出现最后两个数据项的排列错误。
# public void bubbleSort(){//性能O(N^2) 
#         for(int out=nElems-1;out>1;out--){//外循环，控制趟数 
#             for(int in=0;in<out;in++){//内循环，控制一趟比较次数 
#                 if(a[in]>a[in+1]){//交换位置 
#                     swap(in,in+1); 
#                 } 
#             } 
#         } 
#     } 
应改为out>=1或者out>0