![0

🌈欢迎来到算法专栏
🙋🏾‍♀️作者介绍：前PLA队员 目前是一名普通本科大三的软件工程专业学生
🌏IP坐标：湖北武汉
🍉 目前技术栈：C/C++、Linux系统编程、计算机网络、数据结构、Mysql、Python（目前在学）
🍇 博客介绍：通过分享学习过程，加深知识点的掌握，也希望通过平台能认识更多同僚，如果觉得文章有帮助，请您动动发财手点点赞，本人水平有限，有不足之处欢迎大家扶正~
🍓 最后送大家一句话共勉：知不足而奋进，望远山而前行。愿大家都能早日进大厂实现财富自由~
————————————————

1.斐波那契数列的递归算法实现

1.1问题描述

斐波那契数列是一个经典的递归问题，其定义如下：
当 n = 0 时，F（0） = 0
当 n = 1 时，F（1） = 1
当 n > 1 时，F（n） = F（n-1） + F（n-2）

1.2算法分析

递归实现的思路就是将问题分解为更小的子问题，直到达到基本情况（递归终止条件），然后逐级返回结果。在斐波那契数列中，递归的思路是利用函数调用来计算前两个数的和。

1.3代码实现

#include <iostream>
#include <vector>

void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // 创建临时数组
    std::vector<int> leftArr(n1);
    std::vector<int> rightArr(n2);

    // 将数据复制到临时数组 leftArr 和 rightArr
    for (int i = 0; i < n1; i++) {
        leftArr[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        rightArr[j] = arr[mid + 1 + j];
    }

    // 归并临时数组到 arr[left..right]
    int i = 0; // 初始化左子数组的索引
    int j = 0; // 初始化右子数组的索引
    int k = left; // 初始化合并数组的索引

    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        }
        else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    /*i、、jk 分别是用于迭代遍历左子数组、右子数组和合并后的数组的索引。
n1 和  分别是左右两个子数组的长度。n2
循环的条件 i < n1 && j < n2 确保只在左右两个子数组都有元素可供比较的情况下执行。
在循环内部，通过比较 leftArr[i] 和 rightArr[j] 的大小，将较小的元素复制到 arr 中，并相应地更新索引。
如果 leftArr[i] 小于等于 rightArr[j]，则将 leftArr[i] 复制到 arr[k]，并增加 i 的值。
如果 rightArr[j] 小于 leftArr[i]，则将 rightArr[j] 复制到 arr[k]，并增加 j 的值。
无论是哪种情况，都会增加 k 的值，将合并后的数组的索引向前移动。
这个过程重复进行，直到其中一个子数组的所有元素都被合并到 arr 中。
然后，如果左子数组或右子数组中还有元素未合并，将其余元素依次复制到 arr 中。
最终，整个过程确保 arr 成为一个有序的合并数组。





*/

    // 将剩余的元素复制到 arr
    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        // 寻找中间点
        int mid = left + (right - left) / 2;

        // 递归排序左半部分和右半部分
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 合并两个已排序的子数组
        merge(arr, left, mid, right);
    }
}
//
//int main() {
//    std::vector<int> arr = { 12, 11, 13, 5, 6, 7 };
//
//    std::cout << "Original array: ";
//    for (int num : arr) {
//        std::cout << num << " ";
//    }
//    std::cout << std::endl;
//
//    // 调用归并排序
//    mergeSort(arr, 0, arr.size() - 1);
//
//    std::cout << "Sorted array: ";
//    for (int num : arr) {
//        std::cout << num << " ";
//    }
//    std::cout << std::endl;
//
//    return 0;
//}

1.4结果分析

运行结果：
Enter the value of n: 6
F(6) = 8。
分析：
递归实现可能会在计算过程中重复计算相同的子问题，导致效率较低。为了提高效率，可以考虑使用动态规划或者迭代的方式实现斐波那契数列。

2.插入排序问题的递归算法实现

2.1、问题描述

插入排序的递归算法思路是将一个元素插入到已经排好序的数组中，递归地重复这个过程。

2.2、算法分析

