在程序员的世界里，排序算法无处不在。无论是开发面试、还是日常工程实践，排序都是基本功之一。今天，我将用最通俗易懂的方式，带你全面掌握10种常见排序算法，每种算法都配上了Python代码示例和详细讲解，帮你从入门到精通！

---

什么是排序算法？

排序算法是通过特定规则，将一组无序数据重新排列成有序数据的过程。排序可以是升序（从小到大）或降序（从大到小）。

排序算法通常关注两个核心指标：

• 时间复杂度：排序过程所需的时间。

• 空间复杂度：排序过程占用的额外空间。

---

目录预览

1. 冒泡排序（Bubble Sort）

2. 选择排序（Selection Sort）

3. 插入排序（Insertion Sort）

4. 希尔排序（Shell Sort）

5. 归并排序（Merge Sort）

6. 快速排序（Quick Sort）

7. 堆排序（Heap Sort）

8. 计数排序（Counting Sort）

9. 桶排序（Bucket Sort）

10. 基数排序（Radix Sort）

---

1. 冒泡排序（Bubble Sort）

核心思想：相邻元素两两比较，把最大的元素“冒泡”到最后。

Python代码：

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # 每次确定一个最大值
        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)

• 最坏：O(n²)

• 空间复杂度：O(1)

---

2. 选择排序（Selection Sort）

核心思想：每次找到剩余数组中最小（或最大）元素，放到已排序区域末尾。

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[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

时间复杂度

• 最好、最坏：O(n²)

• 空间复杂度：O(1)

---

3. 插入排序（Insertion Sort）

核心思想：构建有序序列，对未排序元素，在已排序序列中从后向前扫描，找到合适位置插入。

Python代码：

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >=0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr

时间复杂度

• 最好：O(n)

• 最坏：O(n²)

• 空间复杂度：O(1)

---

4. 希尔排序（Shell Sort）

核心思想：基于插入排序的改进，先对间隔的元素进行排序，再逐渐缩小间隔。

Python代码：

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j-gap]
                j -= gap
            arr[j] = temp
        gap //= 2
    return arr

时间复杂度

• 根据步长不同而不同，平均：O(n^1.3)

• 空间复杂度：O(1)

---

5. 归并排序（Merge Sort）

核心思想：采用分治法，把数组分成小块分别排序，然后合并。

Python代码：

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)

def merge(left, right):
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged += left[i:]
    merged += right[j:]
    return merged

时间复杂度

• 最好、最坏：O(n log n)

• 空间复杂度：O(n)

---

6. 快速排序（Quick Sort）

核心思想：分治策略，选一个“基准”，把小于它的放左边，大于它的放右边，然后递归。

Python代码：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    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²)（当序列有序时）

• 空间复杂度：O(log n)

---

7. 堆排序（Heap Sort）

核心思想：把数组构建成堆结构，不断取堆顶元素（最大/最小）。

Python代码：

def heapify(arr, n, i):
    largest = i 
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[l] > arr[largest]:
        largest = l
    if r < n and arr[r] > arr[largest]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    for i in range(n//2-1, -1, -1):
        heapify(arr, n, i)
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
    return arr

时间复杂度

• 最好、最坏：O(n log n)

• 空间复杂度：O(1)

---

8. 计数排序（Counting Sort）

核心思想：适用于整数数据，统计每个数出现次数。

Python代码：

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1
    result = []
    for i, c in enumerate(count):
        result.extend([i]*c)
    return result

时间复杂度

• 最好、最坏：O(n + k) （k是最大元素值）

• 空间复杂度：O(k)

---

9. 桶排序（Bucket Sort）

核心思想：将数据分到固定数量的桶里，每个桶单独排序。

Python代码：

def bucket_sort(arr):
    if len(arr) == 0:
        return arr
    min_val, max_val = min(arr), max(arr)
    bucket_range = (max_val - min_val) / len(arr) + 1
    buckets = [[] for _ in range(len(arr))]
    for num in arr:
        index = int((num - min_val) // bucket_range)
        buckets[index].append(num)
    result = []
    for bucket in buckets:
        result.extend(sorted(bucket))
    return result

时间复杂度

• 平均：O(n+k)

• 空间复杂度：O(n+k)

---

10. 基数排序（Radix Sort）

核心思想：按位数（个位、十位、百位……）依次比较排序，适用于整数。

Python代码：

def radix_sort(arr):
    max_num = max(arr)
    exp = 1
    while max_num // exp > 0:
        counting_sort_exp(arr, exp)
        exp *= 10

def counting_sort_exp(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1
    for i in range(1, 10):
        count[i] += count[i-1]
    for i in range(n-1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index]-1] = arr[i]
        count[index] -= 1
    for i in range(n):
        arr[i] = output[i]

时间复杂度

• 最好、最坏：O(nk) （k是最大数位数）

• 空间复杂度：O(n+k)

---

总结表格

排序算法	最好时间复杂度	最坏时间复杂度	空间复杂度	稳定性
冒泡排序	O(n)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(1)	不稳定
插入排序	O(n)	O(n²)	O(1)	稳定
希尔排序	O(n log n)	O(n²)	O(1)	不稳定
归并排序	O(n log n)	O(n log n)	O(n)	稳定
快速排序	O(n log n)	O(n²)	O(log n)	不稳定
堆排序	O(n log n)	O(n log n)	O(1)	不稳定
计数排序	O(n+k)	O(n+k)	O(k)	稳定
桶排序	O(n+k)	O(n²)	O(n+k)	稳定
基数排序	O(nk)	O(nk)	O(n+k)	稳定

---

写在最后

学习排序算法，不是为了死记硬背，而是为了理解不同场景下，选择最合适的算法。掌握了这些排序，你在面试和工作中都会更加游刃有余！

如果这篇文章对你有帮助，记得点赞、收藏+关注！