交互式学习
五大经典排序算法
通过动态可视化，深入理解每种排序算法的工作原理、时间复杂度和适用场景。点击"开始排序"按钮，观察算法如何逐步将数据排列有序。
冒泡排序
Bubble Sort
通过重复遍历数组，比较相邻元素并在必要时交换位置，像气泡一样将最大/最小的元素逐步"冒泡"到序列的一端。
O(n²)
时间复杂度
O(1)
空间复杂度
稳定
排序稳定性
for i in range(n):
for j in range(n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
for j in range(n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
选择排序
Selection Sort
在未排序的部分中找到最小（或最大）元素，将其放到已排序序列的末尾。重复此过程，直到整个数组有序。
O(n²)
时间复杂度
O(1)
空间复杂度
不稳定
排序稳定性
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
插入排序
Insertion Sort
将数组分为已排序和未排序两部分，逐一取出未排序元素，在已排序部分中找到合适位置插入，类似整理扑克牌。
O(n²)
时间复杂度
O(1)
空间复杂度
稳定
排序稳定性
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
归并排序
Merge Sort
采用分治策略，将数组递归地分成两半分别排序，然后合并两个有序子序列。保证完全排序且稳定。
O(n log n)
时间复杂度
O(n)
空间复杂度
稳定
排序稳定性
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
快速排序
Quick Sort
选择一个基准元素，将数组分为两部分：小于基准的和大于基准的，然后递归排序两部分。是实际应用中最快的排序算法之一。
O(n log n)
时间复杂度
O(log n)
空间复杂度
不稳定
排序稳定性
def quick_sort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi-1)
quick_sort(arr, pi+1, high)
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi-1)
quick_sort(arr, pi+1, high)
动态可视化演示
冒泡排序
Bubble Sort
待排序
比较中
交换中
已排序
步骤:
0
动画速度:
50ms
当前步骤说明
点击"开始排序"按钮，观察冒泡排序的工作过程。冒泡排序会重复遍历数组，比较相邻元素，如果顺序错误就交换它们的位置。每一轮遍历后，最大的元素会"冒泡"到数组末尾。
时间复杂度对比
| 算法 | 最好情况 | 平均情况 | 最坏情况 | 空间复杂度 | 排序方式 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 原地排序 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 原地排序 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 原地排序 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 外部排序 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 原地排序 |