插入排序的递归算法的逻辑主要涉及两个部分：递归排序和插入操作。
2.1.递归
递归的终止条件是数组长度小于等于1，因为一个元素的数组已经是排好序的。
在递归调用中，将前 n-1 个元素进行排序，确保它们是按照递增顺序排列的。
2.2.插入操作部
当递归返回时，我们考虑最后一个元素（第 n 个元素），并将其插入到前 n-1 个已经排好序的元素中。
我们将最后一个元素的值存储在变量key中。
使用一个循环找到正确的插入位置，并将比 'key
最终，在正确的位置插入key，使得前 n 个元素仍然是排好序的。
通过递归地应用这个过程，最终整个数组被排序。算法的时间复杂度为 O（n^2），其中 n 是数组的长度。这是因为每个元素都需要与之前的元素进行比较，并进行插入操作

2.3代码实现

#include <iostream>
#include <vector>

void insertRecursive(std::vector<int>& arr, int n) {
    // 递归终止条件
    if (n <= 1) {
        return;
    }

    // 递归调用，将前 n-1 个元素插入排序
    insertRecursive(arr, n - 1);

    // 将最后一个元素插入到已排好序的部分
    int key = arr[n - 1];
    int j = n - 2;

    // 移动比 key 大的元素向后
    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
    }

    // 插入 key 到正确的位置
    arr[j + 1] = key;
}

//int main() {
//    std::vector<int> arr = { 12, 11, 13, 5, 6 };
//
//    std::cout << "Original array: ";
//    for (int num : arr) {
//        std::cout << num << " ";
//    }
//    std::cout << std::endl;
//
//    // 调用插入排序的递归函数
//    insertRecursive(arr, arr.size());
//    std::cout << "Sorted array: ";
//    for (int num : arr) {
//        std::cout << num << " ";
//    }
//    std::cout << std::endl;
//
//    return 0;
//}

2.4结果分析

结果：
Original array: 12 11 13 5 6
Sorted array: 5 6 11 12 13
分析：
插入排序在实践中对小规模数组和部分有序的数组是有效的，但对于大规模乱序数组来说，更高效的排序算法（例如快速排序、归并排序）通常更具优势。

3.归并排序的分治算法实现

3.1、问题描述

归并排序是一种分治算法，其基本思想是将一个大问题分解成两个较小的子问题，然后递归地解决这两个子问题，最后将它们的解合并起来。

3.2、算法分析

归并排序是一种经典的分治算法，其实现逻辑可以分为三个主要步骤：分解、解决、合并。

1. 分解（Divide）： - 将待排序的数组分解成两个子数组，这是递归的基本情况。 - 寻找数组的中间点，即 mid = left + (right - left) / 2。 - 递归地对左半部分（left 到 mid）和右半部分（mid + 1 到 right）进行分解。
2. 解决（Conquer）： - 递归地对左半部分和右半部分进行排序。
3. 合并（Combine）： - 合并两个已排序的子数组，以产生一个新的有序数组。 - merge 函数用于合并，它比较两个子数组的元素，并将它们按照顺序合并到一个临时数组中。 - 将合并后的结果复制回原始数组的相应位置。 整个过程递归地重复执行分解、解决、合并的步骤，直到基本情况下，即子数组长度为1。在这个基本情况下，每个子数组都被视为已经排好序，然后通过合并操作合并为更大的有序数组。 下面是每个步骤的关键实现点：

• 分解： 递归划分数组为左右两半。
• 解决： 递归对左右两半进行排序。
• 合并： 合并两个有序数组。 整个过程保证了每次合并都是在有序的基础上进行，最终得到整个数组的有序排列。算法的时间复杂度为 O(n log n)，其中 n 是数组的长度。

3.3代码实现

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

int fibonacci(int n) {
    // 递归终止条件
    if (n == 0) {
        return 0;
    }
    else if (n == 1) {
        return 1;
    }

    // 递归调用，将问题分解为子问题
    return fibonacci(n - 1) + fibonacci(n - 2);
}

//int main() {
//    int n;
//    std::cout << "Enter the value of n: ";
//    std::cin >> n;
//
//    // 输出斐波那契数列的第 n 项
//    std::cout << "F(" << n << ") = " << fibonacci(n) << std::endl;
//
//    return 0;
//}

3.4结果分析

Original array: 12 11 13 5 6 7
Sorted array: 5 6 7 11 12 13

分析：

