排序算法之冒泡排序

发表于 | 分类于 ，

冒泡排序是一种稳定排序，时间复杂度为O(n^2)。

排序思想

依次交换相邻两个元素，使得大的数据往下沉（或小的数据往上附浮）。

排序过程

  1. 比较相邻的两个元素，如果前者比后者大，则交换两元素。否则，不交换。
  2. 重复第一步直到最后两个元素比较完成，此时，最大的元素已经在最后面了，此趟排序完成。
  3. 去除最后元素，重复上述两步，对最后元素之前的数据进行排序。
  4. 每趟排序完成后，大的数据会往下沉，也就是需要排序的数据会越来越少，直到没有任何一对数据需要排序，排序成功。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//大数下沉
public void sort(int[] array) {
	//控制总共循环次数
	for(int i=1; i<=array.length; i++) {
		for(int j=0; j<array.length-i; j++) {
			if(array[j] > array[j+1]) {
				int temp = array[j+1];
				array[j+1] = array[j];
				array[j] = temp;
			}
		}
		System.out.println("第"+i+"趟排序结果："+Arrays.toString(array));
	}
}

//小数上浮
public void sort2(int[] array) {
	for(int i=1; i<=array.length; i++) {
		for(int j=array.length-1; j>=i; j--) {
			if(array[j] <= array[j-1]) {
				int temp = array[j-1];
				array[j-1] = array[j];
				array[j] = temp;
			}
		}
		System.out.println("第"+i+"趟排序结果："+Arrays.toString(array));
	}
}

代码地址：
https://github.com/zhangyihao/Algorithms/blob/master/com.zhangyihao.algorithms/src/com/zhangyihao/algorithms/sort/BubbleSort.java