必看！Python 中 5 大排序算法及实现代码的面试刷题指南

在 Python 编程的世界中，排序算法是至关重要的基础知识，也是面试中经常被考察的重点。本文将为您详细介绍 Python 中 5 大排序算法及其实现代码，助您在面试中轻松应对相关问题。

首先是冒泡排序（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]

接下来是插入排序（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

选择排序（Selection Sort）则是每次从未排序部分找出最小的元素，与未排序部分的起始位置元素交换。

其 Python 代码实现为：

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[min_idx] > arr[j]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

快速排序（Quick Sort）是通过选择一个基准元素，将数列分为小于和大于基准的两部分，然后对这两部分分别进行排序。

快速排序的 Python 代码：

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)

def partition(arr, low, high):
    pivot = arr[high]
    i = (low - 1)
    for j in range(low, high):
        if arr[j] <= pivot:
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return (i + 1)

最后是归并排序（Merge Sort），它将数列不断分成两半，对两半分别排序，然后将排序好的两半合并。

归并排序的 Python 代码：

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

熟练掌握这 5 大排序算法及其代码实现，不仅能让您在面试中展现出扎实的编程基础，还能为您解决实际问题提供有效的思路和方法。希望您通过不断的练习和理解，能够灵活运用这些算法，在编程的道路上越走越远！