【C++实现递归算法、归并排序和堆排序】

我就是我 2024-03-16 17:32 49阅读 0赞

## 一、递归算法 ##

当我们需要反复地执行某个算法时，使用递归算法可以是一个不错的选择。在这个算法中，**函数会调用自身，直到达到某个特定条件而停止递归**。C++语言中支持递归，下面就来详细介绍一下如何使用C++实现递归算法。

在本教程中，我们将以求斐波那契数列为例子来介绍递归算法的实现。

> 斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：*F*(0)=1，*F*(1)=1, *F*(n)=*F*(n - 1)+*F*(n - 2)（*n* ≥ 2，*n* ∈ N\*）

### 1、定义函数 ###

首先，我们需要定义一个函数，用于计算斐波那契数列的第n项。考虑到斐波那契数列的第0项和第1项是已知的，我们可以将函数分为两种情况：当n为0或1时，我们直接返回n的值；否则我们返回斐波那契数列中n-1项和n-2项的和。代码如下：

int fibonacci(int n) {
        
        if (n == 0 || n == 1) {
        
            return n;
        }
        else {
        
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }

### 2、测试函数 ###

我们可以将这个函数用于测试，计算斐波那契数列的前几项。比如，我们可以使用下面的代码来计算斐波那契数列的前10项：

int main() {
        
        for (int i = 0; i < 10; i++) {
        
            cout << fibonacci(i) << " ";
        }
        return 0;
    }

### 3、分析递归算法 ###

在本例中，递归算法可以用来计算斐波那契数列的第n项，其递归式为：

**F(n) = F(n-1) + F(n-2)**

其中，F(n)表示斐波那契数列的第n项。当n=0或1时，我们直接返回n本身。

需要注意的是，递归算法中需要设置终止递归的条件。在本例中，我们设定当n=0或1时，递归会终止。如果未设置终止递归的条件或者终止条件设置不正确，递归会一直无限地执行下去，导致栈溢出等问题。

### 4、总结 ###

本教程介绍了使用C++实现递归算法的基本步骤，以求斐波那契数列为例子。从定义函数，测试函数到分析递归算法，这个教程希望能帮助您更好地理解递归算法的概念并掌握其实现方法。

完整代码如下：

#include<iostream>
    using namespace std;
    int fibonacci(int n);
    int main()
    {
        
    	for (int i = 0; i < 10; i++) {
        
            cout << fibonacci(i) << " ";
        }
        return 0;
    
    }
    
    int fibonacci(int n) {
        
        if (n == 0 || n == 1) {
        
            return n;
        }
        else {
        
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }

## 二、归并排序 ##

归并排序（Merge Sort）是一种分治算法，其基本思想是**将一个大的数组递归地拆分成两个小的数组，直到不能继续分为止，然后将这些小数组两两合并，不断合并直到原数组完全排序**。归并排序具有稳定性，时间复杂度稳定在O(nlogn)，空间复杂度为O(n)。

下面按照步骤来介绍归并排序的详细实现。

### 1、分解（Divide） ###

首先将待排序的数组递归地划分成两个子数组，直到每个子数组都只有一个元素为止。这意味着数组已被分解为n个长度为1的子数组。

### 2、合并（Merge） ###

将子数组两两合并，得到n/2个已排序的子数组，然后将这些已排序的子数组再次合并，直到最终只剩下一个长度为n的已排序数组为止。合并两个已排序的子数组的步骤为：

（1）创建一个空数组存放合并后的元素。

（2）同时遍历两个已排序数组，比较它们的首位元素，将较小的元素添加到新数组中。

（3）重复以上步骤，直到其中一个数组中所有元素都放入新数组中。

（4）将另一个数组中所有元素直接添加到新数组的末尾。

（5）返回新数组。

### 3、归并排序的代码实现 ###

下面是归并排序的代码实现：

void merge(int nums[], int left, int mid, int right) {
        
        /*将原数组分成两个部分，左半部分为[nums[left], nums[mid]]，
        右半部分为[nums[mid + 1], nums[right]]*/
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int L[n1], R[n2];
        for (int i = 0; i < n1; i++) {
        
            L[i] = nums[left + i];
        }
        for (int i = 0; i < n2; i++) {
        
            R[i] = nums[mid + 1 + i];
        }
        // 将两个数组合并为一个升序数组
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
        
            if (L[i] <= R[j]) {
        
                nums[k++] = L[i++];
            }
            else {
        
                nums[k++] = R[j++];
            }
        }
        while (i < n1) {
        
            nums[k++] = L[i++];
        }
        while (j < n2) {
        
            nums[k++] = R[j++];
        }
    }
    
    void mergeSort(int nums[], int left, int right) {
        
        if (left < right) {
        
            int mid = left + (right - left) / 2;
            mergeSort(nums, left, mid);
            mergeSort(nums, mid + 1, right);
            merge(nums, left, mid, right);
        }
    }

### 4、测试代码 ###

下面是一个测试代码：

int main() {
        
        int nums[] = {
        2, 5, 1, 6, 3, 8, 4, 7};
        int len=sizeof(nums)/sizeof(nums[0]);
        cout<<"排序前：";
    	for (int i=0;i<len;i++) {
        
            cout << nums[i] << " ";
        } 
    	mergeSort(nums, 0, len - 1);
        cout<<"\n排序后："; 
    	for (int i=0;i<len;i++) {
        
            cout << nums[i] << " ";
        }
        return 0;
    }

在上述代码中，我们从测试数据\{2, 5, 1, 6, 3, 8, 4, 7\}中，通过归并排序得到的排序数据为\{1, 2, 3, 4, 5, 6, 7, 8\}。

### 5、总结 ###

归并排序是一种高效的排序算法，它递归地将数组分为两半，然后将两半的数组合并成一个有序的数组。可以在大规模数据下高效地实现排序。需要注意的是，归并排序的实现过程涉及到很多指针与循环，实现时需要多加小心，避免越界等问题。

### 6、完整代码 ###

#include<iostream>
    using namespace std;
    
    void merge(int nums[], int left, int mid, int right) {
        
        /*将原数组分成两个部分，左半部分为[nums[left], nums[mid]]，
        右半部分为[nums[mid + 1], nums[right]]*/
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int L[n1], R[n2];
        for (int i = 0; i < n1; i++) {
        
            L[i] = nums[left + i];
        }
        for (int i = 0; i < n2; i++) {
        
            R[i] = nums[mid + 1 + i];
        }
        // 将两个数组合并为一个升序数组
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
        
            if (L[i] <= R[j]) {
        
                nums[k++] = L[i++];
            }
            else {
        
                nums[k++] = R[j++];
            }
        }
        while (i < n1) {
        
            nums[k++] = L[i++];
        }
        while (j < n2) {
        
            nums[k++] = R[j++];
        }
    }
    
    void mergeSort(int nums[], int left, int right) {
        
        if (left < right) {
        
            int mid = left + (right - left) / 2;
            mergeSort(nums, left, mid);
            mergeSort(nums, mid + 1, right);
            merge(nums, left, mid, right);
        }
    }
    int main() {
        
        int nums[] = {
        2, 5, 1, 6, 3, 8, 4, 7};
        int len=sizeof(nums)/sizeof(nums[0]);
        cout<<"排序前：";
    	for (int i=0;i<len;i++) {
        
            cout << nums[i] << " ";
        } 
    	mergeSort(nums, 0, len - 1);
        cout<<"\n排序后："; 
    	for (int i=0;i<len;i++) {
        
            cout << nums[i] << " ";
        }
        return 0;
    }

