c++实现二路归并排序的示例代码

C++实现二路归并排序是一种常用的排序算法,本文将介绍该算法的详细实现过程,并提供一些示例说明。

一、简述二路归并排序的原理

二路归并排序是一种基于分治思想的排序算法。核心思想是把一个待排序的序列,不断地拆分为两个子序列,直至每个子序列只剩下一个元素,然后利用递归思想将这些子序列不断地两两合并,最终得到一个有序的序列。

二、C++实现二路归并排序的示例代码

代码如下:

#include <iostream>

using namespace std;

void merge(int arr[], int l, int m, int r)
{
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for(int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for(int i = 0; i < n2; i++)
        R[i] = arr[m + 1 + i];

    int i = 0, j = 0, k = l;
    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 l, int r)
{
    if(l < r)
    {
        int m = l + (r - l) / 2;

        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}

void printArray(int arr[], int size)
{
    for(int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main()
{
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, size);

    mergeSort(arr, 0, size - 1);

    cout << "Sorted array: ";
    printArray(arr, size);

    return 0;
}

三、示例说明

示例一

输入: {38, 27, 43, 3, 9, 82, 10}

输出: {3, 9, 10, 27, 38, 43, 82}

解释:将元素依次分割为: {38, 27, 43, 3}, {9, 82, 10},继续分割为 {38, 27}, {43, 3}, {9, 82}, {10},分割完成后,开始将元素进行排序合并。第一次合并为 {27, 38}, {3, 43}, {9, 82}, {10},第二次合并为 {3, 27, 38, 43}, {9, 10, 82},最后一次合并为 {3, 9, 10, 27, 38, 43, 82},得到了一个有序的数组。

示例二

输入: {7, 5, 9, 3, 1, 4, 6, 8, 2}

输出: {1, 2, 3, 4, 5, 6, 7, 8, 9}

解释:将元素依次分割为: {7, 5, 9, 3, 1}, {4, 6, 8, 2},继续分割为 {7, 5}, {9, 3, 1}, {4, 6}, {8, 2},分割完成后,开始将元素进行排序合并。第一次合并为 {5, 7}, {1, 3, 9}, {4, 6}, {2, 8},第二次合并为 {1, 3, 5, 7, 9}, {2, 4, 6, 8},最后一次合并为 {1, 2, 3, 4, 5, 6, 7, 8, 9},得到了一个有序的数组。

综上所述,通过归并排序,可以将一个无序的数组转换为一个有序的数组,其时间复杂度为O(nlogn)。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:c++实现二路归并排序的示例代码 - Python技术站

(0)
上一篇 2023年5月19日
下一篇 2023年5月19日

相关文章

  • PHP抽奖算法程序代码分享

    关于“PHP抽奖算法程序代码分享”的完整攻略,我将会从以下方面进行讲解: 什么是抽奖算法? 如何设计抽奖算法? 实现代码分享及示例说明 什么是抽奖算法? 抽奖算法是指通过一定的算法,实现在一些参与者中选出一个或几个”幸运儿”的过程。 如何设计抽奖算法? 抽奖算法设计的主要目的就是为了确保公平,同时符合某些要求。在比较公平的情况下,抽奖过程也应该是越来越具备娱…

    算法与数据结构 2023年5月19日
    00
  • C++排序算法之插入排序

    C++排序算法之插入排序 插入排序是一种简单且直观的排序算法,在实现上也比较容易。它的基本思路是把一个待排序的序列分成两个部分:已排序部分和未排序部分,然后从未排序部分取出一个元素插入到已排序部分的合适位置,作为新的已排序部分。 算法过程 插入排序的过程可以用以下步骤概括: 将序列的第一个元素看成已排序部分,其他元素看成未排序部分 从未排序部分选择一个元素,…

    算法与数据结构 2023年5月19日
    00
  • Flutter Dart快速排序算法示例详解

    Flutter Dart快速排序算法示例详解 介绍 快速排序是一种排序算法,其基本思想是选择一个基准元素,将数组分成两个子数组,其中一个子数组的元素都比基准元素小,另一个子数组的元素都比基准元素大。然后递归地对两个子数组进行快速排序。 实现步骤 选择一个基准元素,并将其从数组中移除。 遍历数组,将小于基准元素的元素放入一个新的左侧数组中,大于基准元素的元素放…

    算法与数据结构 2023年5月19日
    00
  • php排序算法(冒泡排序,快速排序)

    PHP排序算法是常见的编程问题,其中冒泡排序和快速排序是两种常见的算法。下面我会详细讲解这两种算法的原理和实现方法。 冒泡排序 冒泡排序是一种基本的排序算法,其原理是反复遍历要排序的元素,比较相邻元素的大小,若顺序不对则交换位置,一直重复该过程直到所有元素都按照升序排好。 冒泡排序的实现过程可以分为两个步骤: 外层循环控制排序的趟数,循环次数为 $n-1$ …

    算法与数据结构 2023年5月19日
    00
  • 分布式架构Redis中有哪些数据结构及底层实现原理

    分布式架构Redis中有哪些数据结构及底层实现原理 Redis支持的数据结构包括:字符串(String)、哈希表(Hash)、列表(List)、集合(Set)和有序集合(Sorted Set)。 字符串(String) 字符串是Redis最基础的数据类型,与Java中的String类似,适用于存储任意二进制数据,可以存储字符串、数字、二进制数据等类型的数据。…

    算法与数据结构 2023年5月19日
    00
  • 冒泡排序算法及Ruby版的简单实现

    冒泡排序是一种比较简单的排序算法,其基本思想是重复地遍历数列,每次比较相邻的两个元素,如果前一个元素比后一个元素大,则交换这两个元素的位置,直到遍历完整个数列,这样一次遍历后,数列中最大的元素就被排到了最后面。重复执行此过程,直到整个数列有序为止。 以下是冒泡排序算法的Ruby版简单实现: def bubble_sort(array) n = array.l…

    算法与数据结构 2023年5月19日
    00
  • C++ 基本算法 冒泡法、交换法、选择法、实现代码集合

    C++ 基本算法 冒泡法、交换法、选择法 在编程中,基本算法是非常重要的。本文将介绍C++中基本算法的三种实现方式:冒泡排序、交换排序、选择排序,并附上相应的实现代码集合以及示例说明。 冒泡排序 冒泡排序,顾名思义,就像水中的气泡一样,从底部慢慢上升。在排序过程中,每次比较相邻两个元素的大小,如果发现顺序不对,就进行交换,直到所有元素都排列好。冒泡排序的时间…

    算法与数据结构 2023年5月19日
    00
  • JS/HTML5游戏常用算法之路径搜索算法 A*寻路算法完整实例

    非常感谢你对于本站文章的关注。下面是针对文章“JS/HTML5游戏常用算法之路径搜索算法 A*寻路算法完整实例”的完整攻略解析。 1. 介绍 本文主要讲解的是一种常用于解决路径搜索问题的算法—— A*寻路算法。使用该算法可以在搜索空间(如地图、游戏场景等)中找到一条最优路径,可应用于许多领域,如自动驾驶、游戏AI等。 2. 算法流程 该算法通过在搜索空间中创…

    算法与数据结构 2023年5月19日
    00
合作推广
合作推广
分享本页
返回顶部