10大排序总结

1. 冒泡排序 (Bubble Sort)

def bubble_sort(arr):
    n = len(arr)
    # 遍历数组中的每个元素
    for i in range(n):
        # 内层循环，从数组的第一个元素到倒数第 i + 1 个元素
        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)

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

3. 插入排序 (Insertion Sort)

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

4. 归并排序 (Merge Sort)

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # 找到数组的中间点
        L = arr[:mid]        # 将数组分成两部分
        R = arr[mid:]

        merge_sort(L)  # 递归排序左半部分
        merge_sort(R)  # 递归排序右半部分

        i = j = k = 0
        # 合并两个已排序的子数组
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        # 检查是否还有剩余的元素
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
    return arr

5. 快速排序 (Quick Sort)

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)

6. 堆排序 (Heap Sort)

def heapify(arr, n, i):
    largest = i  # 假设当前节点是最大值
    l = 2 * i + 1  # 左子节点
    r = 2 * i + 2  # 右子节点

    # 如果左子节点存在且大于当前节点
    if l < n and arr[i] < arr[l]:
        largest = l

    # 如果右子节点存在且大于当前最大值
    if r < n and arr[largest] < arr[r]:
        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

7. 希尔排序 (Shell Sort)

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

8. 计数排序 (Counting Sort)

def counting_sort(arr):
    max_val = max(arr)
    m = max_val + 1
    count = [0] * m

    # 统计每个元素的个数
    for a in arr:
        count[a] += 1
    i = 0
    for a in range(m):
        for c in range(count[a]):
            arr[i] = a
            i += 1
    return arr

9. 基数排序 (Radix Sort)

def counting_sort_for_radix(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]

    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1

    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort_for_radix(arr, exp)
        exp *= 10
    return arr

10. 桶排序 (Bucket Sort)

def bucket_sort(arr):
    if len(arr) == 0:
        return arr

    bucket = []
    slot_num = 10  # 桶的数量
    for i in range(slot_num):
        bucket.append([])

    # 将元素分配到不同的桶中
    for j in arr:
        index = int(slot_num * j)
        bucket[index].append(j)

    # 对每个桶中的元素进行排序
    for i in range(slot_num):
        bucket[i] = insertion_sort(bucket[i])

    k = 0
    for i in range(slot_num):
        for j in range(len(bucket[i])):
            arr[k] = bucket[i][j]
            k += 1
    return arr

11. Tim Sort (Tim Sort)

MIN_MERGE = 32

def calc_min_run(n):
    r = 0
    while n >= MIN_MERGE:
        r |= n & 1
        n >>= 1
    return n + r

def insertion_sort_for_timsort(arr, left, right):
    for i in range(left + 1, right + 1):
        temp = arr[i]
        j = i - 1
        while j >= left and arr[j] > temp:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = temp

def merge_for_timsort(arr, l, m, r):
    len1, len2 = m - l + 1, r - m
    left, right = [], []
    for i in range(0, len1):
        left.append(arr[l + i])
    for i in range(0, len2):
        right.append(arr[m + 1 + i])

    i, j,

原文地址：https://blog.csdn.net/weixin_43631425/article/details/144028028

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！