`

Merge Sort (C++ 实现)

 
阅读更多
// Type your C++ code and click the "Run Code" button!
// Your code output will be shown on the left.
// Click on the "Show input" button to enter input data to be read (from stdin).

#include <iostream>
using namespace std;

void mergeArray(int a[], int beg, int mid, int end, int tmp[]) {
    int i = beg, j = mid+1;
    int m =  mid, n = end;
    int k = 0;
    
    while(i <= m && j <= n) {
        if(a[i] > a[j])
            tmp[k++] = a[j++];
        else
            tmp[k++] = a[i++];
    }
    
    while(i <= m) tmp[k++] = a[i++];
    while(j <= n) tmp[k++] = a[j++];
    
    for(i = 0; i < k; ++i)
        a[beg+i] = tmp[i];
}

void mergeSort(int a[], int beg, int end, int tmp[]) {
    if(beg < end) {
        int mid = (beg + end) / 2;
        mergeSort(a, beg, mid, tmp);
        mergeSort(a, mid+1, end, tmp);
        mergeArray(a, beg, mid, end, tmp);
    }
}

void printArr(int a[], int n) {
    for(int i = 0; i < n; ++i) {
        cout<<a[i]<<" ";
    }
    cout<<endl;
}

int main() {
    int a[] = {1, 5, 9, 4, 6, -3, -7, 9, 19, 8};
    int tmp[10];
    
    printArr(a, 10);
    mergeSort(a, 0, 9, tmp);
    printArr(a, 10);
    
    return 0;
}

 

 

欢迎关注微信公众号——计算机视觉:

 

0
3
分享到:
评论

相关推荐

    merge sort 算法的C++实现

    merge sort 排序 C++ merge sort 算法的C++实现

    c++ 分治法合并排序 merge sort c语言 分治法合并排序 merge sort

    c++ 分治法合并排序 merge sort c语言 分治法合并排序 merge sort(将cout修改printf 加头文件include "stdio.h")

    Merge Sort

    C++实现Merge Sort** 在C++中,我们可以定义一个函数`mergeSort()`,它接受一个整型数组和两个整数作为参数,表示要排序的数组和其范围。这个函数首先检查数组长度,如果长度为1,则返回,因为一个元素的数组已经是...

    数据结构常用算法c++实现

    数据结构常用算法c++实现,程序目录如下: Array shuffle Prime test(trial division) Prime test(Miller-Rabin's method) 2D Array Arbitary Integer Linear congruential generator Maximum subarray problem Bit...

    C++实现6种排序算法对四种类型数据排序

    在CSort文件中,你可以找到这六种排序算法的C++实现代码,通过阅读和理解这些代码,你可以更好地掌握各种排序算法的原理和使用方法。同时,通过对不同数据集的测试,可以对比分析各种算法的性能差异,从而加深对排序...

    C++实现归并排序(MergeSort)

    C++实现归并排序(MergeSort) 在这里,我们将详细介绍C++实现归并排序(MergeSort)的知识点。归并排序是一种稳定的排序算法,它的思路是将数组不断地分割成两个子序列,直到每个子序列只有一个元素为止,然后将...

    c++排序算法及实现思路

    C++实现时,可以用两个指针分别表示已排序和未排序部分的边界。时间复杂度同样为O(n^2)。 3. 插入排序(Insertion Sort):插入排序通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并...

    经典的排序算法C++实现大全

    本资源“经典的排序算法C++实现大全”提供了九种不同的排序算法,每种都有C++语言的实现,并且包含了算法的简要介绍。以下是对这些经典排序算法的详细讲解: 1. 冒泡排序(Bubble Sort):这是一种简单的排序算法,...

    基于C++实现的七种排序算法源代码及性能评估报告,基于C++实现的冒泡排序、选择排序、插入排序、归并排序、快速排序、计数排序、基数排序

    本报告记录了使用 C++ 初步实现的七种排序算法的基本原理及其在实际样例下的性能评估结果。这些算法包括: 冒泡排序(Bubble Sort) 选择排序(Selection Sort) 插入排序(Insertion Sort) 归并排序(Merge Sort)...

    常用排序算法C++实现

    C++实现通常使用递归,先递归地将数组分为两部分,然后用`merge`函数将已排序的两部分合并。 每种排序算法都有其适用场景,例如,插入排序和冒泡排序适合小规模数据,快速排序和归并排序适合大规模数据,而堆排序在...

    八大排序算法的c++实现

    本项目涵盖了八大基本排序算法的C++实现,下面将详细阐述这些排序算法的原理和实现方法。 1. 冒泡排序(Bubble Sort): 冒泡排序是一种简单直观的排序算法,通过不断交换相邻的逆序元素来逐步将序列调整为有序。在...

    C++实现各种排序算法.zip

    在“sort_algorithm_cpp-master”这个文件夹中,我们可以期待找到这些排序算法的C++实现源代码。通过阅读和理解这些代码,我们可以更深入地学习C++语法,同时掌握每种排序算法的工作原理和性能特点。这对于提升编程...

    合并排序的C++实现

    ### 合并排序的C++实现 #### 一、引言 合并排序是一种经典的排序算法,采用分治法策略来实现高效排序。它通过将数组分成两个子数组,然后对每个子数组进行排序,最后将两个已排序的子数组合并成一个整体。这种算法...

    几个排序算法的C++实现

    本项目提供了几个经典的排序算法的C++实现,有助于理解这些算法的工作原理以及如何在实际编程中应用它们。 1. **冒泡排序(Bubble Sort)**: 冒泡排序是一种简单的排序算法,通过不断交换相邻的逆序元素来逐渐把...

    8种排序算法/c++实现

    C++实现冒泡排序的关键在于两个嵌套循环,外层控制遍历次数,内层用于相邻元素间的比较和交换。 2. 插入排序(Insertion Sort):插入排序的工作原理是将未排序的元素逐个插入到已排序部分的正确位置。C++实现时,...

    C++实现的各种排序算法

    C++实现时,通常采用一个for循环和一个while循环,将未排序元素与已排序部分进行比较并插入正确位置。插入排序在最好情况下(即输入已经是有序的)达到线性时间复杂度O(n),但最坏情况仍为O(n^2)。 3. 选择排序...

    mergesort

    基于c++的归并排序算法。排序算法大体可分为两种: 一种是比较排序,时间复杂度O(nlogn) ~ O(n^2),主要有:冒泡排序,选择排序,插入排序,归并排序,堆排序,快速排序等。 另一种是非比较排序,时间复杂度可以达到...

    算法导论第4至5章代码c++实现

    2. **归并排序(Merge Sort)**:归并排序是一种稳定的排序算法,它将待排序的序列分为两个子序列,分别进行排序,然后合并这两个已排序的子序列。代码实现中会涉及递归和数组的合并操作。 3. **二分查找(Binary ...

    C++数据结构实现之Sorts.zip

    C++实现中,可以使用`&lt;algorithm&gt;`库中的`make_heap`、`push_heap`、`pop_heap`和`sort_heap`函数。 7. 计数排序(Counting Sort)、桶排序(Bucket Sort)和基数排序(Radix Sort): 这些排序算法适用于特定类型...

Global site tag (gtag.js) - Google Analytics