归并排序具有一些重要的优点，这些优点使得它在某些场景下成为一种非常有效的排序算法： 1. 稳定性： 归并排序是一种稳定的排序算法，即对于相等的元素，排序前后它们的相对顺序保持不变。这对某些应用是很重要的，例如在对具有相同排序键的记录进行多次排序时。 2. 适用于链表： 归并排序天然适用于链表数据结构，不需要额外的空间来存储中间结果。相比之下，其他一些排序算法，比如快速排序，对链表的性能可能不如对数组的性能。 3. 稳定的时间复杂度： 归并排序在最坏、平均和最好情况下的时间复杂度都是 O(n log n)，这使得它在大多数情况下都表现得相当稳定，不受输入数据的影响。 4. 可并行化： 归并排序是一种天然可以并行化的排序算法。由于其分治的性质，可以轻松地将数据划分为多个部分，分别进行排序，然后合并结果。这使得归并排序在多核和分布式系统中有良好的性能表现。 5. 不依赖于初始状态： 归并排序对于输入数据的初始状态不敏感，它总是以相同的时间复杂度运行。这与某些其他排序算法，比如快速排序，有着不同的特点。 尽管归并排序具有这些优点，但它也有一些缺点，主要是它需要额外的存储空间（与输入数据大小成正比）。这使得在内存有限的情况下，归并排序的应用可能受到限制。但总体来说，归并排序是一种非常稳定且通用的排序算法

4.快速排序问题的分治算法实现

4.1、问题描述

快速排序是一种高效的分治排序算法，其核心思想是选择一个基准元素，将数组分成两部分，使得左边的元素都小于等于基准元素，右边的元素都大于等于基准元素，然后对左右两部分分别递归地应用相同的过程。

4.2、算法分析

1. 选择一个基准元素并通过 partition 将数组分为两部分。
2. 对分割出的两个子数组递归地应用相同的过程，直到每个子数组的大小为1。
3. 最终，整个数组就被排序好了，因为每个元素都参与了比较和交换的过程。
   整个过程是递归的，每次递归都会确定一个元素的最终位置，最终所有元素都被放置在正确的位置上，实现了整个数组的排序。算法的时间复杂度平均为 O(n log n)，其中 n 是数组的长度。

4.3 代码实现

#include <iostream>
#include <vector>

int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 选择数组最后一个元素作为基准
    int i = low - 1; // 初始化较小元素的索引

    for (int j = low; j < high; j++) {
        // 如果当前元素小于等于基准，将其与较小元素交换
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }

    // 将基准元素放到正确的位置
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        // 找到基准元素的位置，使得左边元素都小于等于基准，右边元素都大于等于基准
        int pivotIndex = partition(arr, low, high);

        // 递归对基准元素左右两部分进行排序
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

//int main() {
//    std::vector<int> arr = { 12, 11, 13, 5, 6, 7 };
//
//    std::cout << "Original array: ";
//    for (int num : arr) {
//        std::cout << num << " ";
//    }
//    std::cout << std::endl;
//
//    // 调用快速排序
//    quickSort(arr, 0, arr.size() - 1);
//
//    std::cout << "Sorted array: ";
//    for (int num : arr) {
//        std::cout << num << " ";
//    }
//    std::cout << std::endl;
//
//    return 0;
//}

4.4结果分析

结果：
Original array: 12 11 13 5 6 7
Sorted array: 5 6 7 11 12 13
分析：
快速排序是一种高效的排序算法，具有以下一些优点： 1. 平均时间复杂度为 O(n log n)： 在平均情况下，快速排序的时间复杂度是 O(n log n)，这使得它在处理大规模数据时表现出色。 2. 原地排序： 快速排序是一种原地排序算法，不需要额外的辅助数组或存储空间。它通过在原始数组上进行交换和重排来实现排序，节省了内存空间。 3. 高效性： 在实际应用中，快速排序通常比其他 O(n log n) 复杂度的算法表现更好，因为它的常数因子较小。这在处理大规模数据时是一个重要的优势。 4. 稳定性： 由于是原地排序，相同元素的相对位置不会改变，因此快速排序是一种稳定的排序算法。 5. 适应性： 对于部分有序的数据，快速排序的表现也相当好。在这样的情况下，分割操作的代价相对较小，递归深度相对较小，