冒泡排序 #
1. 冒泡排序算法思想 #
冒泡排序(Bubble Sort)基本思想:
对
n
个元素,进行n-1
趟排序。第i (i = 1, 2, …)
趟排序时从数组的前n - i + 1
个元素的第1
个元素开始,依次对相邻两个元素进行比较,若前者大于后者,两者交换位置,否则不交换。
简单来说,「冒泡排序法」通过相邻元素之间的比较与交换,使值较大的元素从前面移到后面,值较小的元素逐步从后面移到前面。
这个过程就像水底的气泡一样向上冒,这也是冒泡排序法名字的由来。
2. 冒泡排序算法步骤 #
- 第
1
趟排序,从序列中前n
个元素的第1
个元素开始,相邻两个元素依次进行比较和交换:- 先将序列中第
1
个元素与第2
个元素进行比较,如果前者大于后者,则两者交换位置,否则不交换; - 然后将第
2
个元素与第3
个元素比较,如果前者大于后者,则两者交换位置,否则不交换; - 依次类推,直到第
n - 1
个元素与第n
个元素比较(或交换)为止。 - 经过第
1
趟排序,使得n
个元素中第i
个值最大元素被安置在第n
个位置上。
- 先将序列中第
- 第
2
趟排序,从序列中前n - 1
个元素的第1
个元素开始,相邻两个元素依次进行比较和交换:- 先将序列中第
1
个元素与第2
个元素进行比较,若前者大于后者,则两者交换位置,否则不交换; - 然后将第
2
个元素与第3
个元素比较,若前者大于后者,则两者交换位置,否则不交换; - 依次类推,直到对
n - 2
个元素与第n - 1
个元素比较(或交换)为止。 - 经过第
2
趟排序,使得数组中第2
个值最大元素被安置在第n - 1
个位置上。
- 先将序列中第
- 依次类推,对前
n - 2
个元素重复上述排序过程,直到某一趟排序过程中不出现元素交换位置的动作,则排序结束。
3. 冒泡排序动画演示 #
- 初始序列为:
[6, 2, 3, 5, 1, 4]
。 - 第
1
趟排序,从序列中前6
个元素的第1
个元素开始,相邻两个元素进行比较和交换::- 先将序列中第
1
个元素与第2
个元素进行比较,也就是将6
和2
进行比较。因为6 > 2
,所以两者交换位置,交换位置后,2
在第1
位,6
在第2
位。 - 然后将第
2
个元素与第3
个元素比较,也就是将2
和3
进行比较。因为2 < 3
,所以不用交换; - 依次类推,直到第
5
个元素与第6
个元素比较(或交换)为止。 - 经过第
1
趟排序,使得6
个元素中第6
个值最大元素被安置在第6
个位置上。此时序列变为:[2, 3, 5, 1, 4, 6]
。
- 先将序列中第
- 第
2
趟排序,从序列中前5
个元素的第1
个元素开始,相邻两个元素进行比较和交换::- 先将序列中第
1
个元素与第2
个元素进行比较,也就是将2
和3
进行比较。因为2 < 3
,所以不用交换; - 然后将第
2
个元素与第3
个元素比较,也就是将3
和4
进行比较。因为3 < 5
,所以不用交换; - 然后将第
3
个元素与第4
个元素比较,也就是将5
和1
进行比较。因为5 > 1
,所以两者交换位置,交换位置后,1
在第3
位,5
在第4
位。 - 依次类推,直到第
4
个元素与第5
个元素比较(或交换)为止。 - 经过第
2
趟排序,使得5
个元素中第5
个值最大元素被安置在第5
个位置上。此时序列变为:[2, 3, 1, 4, 5, 6]
。
- 先将序列中第
- 依次类推,对前
4
个元素重复上述排序过程,直到某一趟排序过程中不出现元素交换位置的动作,则排序结束。此时序列变为:[1, 2, 3, 4, 5, 6]
。
4. 冒泡排序算法分析 #
- 最佳时间复杂度:$O(n)$。最好的情况下(初始时序列已经是升序排列),则只需经过
1
趟排序,总共经过n - 1
次元素之间的比较,并且不移动元素,算法就可结束排序。因此,冒泡排序算法的最佳时间复杂度为 $O(n)$。 - 最坏时间复杂度:$O(n^2)$。最差的情况下(初始时序列已经是降序排列,或者最小值元素处在序列的最后),则需要进行
n - 1
趟排序,总共进行 $∑^n_{i=2}(i−1) = \frac{n(n−1)}{2}$ 次元素之间的比较,因此,冒泡排序算法的最坏时间复杂度为 $O(n^2)$。 - 冒泡排序适用情况:冒泡排序方法在排序过程中需要移动较多次数的元素,并且排序时间效率比较低。因此,冒泡排序方法比较适合于参加排序序列的数据量较小的情况,尤其是当序列的初始状态为基本有序的情况。
- 排序稳定性:由于元素交换是在相邻元素之间进行的,不会改变值相同元素的相对位置,因此,冒泡排序法是一种 稳定排序算法。
5. 冒泡排序代码实现 #
public void bubbleSort_1(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 tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
}
public void bubbleSort_2(int[] arr){
for(int i=0;i<arr.length;i++){
for(int j=0;j<arr.length-i-1;j++){
if(arr[j] > arr[j+1]){
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
}