欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2.冒泡排序(Bubble Sort)

程序员文章站 2022-07-08 14:44:37
...

1.基本思想

每次比较两个相邻元素,如果它们的顺序错误就把它们交换过来。每一轮只能确定将一个数归位(归位指的是已经归回到正确的顺序)。

2.算法设计

例如将99、25、12、18、76这五个数从小到大排序,那也就是说越大的数越靠后(关键话)

  1. 首先比较第一位和第二位的大小,目前第一位是99,第二为25。发现25比99小,上面也说了越大的数越靠后,那么此时需要交换两个数的位置。得:25 99 12 18 76
  2. 按照刚刚的方法,继续比较第二位和第三位的大小,12比99小,那么需要交换两个数的位置。得:25 12 99 18 76
  3. 比较第三位和第四位的大小,99比18大,交换两个数的位置。得:25 12 18 99 76
  4. 比较第四位和第五位的大小,99比78大,交换两个数的位置。得:25 12 18 76 99

经过4次比较,就发现最大的数语句归位(已经在最后一位)。回忆下,每次都是比较相邻的两个数的大小,如果后面的数比前面的数小就交换两个数的位置,一直比较下去直到最后两个数比较完毕,最大的数就在最后一位。就像一个气泡,一步一步往上翻滚。
2.冒泡排序(Bubble Sort)

到这里只是第一轮,即只将最大的数归位而已。还需要继续重复刚才的过程,将剩下的4个数归位。
现在开始第二轮,目的是为了将第二大的数归位。

  1. 首先还是比较第一位和第二位的大小,目前第一位是25,第二位是12,第二位比第一位小,交换位置。得:12 25 18 76 99
  2. 接着比较第二位和第三位,18比25小,交换位置。得:12 18 25 76 99
  3. 接着比较第三位和第四位,76比25大,不用交换。得:12 18 25 76 99
  4. 此时已经不需要比较第四位和第五位,因为在第一轮中已经确定第五位存放的是最大的数了

第三轮也是这样,目的是确定第三大的数归位(可能发现数据顺序没有变化,所以觉得第四轮不用进行,这里的数据纯属巧合,可以换个数据试试),可得:12 18 25 76 99

第四轮一样,可得:12 18 25 76 99

第五轮呢?第五轮就不用进行啦,因为前四轮已经把4个数据归位,那么最后一个数自然也是归位。

3.代码

public class BubbleSort {
	public static void main(String[] args) {
		int[] a = {25,12,18,76,99};
		// 5个数据,我们只需要执行4轮就可以归位,即a.length-1
		for(int i = 0; i < a.length-1; i++) {
			// 完成几轮表示几个数据已经归位,那么已经归位的数就不用去比较
			for(int j = 0; j < a.length-i-1; j++) {
				// 如果第一个数大于第二个数,则交换
				if(a[j] > a[j+1]) {
					int temp = a[j];
					a[j] = a[j+1];
					a[j+1] = temp;
				}
			}
		}
		
		System.out.println(Arrays.toString(a));
	}
}

4.复杂度

  • 时间复杂度

冒泡排序的核心部分就是双重嵌套循环,可得时间复杂度为O(N^2)

  • 空间复杂度

不难看出为O(N)

5.优缺点

  • 优点

设计比较简单,空间复杂度较低,是稳定的

  • 缺点

速度太慢了。