排序算法第四篇——冒泡排序

算法描述：

依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。

Java源代码：

<span style="font-size: 18px;">package ljp.sort.maopao;

public class MaopaoSortDemo01 {
	private int[] list;

	// 构造函数，初始化数组
	public MaopaoSortDemo01() {
		list = new int[10];
		for (int i = 0; i < list.length; i++) {
			list[i] = (int) (Math.random() * 1000);
		}
	}

	public void sort() {
		for (int i = 0; i < list.length - 1; i++) {
			boolean flag = true;
			for (int j = list.length - 1; j > i; j--) {
				if (list[j] < list[j - 1]) {
					int temp = list[j];
					list[j] = list[j - 1];
					list[j - 1] = temp;
					flag = false;
				}
			}
			if (flag) {//冒泡的时候无交换，说明该序列为有序序列，跳出循环
				System.out.println("排序已经完成！");
				break;
			} else {
				System.out.println("第" + (i + 1) + "次冒泡...");
			}
			display();
		}
	}

	public void display() {
		for (int i : list) {
			System.out.print(i + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		MaopaoSortDemo01 maopaosort = new MaopaoSortDemo01();
		System.out.println("排序前:");
		maopaosort.display();
		maopaosort.sort();
	}

}
</span>

运行结果：

排序前:
788 754 434 515 519 579 354 979 94 535
第1次冒泡...
94 788 754 434 515 519 579 354 979 535
第2次冒泡...
94 354 788 754 434 515 519 579 535 979
第3次冒泡...
94 354 434 788 754 515 519 535 579 979
第4次冒泡...
94 354 434 515 788 754 519 535 579 979
第5次冒泡...
94 354 434 515 519 788 754 535 579 979
第6次冒泡...
94 354 434 515 519 535 788 754 579 979
第7次冒泡...
94 354 434 515 519 535 579 788 754 979
第8次冒泡...
94 354 434 515 519 535 579 754 788 979
排序已经完成！
该算法的时间复杂度为O(n2)，排序算法具有稳定性。