常用算法¶

搜索算法
线性搜索 Linear search
二分搜索 Binary search
排序算法
冒泡 Bubble sort
并排 Merge sort
插排 Insertion sort
快排 Quick sort
选排 Selection sort
堆排 Heap sort

一、搜索算法 Search¶

二、排序算法 Sort¶

测试数据：[64,34,25,12,22,23,90]

冒泡排序¶

1.简介

冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，比较相邻两个元素的大小，如果顺序不对就交换这两个元素，直到整个数列排序完成。

冒泡排序的基本思想是每次比较相邻两个元素的大小，如果前一个元素比后一个元素大，则交换这两个元素的位置，经过一轮的比较和交换后，最大的元素就会排到数列的最后面。接着对剩下的元素重复进行这个过程，直到整个数列排序完成。

2.复杂度

冒泡排序的时间复杂度为O(n²)，其中n为要排序的元素个数。它的空间复杂度为O(1)，是一种稳定的排序算法。虽然冒泡排序不如其他高级排序算法效率高，但它实现简单，适用于数据量较小的排序问题。

3.代码实现

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

归并排序¶

1.简介

归并排序是一种基于分治思想的排序算法，它将一个待排序的序列分成两个子序列，分别对这两个子序列进行排序，然后将这两个子序列合并成一个有序的序列。这个过程一直递归下去，直到序列被分解成单个元素为止，单个元素也被认为是有序的。

归并排序的基本思想是先将序列递归地分成两个子序列，然后对这两个子序列分别进行归并排序，最后将两个有序子序列合并成一个有序序列。

2.复杂度

归并排序的时间复杂度为O(nlogn)，其中n为要排序的元素个数。它的空间复杂度为O(n)，因为在排序的过程中需要申请额外的内存空间存放排序结果。归并排序算法是一种稳定的排序算法，适用于各种数据类型的排序问题。

3.代码实现

def merge_sort(arr):
    """归并排序"""

    # 递归终止条件
    if len(arr) <= 1:
        return arr

    # 递归调用
    mid = len(arr) // 2
    left, right = arr[:mid], arr[mid:]
    left_sorted, right_sorted = merge_sort(left), merge_sort(right)

    # 合并列表
    result = _merge(left_sorted, right_sorted)
    return result

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:] or right[j:]
    return merged

插入排序¶

1.简介

插入排序是一种简单直观的排序算法，其基本思想是将一个待排序的序列分成已排序和未排序两部分，然后依次将未排序的元素插入到已排序的序列中，直到所有元素都被插入到已排序序列中为止。具体来说，我们从第二个元素开始，将它与已排序的序列中的元素从后往前逐个比较，如果它小于已排序序列中的某个元素，则将已排序序列中这个元素后移一个位置，直到找到它应该插入的位置为止，然后将它插入到该位置。

2.复杂度

插入排序算法的时间复杂度为O(n^2)，其中n为要排序的元素个数。它的空间复杂度为O(1)，因为在排序的过程中不需要申请额外的内存空间。插入排序算法是一种稳定的排序算法，适用于小规模数据的排序问题。当待排序的序列大部分已经有序时，插入排序算法的效率很高。

3.代码实现

def insertion_sort(arr):
    """插入排序"""

    for i in range(1, len(arr)):

        current = arr[i]

        # 将大的依次后移
        j = i - 1
        while j >= 0 and arr[j] > current:
            arr[j + 1] = arr[j]
            j -= 1

        # 填充当前数
        arr[j + 1] = current

    return arr

快速排序¶

1.简介

快速排序是一种高效的排序算法，它的基本思想是通过选择一个基准元素（pivot），将数组分成两部分，一部分是小于基准元素的，另一部分是大于基准元素的。然后对这两部分分别进行快速排序，最终将整个数组排序完成。

快速排序的具体实现通常采用分治法（Divide and Conquer）：首先选择一个基准元素，然后将数组中小于基准元素的元素放在左边，大于等于基准元素的元素放在右边，接着对左右两个子数组分别递归地进行快速排序，最后将左、基准、右三部分拼接在一起，完成排序。

2.复杂度

快速排序算法的时间复杂度通常为O(nlogn)，其中n为要排序的元素个数。它的空间复杂度为O(logn)到O(n)，具体取决于实现方式。快速排序算法通常比其他排序算法更快，是实际应用中广泛使用的一种排序算法。

3.代码实现

def quick_sort(arr):
    """快速排序"""

    if len(arr) <= 1:
        return arr

    # 拆分
    pivot = arr[0]
    left = [x for x in arr[1:] if x < pivot]
    right = [x for x in arr[1:] if x >= pivot]

    # 递归
    result = quick_sort(left) + [pivot] + quick_sort(right)
    return result

选择排序¶

1.简介

选择排序是一种简单直观的排序算法，其基本思想是在未排序的序列中选择最小（或最大）的元素，然后将其放到已排序序列的末尾。具体来说，我们从第一个元素开始，依次找到未排序序列中最小的元素，并将它与未排序序列的第一个元素交换位置。然后，我们将已排序序列的末尾指针向后移动一个位置，继续在未排序序列中找到最小的元素，并将它与未排序序列的第二个元素交换位置。重复这个过程，直到所有的元素都被排序为止。

2.复杂度

选择排序算法的时间复杂度为O(n^2)，其中n为要排序的元素个数。它的空间复杂度为O(1)，因为在排序的过程中不需要申请额外的内存空间。选择排序算法是一种不稳定的排序算法，因为它可能会改变相等元素的相对顺序。选择排序算法适用于小规模数据的排序问题。当待排序的序列已经比较有序时，选择排序算法的效率反而较低。

3.代码实现

def selection_sort(arr):
    """选择排序"""

    for i in range(len(arr)):
        min_index = i

        # 寻找最小
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j

        # 交换位置
        arr[i], arr[min_index] = arr[min_index], arr[i]

    return arr

堆排序¶

1.简介

堆排序是一种高效的排序算法，它利用了堆的数据结构。堆是一种完全二叉树，其中每个节点的值都大于（或小于）其子节点的值。我们可以使用数组来表示堆，其中根节点存储在位置0上，其余节点依次存储在数组中。根据节点在数组中的位置，我们可以计算出它的父节点和子节点的位置。

堆排序的基本思想是将待排序的序列构建成一个堆，然后依次将堆顶元素（最大元素或最小元素）与未排序的子数组的最后一个元素交换位置。这样，已排序的子数组就增加了一个元素。然后，我们将剩余的元素重新构建成堆，重复这个过程，直到所有的元素都被排序为止。

堆排序算法的实现相对比较复杂，需要实现构建堆、调整堆和交换元素等操作。

2.复杂度

堆排序算法的时间复杂度为O(nlogn)，其中n为要排序的元素个数。它的空间复杂度为O(1)，因为在排序的过程中不需要申请额外的内存空间。

堆排序算法是一种不稳定的排序算法，因为它可能会改变相等元素的相对顺序。堆排序算法适用于大规模数据的排序问题，特别是在需要同时排序多个数据集合时，例如合并多个有序序列。

3.代码实现

def heapify(arr, n, i):
    """
    将数组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)

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[0], arr[i] = arr[i], arr[0]
        # 将剩余的元素重新构建成最大堆
        heapify(arr, i, 0)

    return arr

在这个实现中，我们首先将待排序的数组构建成一个最大堆，然后依次将堆顶元素（最大元素）与未排序的子数组的最后一个元素交换位置。交换后，我们将剩余的元素重新构建成最大堆，重复这个过程，直到所有的元素都被排序为止。