java算法之冒泡排序

package test.base.sort;

/**冒泡排序
 * 每完成一次排序，找出一个最大数。是一种稳定排序算法。
 * 冒泡排序算法的运作如下： 
 * 1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
 * 2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
 * 3、针对所有的元素重复以上的步骤，除了最后一个。
 * 4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
 * 
 * @author sky
 * 
 */
public class BubbleSorting {
	
	public static int[] bubbleSort(int[] arr) {
		boolean swap = true;
		//长度-1次，剩余最后一个元素不用比较
		for (int i = 0; i < arr.length - 1; i++) {
			swap = false;
			//排序完成的不用再继续比较
			for (int j = 0; j < arr.length - i - 1; j++) {
				if(arr[j] > arr[j + 1]){
					swap(arr, j, j + 1);
					swap = true;
				}
			}
			//没有位置调整，冒泡完成
			if(!swap){
				break;
			}
		}
		return arr;
	}
	//交换元素
	public static void swap(int[] arr, int index1, int index2){
		int tmp = arr[index1];
		arr[index1] = arr[index2];
		arr[index2] = tmp;
	}
	
	public static void traverse(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.println(arr[i]);
		}
	}

	public static void main(String[] args) {
		int[] arr = new int[] { 9, 5, 1, 7, 3, 2, 4, 6 };
		traverse(bubbleSort(arr));
	}
	
}

 

评论

1 楼 JerryDwan 2014-05-14  

这是个基本的冒泡排序，其中使用了旗标与右端左移两种方法来改进排序；更高效的方法可以使用ShakerSort排序。