### 冒泡排序 冒泡排序是一种简单的排序算法，它重复地遍历要排序的列表，比较相邻的两个元素，并交换顺序错误的这对元素。这个过程会重复进行，直到没有需要交换的元素为止。冒泡排序的名字来源于较小的元素会像气泡一样慢慢“浮”到数列的顶端。 下面是Python实现冒泡排序的一个例子： ```python def bubble_sort(arr): n = len(arr) for i in range(n): # 最后 i 个元素已经排好序，不需要再比较 for j in range(0, n-i-1): # 如果当前元素大于下一个元素，则交换位置 if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr ``` 在每次迭代中，最大的元素会被移动到最后的位置。冒泡排序的时间复杂度是O(n²)，其中n是数组的长度。冒泡排序通常是教学用的算法，因为它简单但效率不高[^2]。 ### 快速排序 快速排序是一种高效的排序算法，采用分治法的策略来进行排序。它的基本思想是选择一个基准元素，然后将数组分为两部分，一部分包含小于基准的所有元素，另一部分包含大于基准的所有元素。接着，递归地对这两部分进行相同的排序操作，直到整个数组排序完成。 以下是Python中快速排序的一个实现示例： ```python def quick_sort(arr): if len(arr) <= 1: return arr else: # 选择基准值 pivot = arr[len(arr) // 2] # 分别存放比基准小和大的元素 left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] # 递归地对左右两边进行快排，并合并结果 return quick_sort(left) + middle + quick_sort(right) ``` 快速排序的平均时间复杂度是O(n log n)，但在最坏的情况下可以达到O(n²)。然而，由于其简单的实现和良好的性能，在实际应用中非常流行[^3]。 ### 合并排序 合并排序也是一种分治法策略的排序算法。它将输入数组分成两个半部分，分别对这两个半部分进行排序，然后将它们合并成一个有序的数组。合并排序的过程是递归的，它会一直将数组分成更小的部分，直到每个子数组只有一个元素，然后开始合并这些子数组。 下面是一个Python实现合并排序的例子： ```python def merge_sort(arr): if len(arr) > 1: # 找到数组中间点 mid = len(arr) // 2 left_half = arr[:mid] right_half = arr[mid:] # 递归调用合并排序 merge_sort(left_half) merge_sort(right_half) i = j = k = 0 # 合并左右两半 while i < len(left_half) and j < len(right_half): if left_half[i] < right_half[j]: arr[k] = left_half[i] i += 1 else: arr[k] = right_half[j] j += 1 k += 1 # 检查是否有剩余元素 while i < len(left_half): arr[k] = left_half[i] i += 1 k += 1 while j < len(right_half): arr[k] = right_half[j] j += 1 k += 1 return arr ``` 合并排序的时间复杂度总是O(n log n)，因为它总是将数组分成两半，并且合并步骤需要线性时间来合并两个半部分。合并排序适用于大型数据集，并且是稳定的排序算法[^3]。