一、冒泡排序
1.1.冒泡排序简介
bubblesort!💜
- 冒泡排序（bubblesort）是一种效率低下的排序方法，在元素规模很小时可以采用。元素规模较大时，最好使用其他排序方法。
- 之所以叫做冒泡排序，因为每一个元素都可以像小气泡一样，根据自身大小一点一点向数组的一侧移动。
1.2.冒泡排序思路
💡💡思路：
- 第一位元素与相邻元素进行比较，下面依次相邻元素比较
- 如果 左边元素 > 右边元素，交换（左边元素，右边元素）
- 如果比较发现次序不对，则将2个元素的位置互换。每一趟只能确定一个数归位
- 依次由左往右(由上往下)比较，最终较大的元素会向上浮起，犹如冒泡一般
1.3.时间复杂度
💡💡:
- 最好的情况下，列表本来就是有序的，则一趟扫描即可结束，共比较n-1次，无须交换。所以时间复杂度为O(n)
- 在最坏的情况下，元素逆序排列，则一共需要做n-1次扫描，每次扫描都必须比较n-1次，因此一共需做n(n-1)/2次比较和交换，时间复杂度为O(n^2)。
- 综上，时间复杂度为O(n^2)
1.4.空间复杂度
💡💡:
冒泡排序不需要占用太多的内存空间，仅需要一个交换时进行元素暂存的临时变量存储空间，因此空间复杂度为O(1)
1.5.代码实现
C++代码：
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int length)
{
// 外循环控制排序轮数(元素个数-1)
for (int i = 0; i <= length - 1; i++)
{
// 内循环负责2个元素的比较，j为下标
for (int j = 0; j < length - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
//交换两个元素的值
swap(arr[j], arr[j + 1]);
}
}
}
}
int main()
{
int arr[5] = {7,2,5,3,1};
int length = sizeof(arr) / sizeof(arr[0]); //获取数组长度
bubbleSort(arr, length);
for (int i = 0; i < length; i++)
{
cout << arr[i] << endl;
}
return 0;
}
// 输出结果
1
2
3
5
7
Python代码：
def bubbleSort(nums):
# 外循环控制排序轮数(元素个数-1)
for i in range(len(nums)-1):
# 内循环负责2个元素的比较，j为下标
for j in range(len(nums) -i-1):
# 判断2个元素大小
if nums[j]>nums[j+1]:
# 交换2个元素的位置
nums[j],nums[j+1] = nums[j+1],nums[j]
print(nums)
return nums
nums = [7,2,5,3,1]
print(bubbleSort(nums))
# 每一轮的输出结果
>>>[2,5,3,1,7][2,3,1,5,7][2,1,3,5,7][1,2,3,5,7][1,2,3,5,7] 1.6.优缺点
优点:
比较简单，空间复杂度较低，是稳定的；
缺点:
时间复杂度太高，效率慢；
