冒泡排序

发布日期: 2025-04-27

文章字数: 566

冒泡算法是对选择排序的一种优化，通过交换 nums[sortedIndex] 右侧的逆序对完成排序，是一种稳定排序算法。

练习题目: 力扣第 912 题数组排序，先不纠结时间复杂度。

想法

选择排序失去稳定性的原因，即每次都要交换最小元素nums[minIndex]和当前元素nums[sortedIndex]，这样可能会改变相同元素的相对位置。

所以优化的方向就在这里，你不要图省事儿直接把 nums[sortedIndex] 交换到 nums[minIndex]，而是模仿
在数组中部插入元素的操作，将 nums[sortedIndex..minIndex] 的元素整体向后移动一位，把 nums[sortedIndex + 1] 的位置空出来让 nums[sortedIndex] 这个元素去那里待着。

这就是冒泡排序实际做的事。

算法步骤

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

代码实现

# 对选择排序进行第一波优化，获得了稳定性
def sort(nums):
    n = len(nums)
    sortedIndex = 0
    while sortedIndex < n:
        # 在未排序部分中找到最小值 nums[minIndex]
        minIndex = sortedIndex
        for i in range(sortedIndex + 1, n):
            if nums[i] < nums[minIndex]:
                minIndex = i

        # 优化：将 nums[minIndex] 插入到 nums[sortedIndex] 的位置
        # 将 nums[sortedIndex..minIndex] 的元素整体向后移动一位
        minVal = nums[minIndex]
        # 数组搬移数据的操作
        for i in range(minIndex, sortedIndex, -1):
            nums[i] = nums[i - 1]
        nums[sortedIndex] = minVal

        sortedIndex += 1

代码上优化一下

def sortArray(self, nums: List[int]) -> List[int]:
    n = len(nums)
    sortedIndex = 0

    while sortedIndex < n:
        # 通过一次循环,一边找最小值一边换位，可以将一个元素换到正确的位置
        for i in range(n-1,sortedIndex-1,-1): # Output: n-1,n-2,..., 0 
            if nums[i] < nums[i-1]:
            nums[i],nums[i-1] = nums[i-1],nums[i]
        
        sortedIndex += 1
    return nums