手把手教你搞懂冒泡排序和选择排序

冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换的数据为止。

算法流程

1. 比较相邻的元素。如果当前的元素大于下一个元素，则交换它们的位置。
2. 对每一对相邻元素都执行步骤 1，从开始第一对到结尾最后一对。在这步操作后，最后的元素会是最大的数。
3. 针对所有的元素重复执行步骤 1~2，除了最后一个。
4. 重复步骤 1~3，直到排序完成。

代码实现

以下是冒泡排序的Python实现示例代码：

def bubble_sort(arr):
    n = len(arr)
    # 遍历所有数组元素
    for i in range(n):
        # Last i elements are already sorted
        for j in range(0, 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]

示例说明

假设有一个数组 [64, 34, 25, 12, 22, 11, 90] 需要进行冒泡排序，其排序流程如下表所示：

初始数组	第一轮冒泡排序	第二轮冒泡排序	第三轮冒泡排序	...	最终排序结果
[64, 34, 25, 12, 22, 11, 90]	[34, 25, 12, 22, 11, 64, 90]	[25, 12, 22, 11, 34, 64, 90]	[12, 22, 11, 25, 34, 64, 90]	...	[11, 12, 22, 25, 34, 64, 90]

选择排序

选择排序（Selection Sort）是一种简单直观的排序算法。其基本思想是每次选择最小的元素放到已排序的队列末尾。

算法流程

1. 首先在未排序的序列中找到最小（大）元素，存放到排序序列的起始位置。
2. 再从剩余未排序的元素中继续寻找最小（大）元素，放到已排序的序列的末尾。
3. 重复步骤 2，直到所有的元素均排序完毕。

代码实现

以下是选择排序的Python实现示例代码：

def selection_sort(arr):
    n = len(arr)
    # 遍历所有数组元素
    for i in range(n):
        # 查找最小元素的位置
        min_idx = i
        for j in range(i+1, n):
            if arr[min_idx] > arr[j]:
                min_idx = j
        # 将找到的最小元素交换到当前位置
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

示例说明

假设有一个数组 [64, 34, 25, 12, 22, 11, 90] 需要进行选择排序，其排序流程如下表所示：

初始数组	第一轮选择排序	第二轮选择排序	第三轮选择排序	...	最终排序结果
[64, 34, 25, 12, 22, 11, 90]	[11, 34, 25, 12, 22, 64, 90]	[11, 12, 25, 34, 22, 64, 90]	[11, 12, 22, 34, 25, 64, 90]	...	[11, 12, 22, 25, 34, 64, 90]

总结

冒泡排序和选择排序都是简单但低效的排序算法，它们的时间复杂度都是O(n^2)。尽管如此，在某些情况下，比如对于简单的数据结构或是小规模的数据，这些排序算法可能是最优的选择。为了更加高效地排序，我们需要学习更加高级和复杂的排序算法，比如快速排序、归并排序等。