目录

排序算法

冒泡排序

原理

代码实现

选择排序

原理

代码实现

插入排序

原理

实现代码

快速排序

原理

实现代码

归并排序

原理

实现代码

查找算法

线性查找

二分查找

原理

实现代码

插值查找

原理

实现代码

斐波那契查找

原理

实现代码

---

排序算法

冒泡排序

原理

冒泡排序是一种基本的排序算法。其基本思想是通过相邻元素的比较和交换来使较小的元素逐渐“浮”到数组的顶部，而较大的元素则“沉”到数组的底部。具体来说，冒泡排序的算法流程如下：

1. 比较相邻的两个元素。如果第一个比第二个大，就交换它们的位置，否则不交换。
2. 对每一对相邻元素做同样的工作，从开始的第一对到最后的一对，这样一轮下来，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复以上的步骤，直到没有任何一对数字需要比较。

冒泡排序是一种稳定排序算法，因为它不会改变相同元素的相对顺序。但是由于其时间复杂度较高，不适合对大规模数据进行排序。

代码实现

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. 再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。

选择排序是一种不稳定排序算法，因为它可能改变相同元素的相对顺序。但是选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)，比冒泡排序略快，但对于大规模数据的排序仍然不够高效。

代码实现

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

插入排序

原理

插入排序是一种基本的排序算法。其基本思想是将未排序的元素一个一个地插入到已排序的序列中，从而得到一个新的、有序的序列。具体来说，插入排序的算法流程如下：

1. 从第一个元素开始，该元素可以视为已排序部分。
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
3. 如果该元素（已排序）大于新元素，则将该元素移到下一位置。
4. 重复步骤3，直到找到已排序的元素小于或等于新元素的位置。
5. 将新元素插入到该位置后。
6. 重复步骤2~5，直到排序完成。

插入排序是一种稳定排序算法，因为它不会改变相同元素的相对顺序。插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)，比冒泡排序和选择排序稍微快一些，但对于大规模数据的排序仍然不够高效。

实现代码

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        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

快速排序

原理

快速排序是一种基本的排序算法。其基本思想是通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后再分别对这两部分记录继续进行排序，从而达到整个序列有序的目的。具体来说，快速排序的算法流程如下：

1. 从数列中挑出一个元素，称为“基准”（pivot）。
2. 重新排列数列，将所有小于“基准”的元素放在“基准”的左边，所有大于“基准”的元素放在“基准”的右边，相同元素可以放在任意一边。在这个分区结束之后，该“基准”就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursive）把“基准”左边的子序列和右边的子序列重复进行步骤1和2的操作，直到每个子序列中只有一个元素为止。

快速排序是一种不稳定排序算法，因为它可能改变相同元素的相对顺序。快速排序的时间复杂度为O(nlogn)，空间复杂度为O(logn)，在大多数情况下，快速排序是一种高效的排序算法，但在最坏情况下，时间复杂度为O(n^2)，需要特殊处理以避免这种情况。

实现代码

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        left = []
        right = []
        for i in range(1, len(arr)):
            if arr[i] < pivot:
                left.append(arr[i])
            else:
                right.append(arr[i])
        return quick_sort(left) + [pivot] + quick_sort(right)

归并排序

原理

归并排序是一种分治算法，它将待排序的数组分成两个部分，然后对这两个部分分别进行排序，最后将排好序的两个部分合并成一个有序的数组。

具体实现过程如下：

1.将待排序的数组从中间分成两个部分，分别为左半部分和右半部分。

2.对左半部分和右半部分分别进行归并排序，直到每个部分只剩下一个元素为止。

3.将排好序的左半部分和右半部分合并成一个有序的数组。

4.重复步骤2和步骤3，直到整个数组排好序。

归并排序的时间复杂度为O(nlogn)，它是一种稳定的排序算法。

归并排序的空间复杂度为O(n)，其中n为待排序数组的长度。归并排序需要额外的空间来存储归并过程中的中间结果，这些中间结果需要占用与原始数组相同大小的空间。因此，归并排序的空间复杂度为O(n)。

实现代码

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]

        left = merge_sort(left)
        right = merge_sort(right)

        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 += left[i:]
    result += right[j:]
    return result

查找算法

线性查找