## 三、堆排序 ##

堆排序是一种基于二叉堆的排序算法，它的时间复杂度为O(nlogn)，在实际应用中得到广泛应用。**堆排序的基本思想是将待排序的序列构建成一个二叉堆，然后依次取出堆顶元素，直到堆为空**。

### 1、堆的定义 ###

堆是一种完全二叉树，它分为两种类型：最大堆和最小堆。

最大堆：每个节点的值都大于或等于它的左右子节点的值。

最小堆：每个节点的值都小于或等于它的左右子节点的值。

### 2、堆排序的基本思想 ###

堆排序的基本思想是将待排序的序列构建成一个二叉堆，然后依次取出堆顶元素，直到堆为空。具体流程如下：

（1）将待排序序列构建成一个最大堆。

（2）将堆顶元素与堆底元素交换，然后去掉堆底元素，再将剩余元素重新构建成一个最大堆。

（3）重复步骤（2）直到堆为空。

### 3、堆排序的实现 ###

#### （1）构建最大堆 ####

构建最大堆的过程可以采用自下而上的方式，从最后一个非叶子节点开始，依次将每个节点调整到它所在的子树成为最大堆。具体实现如下：

void AdjustHeap(int arr[], int i, int n)
    {
        
        int temp = arr[i];
        int j = 2 * i + 1;
        while (j < n)
        {
        
            if (j + 1 < n && arr[j + 1] > arr[j])
            {
        
                j++;
            }
            if (arr[j] > temp)
            {
        
                arr[i] = arr[j];
                i = j;
                j = 2 * i + 1;
            }
            else
            {
        
                break;
            }
        }
        arr[i] = temp;
    }
    
    void buildMaxHeap(int arr[], int n)
    {
        
        for (int i = n / 2 - 1; i >= 0; i--)
        {
        
            AdjustHeap(arr, i, n);
        }
    }

