（6）排序算法——交换排序之冒泡排序

发表于   |   分类于   |   阅读次数

1、基本思想：

冒泡排序是一种简单的交换排序，交换排序就是两两比较待排序的元素，调整那些不满足次序要求的元素，直到整个表都满足次序要求为止。冒泡名字的由来是在排序过程中越大的元素会慢慢浮到数组的一端。

2、算法描述：

假设有数组arr[n]，升序排列。

  1. 比较相邻的元素，如果arr[0]比arr[1]大，则交换他们
  2. 比较arr[1]与arr[2]，依次比较下去，直到比较完成数组最后一个。这时数组最后一个应该是数组中最大的值。
  3. 重复上面的1,2步骤，比较除了最后一个之外的元素。
  4. 不断的重复直到数组中没有可以比较的元素。

3、Java实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 冒泡算法
 * 
 * @author lizhen
 */
public class BubbleSort {
	public void bubbleSort(int[] arr) {
		// 升序排列
		for (int i = arr.length - 1; i > 0; i--) {
			for (int j = 0; j < i; j++) {
				if (arr[j] > arr[j + 1]) {
					// 交换不满足次序的两个相邻节点。
					int temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
		}
	}
}

1.1.5.4 效率分析：