冒泡排序 (Bubble Sort)
冒泡排序是一种简单的排序算法，它通过反复比较相邻元素并交换它们的位置，将较大的元素“滚”到数组的末尾。这个过程重复进行，直到整个数组排序完成。每一轮比较后，最大的元素会“冒泡”到当前未排序部分的最后一个位置。
Bubble Sort is a simple sorting algorithm that repeatedly compares adjacent elements and swaps them if they are in the wrong order. This causes the larger elements to "bubble" to the end of the array. The process is repeated until the entire array is sorted. After each round of comparisons, the largest element ends up in the last position of the unsorted portion.
1. What is Bubble Sort and How Does It Work?
[English] Bubble sort works by repeatedly stepping through the list, comparing each pair of adjacent elements, and swapping them if they are in the wrong order. This process is repeated for each element in the list until no more swaps are needed, indicating that the list is sorted.
Steps:
- Start with the first element and compare it with the next element.
- If the current element is greater than the next element, swap them.
- Move to the next pair of elements and repeat the process.
- Continue this process until the largest element is "bubbled" to the end of the array.
- Repeat the process for the next largest element in the remaining unsorted portion until the entire array is sorted.
Example:
Initial array: [5, 3, 8, 4, 2]
Pass 1:
[5, 3, 8, 4, 2] -> [3, 5, 8, 4, 2] -> [3, 5, 8, 4, 2] -> [3, 5, 4, 8, 2] -> [3, 5, 4, 2, 8]
Largest element 8 has bubbled to the last position.
Pass 2:
[3, 5, 4, 2, 8] -> [3, 5, 4, 2, 8] -> [3, 4, 5, 2, 8] -> [3, 4, 2, 5, 8]
Second largest element 5 has bubbled to its correct position.
Pass 3:
[3, 4, 2, 5, 8] -> [3, 4, 2, 5, 8] -> [3, 2, 4, 5, 8] -> [3, 2, 4, 5, 8]
Third largest element 4 has bubbled to its correct position.
Pass 4:
[3, 2, 4, 5, 8] -> [2, 3, 4, 5, 8]
Fourth largest element 3 has bubbled to its correct position.
Sorted array: [2, 3, 4, 5, 8]Behind the Scenes: The largest element in the array is moved to its correct position at the end of each pass, reducing the range of unsorted elements by one.
[Chinese] 冒泡排序通过反复遍历列表，比较每对相邻元素，并在它们的顺序错误时交换它们的位置。这一过程对列表中的每个元素重复进行，直到不再需要交换，表明列表已排序完成。
步骤:
- 从第一个元素开始，将其与下一个元素进行比较。
- 如果当前元素大于下一个元素，则交换它们。
- 移动到下一对元素，重复此过程。
- 继续此过程，直到最大的元素“冒泡”到数组的末尾。
- 对未排序部分的下一个最大元素重复此过程，直到整个数组排序完成。
示例:
初始数组: [5, 3, 8, 4, 2]
第一轮:
[5, 3, 8, 4, 2] -> [3, 5, 8, 4, 2] -> [3, 5, 8, 4, 2] -> [3, 5, 4, 8, 2] -> [3, 5, 4, 2, 8]
最大元素 8 已经冒泡到最后一个位置。
第二轮:
[3, 5, 4, 2, 8] -> [3, 5, 4, 2, 8] -> [3, 4, 5, 2, 8] -> [3, 4, 2, 5, 8]
第二大的元素 5 已经冒泡到正确的位置。
第三轮:
[3, 4, 2, 5, 8] -> [3, 4, 2, 5, 8] -> [3, 2, 4, 5, 8] -> [3, 2, 4, 5, 8]
第三大的元素 4 已经冒泡到正确的位置。
第四轮:
[3, 2, 4, 5, 8] -> [2, 3, 4, 5, 8]
第四大的元素 3 已经冒泡到正确的位置。
排序后的数组: [2, 3, 4, 5, 8]Behind the Scenes: 数组中的最大元素在每一轮后移动到正确位置，逐渐减少未排序元素的范围。
2. How to Implement Bubble Sort in Python?
[English] Here is the Python code to implement the bubble sort algorithm.
def bubble_sort(arr):
n = len(arr)
for i in range(n):
# Last i elements are already in place
for j in range(0, n - i - 1):
# Traverse the array from 0 to n-i-1
# Swap if the element found is greater than the next element
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
# Example usage
arr = [5, 3, 8, 4, 2]
sorted_arr = bubble_sort(arr)
print("Sorted array:", sorted_arr)What Happens: The function bubble_sort sorts the input array in ascending order by repeatedly comparing and swapping adjacent elements.
Behind the Scenes: The outer loop ensures that after each pass, the largest unsorted element is placed at its correct position, while the inner loop performs the necessary comparisons and swaps.
[Chinese] 下面是冒泡排序算法的 Python 实现代码。
def bubble_sort(arr):
n = len(arr)
for i in range(n):
# 最后 i 个元素已经就位
for j in range(0, n - i - 1):
# 遍历数组从 0 到 n-i-1
# 如果找到的元素大于下一个元素，则交换它们
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
# 示例用法
arr = [5, 3, 8, 4, 2]
sorted_arr = bubble_sort(arr)
print("排序后的数组:", sorted_arr)What Happens: 函数 bubble_sort 通过反复比较和交换相邻元素来按升序排序输入数组。
Behind the Scenes: 外层循环确保每一轮之后，最大的未排序元素被放置在正确位置，而内层循环执行必要的比较和交换。
3. What is the Time Complexity of Bubble Sort?
[English] The time complexity of bubble sort is O(n^2) in the worst and average cases, where n is the number of elements in the array. This is because each element needs to be compared with every other element. In the best case, where the array is already sorted, the time complexity can be reduced to O(n) if the algorithm is optimized to stop early when no swaps are needed.
Time Complexity:
- Best Case:
O(n)(with optimization, when the array is already sorted) - Average Case:
O(n^2) - Worst Case:
O(n^2)
Space Complexity:
- Space Complexity:
O(1)(in-place sorting, no extra space needed)
[Chinese] 冒泡排序的时间复杂度在最坏情况和平均情况下都是 O(n^2)，其中 n 是数组中的元素数量。这是因为每个元素都需要与其他每个元素进行比较。在最好的情况下，如果数组已经排序好，并且算法优化为在不需要交换时提前停止，则时间复杂度可以降低到 O(n)。
时间复杂度:
- 最好情况:
O(n)（如果已经排序且算法优化） - 平均情况:
O(n^2) - 最坏情况:
O(n^2)
空间复杂度:
- 空间复杂度:
O(1)（原地排序，不需要额外空间）
4. When Should You Use Bubble Sort?
[English] Bubble sort is generally not used for
large datasets due to its O(n^2) time complexity, which makes it inefficient compared to other sorting algorithms. However, it can be useful in cases where simplicity is more important than efficiency, or when working with small datasets.
Use Cases:
- Small datasets: Suitable for small lists where simplicity is preferred over efficiency.
- Teaching purposes: Ideal for introducing sorting algorithms due to its straightforward implementation and easy-to-understand mechanism.
- Detecting nearly sorted arrays: With optimization, it can be used to detect nearly sorted arrays where the number of swaps is minimal.
[Chinese] 由于其 O(n^2) 的时间复杂度，冒泡排序通常不适用于大型数据集，因为它与其他排序算法相比效率较低。然而，它在简单性比效率更重要的情况下或处理小型数据集时可能非常有用。
使用场景:
- 小数据集: 适用于小型列表，在简单性优先于效率的情况下效果良好。
- 教学目的: 由于其简单的实现和易于理解的机制，适合作为排序算法的入门教材。
- 检测近乎排序的数组: 通过优化，可以用于检测几乎排序的数组，其中交换的次数最少。
Recommend Resources:
Python: BubbleSort sorting algorithm by Oggi AI
Leave a Reply