交换排序——冒泡排序

on October 8, 2016 under jekyll

1 minute read

算法描述：

基本思想是：比较相邻两个元素的值，如果反序则交换。若按升序排，每一趟将最大元素交换到最后位置。

两层for循环实现，其中外层循环控制最多n-1趟扫描，内层循环进行每趟扫描的比较和交换。

布尔变量是为了减少在排序完成后不再扫描。即，如果上次扫描没有交换元素则说明已经排序好，不再扫描。

稳定性：稳定（若将if判断条件改成>=则不稳定了）。

时间复杂度：

最好情况（已排序）：只需一趟扫描，比较n-1次，移动0次。时间复杂度为O（n）。

最坏情况（逆序）：需要n-1趟扫描，比较次数n（n-1）/2,移动次数n（n-1）/2.时间复杂度为O（n^2）。

所以冒泡排序的时间复杂度介于O（n）和O（n^2）之间。

空间复杂度：O（1）

Java实现：

//交换排序：冒泡排序
public class M003 {
	public static void main(String[] args) {
		int[] number = { 21, 32, 2, 4, 65, 90, 54 };
		int result[] = bubbleSort(number);
		for (int i = 0; i < result.length; i++) {
			System.out.print(result[i] + " ");
		}
	}

	/**
	 * 
	 * @param exchenge
	 *            布尔变量是为了减少在排序完成后不再扫描。 即，如果上次扫描没有交换元素则说明已经排序好，不再扫描。
	 * @return
	 */
	private static int[] bubbleSort(int[] number) {
		boolean exchange = true;
		for (int i = 1; i < number.length && exchange; i++) {
			exchange = false;
			for (int j = 0; j < number.length - i; j++) {
				if (number[j] > number[j + 1]) {
					int temp = number[j];
					number[j] = number[j + 1];
					number[j + 1] = temp;
					exchange = true;
				}
			}
		}
		return number;
	}
}

学习笔记, 数据结构, Java, 排序

I feedback.
Let me know what you think of this article on twitter @Yanlei_Hello or leave a comment below!