2、冒泡排序算法
简介
估计我们在各个算法书上介绍排序时，第一个估计都是冒泡排序。主要是这个排序算法思路最简单，也最容易理解，（也可能是它的名字好听，哈哈），学过的老哥们也一起来复习一下吧，我们一起深挖一下冒泡排序。
冒泡排序的基本思想是，两两比较相邻记录的关键字，如果是反序则交换，直到没有反序为止。冒泡一次冒泡会让至少一个元素移动到它应该在的位置，那么如果数组有 n 个元素，重复 n 次后则能完成排序。根据定义可知那么冒泡排序显然是一种比较类排序。
最简单的排序实现
我们来看一下这段代码
Java Code:
class Solution {
public int[] sortArray(int[] nums) {
int len = nums.length;
for (int i = 0; i < len; ++i) {
for (int j = i+1; j < len; ++j) {
if (nums[i] > nums[j]) {
swap(nums,i,j);
}
}
}
return nums;
}
public void swap(int[] nums,int i,int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
Python Code:
from typing import List
class Solution:
def sortArray(self, nums: List[int])->List[int]:
leng = len(nums)
for i in range(0, leng):
for j in range(i + 1, leng):
if nums[i] > nums[j]:
self.swap(nums, i, j)
return nums
def swap(self, nums: List[int], i: int, j: int):
temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
我们来思考一下上面的代码，每次让关键字 nums[i] 和 nums[j] 进行比较如果 nums[i] > nums[j] 时则进行交换，这样 nums[0] 在经过一次循环后一定为最小值。那么这段代码是冒泡排序吗？
显然不是，我们冒泡排序的思想是两两比较相邻记录的关键字，注意里面有相邻记录，所以这段代码不是我们的冒泡排序，下面我们用动图来模拟一下冒泡排序的执行过程，看完之后一定可以写出正宗的冒泡排序。
动画模拟
代码
class Solution {
public int[] sortArray(int[] nums) {
int len = nums.length;
for (int i = 0; i < len; ++i) {
for (int j = 0; j < len - i - 1; ++j) {
if (nums[j] > nums[j+1]) {
swap(nums,j,j+1);
}
}
}
return nums;
}
public void swap(int[] nums,int i,int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
上图中的代码则为正宗的冒泡排序代码，但是我们是不是发现了这个问题
我们此时数组已经完全有序了，可以直接返回，但是动图中并没有返回，而是继续执行，那我们有什么办法让其完全有序时，直接返回，不继续执行吗？
我们设想一下，我们是通过 nums[j] 和 nums[j+1] 进行比较，如果大于则进行交换，那我们设想一下，如果一个完全有序的数组，我们进行冒泡排序，每次比较发现都不用进行交换。
那么如果没有交换则说明当前完全有序。那我们可不可以通过一个标志位来进行判断是否发生了交换呢？当然是可以的
我们来对冒泡排序进行改进
代码
Java Code:
class Solution {
public int[] sortArray(int[] nums) {
int len = nums.length;
//标志位
boolean flag = true;
//注意看 for 循环条件
for (int i = 0; i < len && flag; ++i) {
//如果没发生交换，则依旧为false，下次就会跳出循环
flag = false;
for (int j = 0; j < len - i - 1; ++j) {
if (nums[j] > nums[j+1]) {
swap(nums,j,j+1);
//发生交换，则变为true,下次继续判断
flag = true;
}
}
}
return nums;
}
public void swap(int[] nums,int i,int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
Python Code:
from typing import List
class Solution:
def sortArray(self, nums: List[int])->List[int]:
leng = len(nums)
# 标志位
flag = True
for i in range(0, leng):
if not flag:
break
flag = False
for j in range(0, leng - i - 1):
if nums[j] > nums[j + 1]:
self.swap(nums, j, j + 1)
# 发生交换，则变为true，下次继续判断
flag = True
return nums
def swap(self, nums: List[int], i: int, j: int):
temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
这样我们就避免掉了已经有序的情况下无意义的循环判断。
时间复杂度分析
最好情况，就是要排序的表完全有序的情况下，根据改进后的代码，我们只需要一次遍历即可，
只需 n -1 次比较，时间复杂度为 O(n)。最坏情况时，即待排序表逆序的情况，则需要比较(n-1) + (n-2) +.... + 2 + 1= n*(n-1)/2 ，并等量级的交换，则时间复杂度为 O(n^2)。*
平均情况下，需要 n(n-1)/4 次交换操作，比较操作大于等于交换操作，而复杂度的上限是 O(n^2)，所以平均情况下的时间复杂度就是 O(n^2)。
空间复杂度分析
因为冒泡排序只是相邻元素之间的交换操作，只用到了常量级的额外空间，所以空间复杂度为 O(1)
稳定性分析
那么冒泡排序是稳定的吗？当然是稳定的，我们代码中，当 nums[j] > nums[j + 1] 时，才会进行交换，相等时不会交换，相等元素的相对位置没有改变，所以冒泡排序是稳定的。
| 算法名称 | 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 | 空间复杂度 | 是否稳定 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
