排序算法——冒泡排序

一、冒泡排序

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 <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.优缺点

优点:

比较简单,空间复杂度较低,是稳定的;

缺点:

时间复杂度太高,效率慢;