算法基础之冒泡排序

2019-11-06 07:37:42

字体：大中小

来源：转载

供稿：网友

冒泡排序的思想是

是让最大的数浮动到数组最后的位置，其次大的数浮动到数组倒数第二个位置。当然，你也可以从大到小排序，也可以从后向前冒泡。其特征操作是相邻元素的比较和交换。

伪代码表示

BUBBLE-SORT(A)for i = A.length to 1 for j = 1 to i if A[j] < A[j - 1] exchance A[j] and A[j - 1]

java表示

public static int[] bubbleSort(int[] queue) { if (queue == null || queue.length < 2) { return queue; } int temp; for (int i = queue.length - 1; i > 0; i--) { for (int j = 0; j < i; j++) { if (queue[j + 1] < queue[j]) { temp = queue[j]; queue[j] = queue[j + 1]; queue[j + 1] = temp; } } } return queue; }

排序过程大致为：

数组编号	0	1	2	3	4	5
初始状态	5	2	4	6	1	3
第一次比较	2	5	4	6	1	3
第二次比较	2	4	5	6	1	3
第三次比较	2	4	5	6	1	3
第四次比较	2	4	5	1	6	3
第五次比较（第一次排序）	2	4	5	1	3	6
第二次排序	2	4	1	3	5	6
第三次排序	2	1	3	4	5	6
第四次排序	1	2	3	4	5	6
第五次排序	1	2	3	4	5	6

冒泡排序的时空复杂度

1、其外层循环执行 N - 1次。内层循环最多的时候执行N次，最少的时候执行1次，平均执行 (N+1)/2次。所以循环体内的比较交换约执行 (N - 1)(N + 1) / 2 = (N^2 - 1)/2次。其复杂度为O(N^2)。 2、冒泡排序算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；

冒泡排序的简单改进

从例子处我们可以看到当第四次外层循环完成后，排序就完成了。后面的循环只有比较，而没有交换。就说明数组已经是有序的了，这时可以跳出循环。因此，我们可以设置一个布尔变量，记录一次外层循环中是否发生交换，如果未发生交换，跳出算法。

Java代码表示

public static int[] bubbleSort(int[] queue) { if (queue == null || queue.length < 2) { return queue; } int temp; boolean flag = false; for (int i = queue.length - 1; i > 0; i--) { for (int j = 0; j < i; j++) { if (queue[j + 1] < queue[j]) { temp = queue[j]; queue[j] = queue[j + 1]; queue[j + 1] = temp; flag = true; } } if(!flag){ return queue; } } return queue;

以上，就是笔者对于冒泡排序的初略见解。

上一篇：设计模式之策略模式

下一篇：【数组】Leetcode编程题解：289. Game of Life Add to List