数据结构与算法：冒泡排序

女爷i 2023-06-04 06:53 21阅读 0赞

## 1.冒泡排序 ##

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

**原理：**

1.  比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.  对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.  针对所有的元素重复以上的步骤，除了最后一个。
4.  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

**例如：**

有一个无序数列：3, 6, 5, 8, 4, 2, 7, 9, 1, 希望从小到大排序。

**第一轮：**（3, 6, 5, 8, 4, 2, 7, 9, 1）

3与6比较，3<6，元素位置不变；3, 6, 5, 8, 4, 2, 7, 9, 1  
6与5比较，6>5，元素6和5交换位置；3, 5, 6 , 8, 4, 2, 7, 9, 1  
6与8比较，6<8，元素位置不变；3, 5, 6 , 8, 4, 2, 7, 9, 1  
8与4比较，8>4，元素8和4交换位置；3, 5, 6 , 4, 8, 2, 7, 9, 1  
8与2比较，8>2，元素8和2交换位置；3, 5, 6 , 4, 2, 8, 7, 9, 1  
8与7比较，8>7，元素8和4交换位置；3, 5, 6 , 4, 2, 7, 8, 9, 1  
8与9比较，8<9，元素位置不变；3, 5, 6 , 4, 2, 7, 8, 9, 1  
9与1比较，9>1，元素9和1交换位置；3, 5, 6 , 4, 2, 7, 8, 1, 9

此时，元素9作为数列最大元素，移动到了最右侧；

**第二轮：**（3, 5, 6 , 4, 2, 7, 8, 1, 9）

3与5比较，3<5，元素位置不变；3, 5, 6 , 4, 2, 7, 8, 1, 9  
5与6比较，5<6，元素位置不变；3, 5, 6 , 4, 2, 7, 8, 1, 9  
6与4比较，6>4，元素6和4交换位置；3, 5, 4 , 6, 2, 7, 8, 1, 9  
6与2比较，6>2，元素6和2交换位置；3, 5, 4 , 2, 6, 7, 8, 1, 9  
6与7比较，6<7，元素位置不变；3, 5, 4 , 2, 6, 7, 8, 1, 9  
7与8比较，7<8，元素位置不变；3, 5, 4 , 2, 6, 7, 8, 1, 9  
8与1比较，8>1，元素8和1交换位置；3, 5, 4 , 2, 6, 7, 1, 8, 9

此时，8和9都是有序的；

**第三轮：**（3, 5, 4 , 2, 6, 7, 1, 8, 9）

按照上面操作，结果是3, 4, 2 , 5, 6, 1, 7, 8, 9

此时，7,8,9是有序的；

**第四轮：**（3, 4, 2 , 5, 6, 1, 7, 8, 9）

交换后，结果是3, 2, 4 , 5, 1, 6, 7, 8, 9

此时，6,7,8,9是有序的

**第五轮：**（3, 2, 4 , 5, 1, 6, 7, 8, 9）

交换后，结果是2, 3, 4 , 1, 5, 6, 7, 8, 9

此时，5,6,7,8,9是有序的

**第六轮：**（2, 3, 4 , 1, 5, 6, 7, 8, 9）

交换后，结果是2, 3, 1 , 4, 5, 6, 7, 8, 9

此时，4,5,6,7,8,9是有序的

**第七轮：**（2, 3, 1 , 4, 5, 6, 7, 8, 9）

交换后，结果是2, 1, 3 , 4, 5, 6, 7, 8, 9

此时，3,4,5,6,7,8,9是有序的

**第八轮：**（2, 1, 3 , 4, 5, 6, 7, 8, 9）

交换后，结果是1, 2, 3 , 4, 5, 6, 7, 8, 9

此时，所有元素都有序。**时间复杂度（O(n^2）**

代码：

def bubble_sort(nums):
        for i in range(len(nums) - 1):
            for j in range(len(nums) - i - 1):
                if nums[j] > nums[j + 1]:
                    nums[j], nums[j + 1] = nums[j + 1], nums[j]
        return nums

**优化：**

1.  若数列提前有序，及时结束；
2.  每一轮排序的最后，记录下最后一次元素交换的位置，那个位置也是无序数列的边界，再往后就是有序区；

def bubble_sort(nums):
        for i in range(len(nums) - 1):
            ex_flag = False  # 设置一个交换标志位
            for j in range(len(nums) - i - 1):
                
                if nums[j] > nums[j + 1]:
                    nums[j], nums[j + 1] = nums[j + 1], nums[j]
                    ex_flag = True
            if not ex_flag:
                return nums
        return nums