c++归并排序算法图解

好的，下面是 c++ 归并排序算法的图解：


归并排序是一种分治思想的排序算法，它将待排序的序列分成两个子序列，对每个子序列进行递归排序，然后将两个已排序的子序列合并成一个有序的序列。具体实现时，可以使用递归或迭代的方式。

相关问题

c++实现归并排序算法

归并排序是一种经典的排序算法，它的实现可以使用C语言。具体步骤如下：

1. 定义一个递归函数mergeSort，用于对待排序的数组进行划分和合并操作。
2. 在mergeSort函数中，判断数组的长度是否大于1，如果不大于1，则直接返回。
3. 如果数组长度大于1，将数组划分为两个子数组，分别递归调用mergeSort函数对这两个子数组进行排序。
4. 接下来，定义一个merge函数，用于将两个已经排序好的子数组合并成一个有序数组。
5. 在merge函数中，使用两个指针分别指向两个子数组的开头，并比较指针所指的元素大小。
6. 将较小的元素放入临时数组中，并将对应的指针向后移动一位。
7. 重复上述步骤，直到其中一个子数组的元素全部放入临时数组中。
8. 将剩余的子数组中的元素依次放入临时数组中。
9. 最后，将临时数组中的元素复制回原数组。

以下是C语言实现归并排序算法的代码：

#include <stdio.h>

void merge(int arr[], int left[], int leftSize, int right[], int rightSize) {
    int i = 0, j = 0, k = 0;
    
    while (i < leftSize && j < rightSize) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }
    
    while (i < leftSize) {
        arr[k++] = left[i++];
    }
    
    while (j < rightSize) {
        arr[k++] = right[j++];
    }
}

void mergeSort(int arr[], int size) {
    if (size <= 1) {
        return;
    }
    
    int mid = size / 2;
    int left[mid];
    int right[size - mid];
    
    for (int i = 0; i < mid; i++) {
        left[i] = arr[i];
    }
    
    for (int i = mid; i < size; i++) {
        right[i - mid] = arr[i];
    }
    
    mergeSort(left, mid);
    mergeSort(right, size - mid);    merge(arr, left, mid, right, size - mid);
}

int main() {
    int arr[] = {5, 2, 8, 1, 9, 4, 6, 3, 7};
    int size = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, size);

    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

这段代码可以将数组 {5, 2, 8, 1, 9, 4, 6, 3, 7} 进行归并排序，最终输出排序后的结果。

C++实现归并排序算法代码

当然，我可以为您提供C++实现的归并排序算法代码。以下是一个示例：

#include <iostream>
using namespace std;

// 合并两个子数组
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;    // 左子数组的大小
    int n2 = right - mid;       // 右子数组的大小

    // 创建临时数组
    int L[n1], R[n2];

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

    // 归并临时数组到原始数组
    int i = 0;  // 左子数组的索引
    int j = 0;  // 右子数组的索引
    int k = left;   // 合并后的数组的索引

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

    // 将剩余元素复制到原始数组（如果有）
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// 归并排序函数
void mergeSort(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);
    }
}

// 打印数组元素
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = { 12, 11, 13, 5, 6, 7 };
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "原始数组：";
    printArray(arr, size);

    mergeSort(arr, 0, size - 1);

    cout << "排序后的数组：";
    printArray(arr, size);

    return 0;
}

这段代码实现了归并排序算法。您可以将要排序的数组存储在`arr`中，并调用`mergeSort`函数对其进行排序。最后，使用`printArray`函数打印排序后的数组。希望这可以帮助到您！