def reverse_bubble_sort(arr): n = len(arr) # 外层循环控制轮次，每轮确定一个最小元素的位置 for i in range(n): swapped = False # 内层循环从末尾向前遍历，范围逐渐缩小 # 已排好序的最小元素在前端，因此右侧边界逐渐左移 for j in range(n-1, i, -1): # 若前一个元素（左侧）大于后一个元素（右侧），则交换 # 目的是将较小的元素向左移动（冒泡到前面） if arr[j-1] > arr[j]: arr[j-1], arr[j] = arr[j], arr[j-1] swapped = True # 若本轮无交换，说明数组已有序，提前退出 if not swapped: break return arr # 测试 arr = [64, 34, 25, 12, 22, 11, 90] print("排序前:", arr) print("逆向冒泡排序后（升序）:", reverse_bubble_sort(arr))

视频信息

答案文本 复制

视频字幕 复制

逆向冒泡排序是传统冒泡排序的一个变体。与传统冒泡排序从左向右遍历不同，逆向冒泡排序从右向左遍历数组。在每轮比较中，它将较小的元素向左移动，最终将最小元素冒泡到数组的前端。这种方法同样能够实现升序排序，但遍历方向相反。 逆向冒泡排序采用双层循环结构。外层循环控制排序轮次，每轮确定一个最小元素的最终位置。内层循环从数组末尾向前遍历，范围逐渐缩小，因为已排好序的最小元素在前端。当相邻元素顺序错误时执行交换操作，将较小元素向左移动。算法还包含优化机制：如果某轮没有发生交换，说明数组已有序，可以提前退出。 现在我们用具体示例来演示第一轮排序过程。给定数组64、34、25、12、22、11、90，我们从右向左开始比较。首先比较位置6的90和位置5的11，发现11小于90，所以交换它们。然后继续向左比较11和22，11更小，再次交换。这样逐步进行，直到最小元素11移动到数组的开头位置。 现在展示完整的多轮排序过程。第一轮后，最小元素11已经到达正确位置。第二轮确定次小元素12的位置，内层循环范围缩小到从位置2开始。每轮排序后，已排序的部分用绿色标记，逐渐扩大。经过5轮排序，整个数组变为有序。算法的优化机制确保当某轮没有交换发生时，可以提前结束排序过程。 现在分析逆向冒泡排序的算法复杂度。时间复杂度方面，最坏情况是O(n²)，发生在数组完全逆序时，需要进行最多的比较和交换。最好情况是O(n)，当数组已经有序时，只需一轮遍历就能确定无需交换。平均情况仍为O(n²)。空间复杂度为O(1)，因为只使用了常数个额外变量，是原地排序算法。提前退出的优化机制能够在最好情况下显著提升性能。