def linear_search(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

二分查找

原理

二分查找（Binary Search）是一种基于比较目标值和数组中间元素的查找算法。它的基本思想是：查找过程中，不断缩小查找范围，直到找到目标元素或查找范围为空为止。

具体实现过程如下：

1.将待查找的数组按照元素大小从小到大排序。

2.设定查找范围的左右边界left和right，初始时left为数组第一个元素的下标，right为数组最后一个元素的下标。

3.计算中间元素的下标mid，mid = (left + right) / 2。

4.比较目标元素target和中间元素arr[mid]的大小。

a.如果target等于arr[mid]，则查找成功，返回mid。

b.如果target小于arr[mid]，则在左半部分继续查找，将右边界right设为mid-1。

c.如果target大于arr[mid]，则在右半部分继续查找，将左边界left设为mid+1。

5.重复步骤3和步骤4，直到找到目标元素或查找范围为空为止。

如果目标元素不存在于数组中，最终的查找结果将返回-1。

二分查找的时间复杂度为O(log n)，其中n为待查找数组的长度。

实现代码

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
    return -1

插值查找

原理

插值查找（Interpolation Search）是一种基于二分查找的优化算法，它通过对查找范围的估计，快速定位目标元素的位置。在插值查找中，我们根据目标元素与查找范围的最大值和最小值之间的比例，估算出目标元素在查找范围中的大致位置，然后根据估算结果调整查找范围，最终找到目标元素。

具体实现过程如下：

1.将待查找的数组按照元素大小从小到大排序。

2.设定查找范围的左右边界left和right，初始时left为数组第一个元素的下标，right为数组最后一个元素的下标。

3.计算目标元素在查找范围中的估计位置pos，pos = left + (right - left) * (target - arr[left]) / (arr[right] - arr[left])。

4.比较目标元素target和估计位置pos处的元素arr[pos]的大小。

a.如果target等于arr[pos]，则查找成功，返回pos。

b.如果target小于arr[pos]，则在左半部分继续查找，将右边界right设为pos-1。

c.如果target大于arr[pos]，则在右半部分继续查找，将左边界left设为pos+1。

5.重复步骤3和步骤4，直到找到目标元素或查找范围为空为止。

如果目标元素不存在于数组中，最终的查找结果将返回-1。

插值查找的时间复杂度为O(log log n)~O(log n)，其中n为待查找数组的长度。当数组中元素分布均匀时，插值查找的效率很高，但当元素分布不均时，插值查找的效率可能不如二分查找。

实现代码

def interpolation_search(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high and x >= arr[low] and x <= arr[high]:
        pos = low + ((x - arr[low]) * (high - low)) // (arr[high] - arr[low])
        if arr[pos] == x:
            return pos
        elif arr[pos] < x:
            low = pos + 1
        else:
            high = pos - 1
    return -1

斐波那契查找

原理

斐波那契查找（Fibonacci Search）是一种基于黄金分割原理的查找算法，它利用数列中相邻两个数的比值逼近黄金分割比例，快速定位目标元素的位置。在斐波那契查找中，我们先利用斐波那契数列生成一个递增的下标序列，然后根据这个下标序列来定位目标元素。

具体实现过程如下：

1.将待查找的数组按照元素大小从小到大排序。

2.利用斐波那契数列生成一个递增的下标序列fib，使得fib[k] >= n，其中n为待查找数组的长度。

3.设定查找范围的左右边界left和right，初始时left为数组第一个元素的下标，right为数组最后一个元素的下标。

4.计算斐波那契数列中第k-1个数和第k-2个数的和f，使得f恰好大于等于当前查找范围的长度，即f = fib[k-1] + fib[k-2] >= right - left + 1。

5.根据f将查找范围分成两部分，前半部分长度为fib[k-2]，后半部分长度为fib[k-1]。

6.比较目标元素target和前半部分的最后一个元素arr[left+fib[k-2]-1]的大小。

a.如果target等于arr[left+fib[k-2]-1]，则查找成功，返回left+fib[k-2]-1。

b.如果target小于arr[left+fib[k-2]-1]，则在前半部分继续查找，将右边界right设为left+fib[k-2]-2，同时将k减小1，f减小fib[k-1]。

c.如果target大于arr[left+fib[k-2]-1]，则在后半部分继续查找，将左边界left设为left+fib[k-2]，同时将k减小2，f减小fib[k-2]和fib[k-1]。

7.重复步骤4至步骤6，直到找到目标元素或查找范围为空为止。

如果目标元素不存在于数组中，最终的查找结果将返回-1。

斐波那契查找的时间复杂度为O(log n)，其中n为待查找数组的长度。

实现代码

def fibonacci_search(arr, x):
    n = len(arr)
    fib2 = 0
    fib1 = 1
    fib = fib2 + fib1
    while fib < n:
        fib2 = fib1
        fib1 = fib
        fib = fib2 + fib1
    offset = -1
    while fib > 1:
        i = min(offset+fib2, n-1)
        if arr[i] < x:
            fib = fib1
            fib1 = fib2
            fib2 = fib - fib1
            offset = i
        elif arr[i] > x:
            fib = fib2
            fib1 = fib1 - fib2
            fib2 = fib - fib1
        else:
            return i
    if fib1 and offset < n-1 and arr[offset+1] == x:
        return offset + 1
    return -1