冒泡排序

冒泡排序算法

冒泡排序基本思想：
设数组arr中存放了n个元素，循环n-1次如下的排序过程：
step1：一次比较相邻两个数据元素，若a[i]>a[i+1],则交换两个数据元素，否则不交换。
step2：当完成一趟交换以后，最大的元素将会出现在数组的最后一个位置。
step3：一次重复以上过程，当第n-1趟结束时，整个n个数据元素集合中次小元素被放在a[1]中，a[0]中放置最小的数据元素

package com.bubblesort.yy;

/**
 * 冒泡排序
 * 
 * @author yuyang_csu
 *@data 2013-4-7
 */
public class BubbleSort {
	// 声明待排序的数组
	private int[] arr;

	// 重载构造方法
	public BubbleSort(int[] arr) {
		this.arr = arr;
	}

	// 交换数组中两个元素的方法
	public void swap(int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

	// 递归实现冒泡排序主方法
	public void bubbleSort(int lastindex) {
		for (int i = 0; i < lastindex; i++) {
			if (arr[i] > arr[i + 1]) {
				swap(i, i + 1);
			}
		}
		//递归的调用冒泡方法
		if (lastindex >= 0) {
			bubbleSort(--lastindex);
		}
	}
	
	//循环实现冒泡排序方法
	public void bubbleSort(){
		for(int i = 1;i<arr.length;i++){
			for(int j = 0;j<arr.length-i;j++){
				if (arr[j] > arr[j + 1]) {
					swap(j, j + 1);
				}
			}
		}
	}

	// 显示数组的方法
	public void display() {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + "  ");
		}
	}

	// 主函数
	public static void main(String args[]) {
		int[] arr = { 32, 26, 87, 72, 26, 17 };
		BubbleSort bs = new BubbleSort(arr);
		//bs.bubbleSort(arr.length - 1);
		bs.bubbleSort();
		bs.display();

	}
}

冒泡排序时间复杂度分析：一般情况下，冒泡排序的时间复杂度为O（n^2）。最好情况是数据的初始序列已排序，只需一趟扫描，比较次数为n，没有数据移动，时间复杂度为O（n）。最坏情况是数据元素反序排列，需要n-1趟扫描，比较次数和移动次数都是O（n^2）,时间复杂度为O（n^2）。总之，数据序列的初始排列越接近有序，冒泡排序的时间效率越高，其时间效率在O（n）和O（n^2）之间。

冒泡排序稳定性分析： 冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。