【21天算法挑战赛】排序算法——冒泡排序

​💬💬作者有话想说：

💟作者简介：我目前是一个在校学生，想通过自己的学习努力让自己的技术、知识都慢慢提升，希望我们一起学习呀~💜💜💜
 
☂️兴趣领域：目前偏向于前端学习 💜💜💜
 
🎬> 活动地址：CSDN21天学习挑战赛
 
💜有话想说：写博客、记笔记并不是一种自我感动，把学到的东西记在脑子里才是最重要的，在这个过程中，不要浮躁，希望我们都可以越来越优秀！💜💜💜
 
🪀语言说明：代码实现我会用Python/C++~

​

一、冒泡排序

1.1.冒泡排序简介

bubblesort!💜

• 冒泡排序（bubblesort）是一种效率低下的排序方法，在元素规模很小时可以采用。元素规模较大时，最好使用其他排序方法。
• 之所以叫做冒泡排序，因为每一个元素都可以像小气泡一样，根据自身大小一点一点向数组的一侧移动。

1.2.冒泡排序思路

💡💡思路：

1. 第一位元素与相邻元素进行比较，下面依次相邻元素比较
2. 如果 左边元素 > 右边元素，交换（左边元素，右边元素）
3. 如果比较发现次序不对，则将2个元素的位置互换。每一趟只能确定一个数归位
4. 依次由左往右(由上往下)比较，最终较大的元素会向上浮起，犹如冒泡一般

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 
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1.6.优缺点

优点:

比较简单，空间复杂度较低，是稳定的；

缺点:

时间复杂度太高，效率慢；

​持续更新中，fighting！💜💜💜