「排序算法」专题 10:冒泡排序(了解)
冒泡排序(了解)
前面的选择排序可以作为排序算法的入门算法,插入排序让我们看到了如何改进算法,充分利用每一轮循环的比较来加快排序的速度。冒泡排序的思想如同它的名字一样,每一轮都将一个元素「冒泡」到数组的末尾。
冒泡排序的基本思想
基本思想:外层循环每一次经过两两比较,把每一轮未排定部分最大的元素放到了数组的末尾;
依次将相邻的两个元素进行比较,把较大的元素交换到后面,这样一轮循环下来,就可以找到这一轮循环中最大的那个元素,我们把这个过程形象地称之为“冒泡”;
由于每一轮循环都「冒泡」出一个这一轮循环最大的元素,所以上一轮循环的最后一个元素,没有必要再参加下一轮循环的比较了;
「冒泡排序」有个特点:在遍历的过程中,提前检测到数组是有序的,从而结束排序,而不像「选择排序」那样,即使输入数据是有序的,「选择排序」依然需要很「死板地」地走完所有的流程。
冒泡排序第 1 版
Python 代码:
def bubble_sort_1(nums):
n = len(nums)
for i in range(0, n - 1):
for j in range(0, n - i - 1): # 注意临界值的选取
if nums[j] > nums[j + 1]:
swap(nums, j, j + 1)
冒泡排序第 2 版
Java 代码:
以下代码提交以后会出现超时,超时数据是规模较大的数据,一般情况下说明算法是正确的,但不高效。
public class Solution {
// 冒泡排序:超时
public int[] sortArray(int[] nums) {
int len = nums.length;
for (int i = len - 1; i >= 0; i--) {
// 先默认数组是有序的,只要发生一次交换,就必须进行下一轮比较,
// 如果在内层循环中,都没有执行一次交换操作,说明此时数组已经是升序数组
boolean sorted = true;
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1);
sorted = false;
}
}
if (sorted) {
break;
}
}
return nums;
}
private void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}
Python 代码:在「冒泡」的过程中检查数组是否已经排好序,如果已经是顺序数组,整个算法就可以终止了。
def bubble_sort_2(nums):
n = len(nums)
for i in range(0, n - 1):
sorted = True # 假设数组是排好序的
for j in range(0, n - i - 1): # 注意临界值的选取
if nums[j] > nums[j + 1]:
swap(nums, j, j + 1)
sorted = False # 只要发现有元素交换,就说明假设是错误的
# 如果一轮下来都没有元素交换,那么接下来的几轮就没有必要进行比较了
if sorted:
break
复杂度分析:
- 时间复杂度:$O(N^2)$,这里 $N$ 是数组的长度;
- 空间复杂度:$O(1)$,使用到常数个临时变量。
(本节完)