排序算法
SELECTION | BUBBLE | INSERTION | QUICK | MERGE
选择排序 (Selection Sort)
每次从未排序区间选取最小元素，与未排序区间的第一个元素交换，直到全部有序。思路简单，但无论数据如何都要做 O(n²) 次比较。
最佳 O(n²)
平均 O(n²)
最坏 O(n²)
for i from 0 to n-2:
minIdx = i
for j from i+1 to n-1:
if arr[j] < arr[minIdx]:
minIdx = j
swap arr[i] and arr[minIdx]
冒泡排序 (Bubble Sort)
相邻元素两两比较，若前者大于后者则交换。每轮“冒泡”会把当前未排序区间的最大值“冒”到末尾。可加标志位优化：若某轮无交换则提前结束。
最佳 O(n)
平均 O(n²)
最坏 O(n²)
for i from 0 to n-1:
swapped = false
for j from 0 to n-2-i:
if arr[j] > arr[j+1]:
swap arr[j] and arr[j+1]
swapped = true
if not swapped: break
插入排序 (Insertion Sort)
将数组视为“已排序 + 未排序”两部分，每次取未排序区第一个元素，在已排序区中从后往前找插入位置并插入。对近乎有序的数据非常高效。
最佳 O(n)
平均 O(n²)
最坏 O(n²)
for i from 1 to n-1:
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j--
arr[j+1] = key
快速排序 (Quick Sort)
分治思想：选一个基准（通常取首/尾/中），将数组划分为“小于基准”和“大于基准”两部分，再对两部分递归排序。平均性能优秀，但最坏情况（如已有序且选错基准）会退化为 O(n²)。
最佳 O(n log n)
平均 O(n log n)
最坏 O(n²)
function quickSort(arr, low, high):
if low < high:
pivot = partition(arr, low, high)
quickSort(arr, low, pivot - 1)
quickSort(arr, pivot + 1, high)
function partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j from low to high-1:
if arr[j] <= pivot:
i++; swap arr[i] and arr[j]
swap arr[i+1] and arr[high]
return i + 1
归并排序 (Merge Sort)
分治思想：将数组不断二分，直到子数组长度为 1，再两两合并成有序数组。稳定排序，时间复杂度恒为 O(n log n)，但需要 O(n) 额外空间。
最佳 O(n log n)
平均 O(n log n)
最坏 O(n log n)
function mergeSort(arr, left, right):
if left < right:
mid = (left + right) / 2
mergeSort(arr, left, mid)
mergeSort(arr, mid+1, right)
merge(arr, left, mid, right)
function merge(arr, left, mid, right):
// 将 arr[left..mid] 与 arr[mid+1..right] 合并为有序
L = arr[left..mid], R = arr[mid+1..right]
i=j=0, k=left
while i < len(L) and j < len(R):
if L[i] <= R[j]: arr[k++] = L[i++]
else: arr[k++] = R[j++]
copy remaining elements
动画演示 · 按当前标签运行对应算法
比较
交换
已排序
基准(pivot)