#### （2）堆排序 ####

堆排序的实现过程如下：

void heapSort(int arr[], int n)
    {
        
        buildMaxHeap(arr, n);
        for (int i = n - 1; i > 0; i--)
        {
        
            swap(arr[0], arr[i]);
            AdjustHeap(arr, 0, i);
        }
    }

### 4、堆排序的优化 ###

#### （1）优化建堆过程 ####

在建堆过程中，对于一个节点i，它的左右子节点分别为2i+1和2i+2，如果左右子节点中的较大值比i节点的值大，那么就需要将较大值与i节点交换，然后继续向下调整。这个过程可以用一个循环来实现，避免了递归调用，提高了效率。

void AdjustHeap(int arr[], int i, int n)
    {
        
        int temp = arr[i];
        for (int j = 2 * i + 1; j < n; j = 2 * j + 1)
        {
        
            if (j + 1 < n && arr[j + 1] > arr[j])
            {
        
                j++;
            }
            if (arr[j] > temp)
            {
        
                arr[i] = arr[j];
                i = j;
            }
            else
            {
        
                break;
            }
        }
        arr[i] = temp;
    }

#### （2）优化排序过程 ####

在排序过程中，每次将堆顶元素与堆底元素交换后，堆的大小减1，然后需要重新调整堆。但是，由于堆底元素已经被交换到堆顶，而堆底元素上方的部分仍然是一个最大堆，因此可以直接对堆顶元素进行调整，而不需要重新构建整个堆，这样可以减少一些不必要的操作。

### 5、堆排序的稳定性 ###

堆排序是一种不稳定的排序算法，因为在调整堆的过程中，可能会交换相同元素的位置。例如，对于序列\{5, 2, 5, 1, 6, 2\}，经过堆排序后，可能会变成\{1, 2, 2, 5, 5, 6\}，其中两个2的相对位置发生了改变。

### 6、完整代码 ###

#include<iostream>
    using namespace std;
    //构建最大堆 
    void AdjustHeap(int arr[], int i, int n)
    {
        
        int temp = arr[i];
        for (int j = 2 * i + 1; j < n; j = 2 * j + 1)
        {
        
            if (j + 1 < n && arr[j + 1] > arr[j])
            {
        
                j++;
            }
            if (arr[j] > temp)
            {
        
                arr[i] = arr[j];
                i = j;
            }
            else
            {
        
                break;
            }
        }
        arr[i] = temp;
    }
    
    void buildMaxHeap(int arr[], int n)
    {
        
        for (int i = n / 2 - 1; i >= 0; i--)
        {
        
            AdjustHeap(arr, i, n);
        }
    }
    //堆排序 
    void heapSort(int arr[], int n)
    {
        
        buildMaxHeap(arr, n);
        for (int i = n - 1; i > 0; i--)
        {
        
            swap(arr[0], arr[i]);
            AdjustHeap(arr, 0, i);
        }
    }
    
    int main()
    {
        
    	int arr[]={
        4,6,3,7,2,9};
    	int len=sizeof(arr)/sizeof(arr[0]);
    	cout<<"原数组："; 
    	for(int i=0;i<len;i++){
        
    		cout<<arr[i]<<" ";
    	}	
    	heapSort(arr,len);
    	cout<<endl;
    	cout<<"排序后：";
    	for(int i=0;i<len;i++){
        
    		cout<<arr[i]<<" ";
    	}
     }