当前位置：首页 > article >正文

【算法】排序算法

article 2024/11/13 11:58:36

排序算法是计算机科学中用于将一组数据按一定顺序重新排列的算法。常见的排序算法主要有以下几种，每种算法有其优缺点和适用场景。以下是几种常用的排序算法及其简要介绍：

1. 冒泡排序（Bubble Sort）

原理：重复地遍历待排序的序列，每次比较相邻的元素并交换它们的位置，使得每一趟遍历都会将当前未排序部分中最大的元素“冒泡”到最后。

时间复杂度：O(n^2)

代码示例：

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

特点：简单直观，但效率较低，适合小规模或近乎有序的数据。

2. 选择排序（Selection Sort）

原理：每次从未排序的部分中找到最小（或最大）的元素，放到已排序部分的末尾。这样在排序的过程中，已排序部分逐渐变长，未排序部分逐渐缩短。

时间复杂度：O(n^2)

代码示例：

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

特点：不稳定排序，交换次数少，但效率低，适合数据量小的情况。

3. 插入排序（Insertion Sort）

原理：将未排序的元素插入到已排序部分的适当位置，类似于玩扑克牌时整理手牌的过程。

时间复杂度：O(n^2)

代码示例：

def insertion_sort(arr):
    n = len(arr)
    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
    return arr

特点：稳定排序，适合小规模数据或部分有序的数据，效率比冒泡排序高。

4. 快速排序（Quick Sort）

原理：选择一个“基准”元素，将序列划分为小于和大于该基准的两个部分，分别递归地排序这两个部分。

时间复杂度：平均 O(n log n)，最坏 O(n^2)

代码示例：

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)

特点：通常是最快的排序算法之一，但不稳定，且在最坏情况下（如数组已排序）会退化。

5. 归并排序（Merge Sort）

原理：将数组分成两半，分别排序后合并两个有序部分，递归地应用此过程直到只剩一个元素。

时间复杂度：O(n log 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)

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

特点：稳定排序，适合大规模数据的排序，但需要额外的存储空间。

6. 堆排序（Heap Sort）

原理：构建一个最大堆（或最小堆），每次将堆顶元素放到已排序部分的末尾，并调整堆。

时间复杂度：O(n log n)

代码示例：

def heap_sort(arr):
    def heapify(arr, n, i):
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
        if left < n and arr[left] > arr[largest]:
            largest = left
        if right < n and arr[right] > arr[largest]:
            largest = right
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            heapify(arr, n, largest)
    
    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

特点：不稳定排序，适合大规模数据的排序，不需要额外的存储空间。

7. 基数排序（Radix Sort）

原理：按位数对数据进行多次排序，从最低位到最高位逐位排序，常用于整数排序。

时间复杂度：O(d ⋅ (n + k)) （其中 d 是位数，k 是基数）

代码示例：

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

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