C++实现归并排序的实例

  • 时间:
  • 7175人关注

这篇文章主要为大家详细介绍了C++实现归并排序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下,另外这篇文章主要知识点是关于C++、归并排序、C++归并排序的内容,如果大家想对相关知识点有系统深入的学习,可以参阅以下电子资料:

教程详情电子资料
  • 教程类别:C++归并排序
  • 编辑整理:谷乐成
  • 教程字数:2136字节
  • 阅读时间:大概6分钟
  • 下载本教程(DOC版)
  • C++从入门到精通
  • C和C++程序员面试秘笈
  • C及C++程序设计
  • 数据结构:用C++语言描述
  • C++面向对象程序设计(第2版)
  • 定义:归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

    简单的来说,归并排序主要分为三步,一是对数组的划分,二是对数组的排序,三是对数组的合并。划分的大小是可以随自己的想法而设置,但是一般都是以2为单位,这样最小的一组的排序就比较方便。

    具体一个简单的例子:

    设有数列{6,202,100,301,38,8,1}

    初始状态:6,202,100,301,38,8,1

    第一次归并后:{6,202},{100,301},{8,38},{1},比较次数:3;

    第二次归并后:{6,100,202,301},{1,8,38},比较次数:4;

    第三次归并后:{1,6,8,38,100,202,301},比较次数:4;

    总的比较次数为:3+4+4=11;

    逆序数为14;

    在利用算法实现的时候,需要利用递归的思想,函数的入口是整个数组,不断进行划分,直到划分的数组只剩下一个或两个元素为止,对这一组进行排序后,再按原来划分的大小还原并排序,这里利用一个新的数组比较方便,将两个排序后的数组,再从小到大一个一个放入新的数组。

    具体代码:

    #include<iostream>
    #include<algorithm>
    using namespace std;
     
    void merge(int *data,int start,int end,int *result) 
    {
      int left_length = (end - start + 1) / 2 + 1;  
      int left_index = start;
      int right_index = start + left_length;
      int result_index = start;
      while(left_index<start + left_length && right_index <end + 1) //store data into new array
      {
        if(data[left_index] <= data[right_index])
          result[result_index++] = data[left_index++];
        else
          result[result_index++] = data[right_index++];
      }
      while(left_index < start + left_length)
        result[result_index++] = data[left_index++];
      while(right_index <end+1)
        result[result_index++] = data[right_index++];
    }
     
    void merge_sort(int *data,int start,int end,int *result)
    {
      if(1 == end - start)  //last only two elements
      {
        if(data[start] > data[end])
        {
          int temp = data[start];
          data[start] = data[end];
          data[end] = temp;
        }
        return;
      }
      else if (end == start)
        return; //last one element then there is no need to sort;
      else{
        //continue to divide the interval
        merge_sort(data, start, (end - start + 1) / 2 + start, result);
        merge_sort(data, (end - start + 1) / 2 + start + 1, end, result);
        //start to merge sorted data
        merge(data, start, end, result);
        for (int i = start; i <= end;++i)
        {
          data[i] = result[i];
        }
      }
     
    }
    //example
    int main()
    {
      int data[] = {5,3,6,7,3,2,7,9,8,6,34,32,5,4,43,12,37};
      int length = 17;
      int result[length];
      cout << "before sorted:"<<'\n';
      for (int i = 0; i < length;i++)
        cout << data[i]<<' ';
      cout << '\n'
         << "after sorted:"<<'\n';
      merge_sort(data, 0, length - 1, result);
      for (int i = 0; i < length;i++)
        cout << result[i]<<' ';
      return 0;
    }

    以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持码农之家。

    码农之家
    C++/GoLang如何实现自底向上的归并排序

    11小时46分钟前回答

    C++/GoLang如何实现自底向上的归并排序

    前言

    上一篇文章写了一个自顶向下的归并排序,把一个完整的数组不断二分,然后再合并。其实换一种思路:把数组中相邻的N个元素看成是已经二分好了的,直接进行合并,就省掉了二分那一步骤

    C++实现:

    template<typename T>
    void mergeSortButton2Top(T arr[], int n) {
     for (int size = 1; size <= n; size += size) {
     for (int i = 0; i+size < n; i+=2*size) //对[i,i+size-1]和[i+size,i+2*size-1]进行归并
     __merge(arr, i, i + size - 1, min(i + size + size - 1,n-1));// arr left mid right 如果i+2*size>n了,越界了,就取n-1
     }
    }
    
    template<typename T>
    void __merge(T arr[], int left, int mid, int right) { //将arr[left,mid] 和 arr[mid+1,right] 两部分进行归并
    
     T *tmp=new T[right-left+1];
     for (int i = left; i <= right; i++)
     tmp[i - left] = arr[i]; //先把arr(需要合并的左右片段) 复制给tmp
    
     int i = left, j = mid + 1; // i 做为左半部分的指针 j作为右半部分的指针
     for (int k = left; k <= right; k++) {
     if (i > mid) { // 左半部分 已经合入完了,将右半部分剩下的 全部合入
     arr[k] = tmp[j - left];
     j++;
     }
     else if (j > right) { // 右半部分 已经合入完了,将左半部分剩下的 全部合入
     arr[k] = tmp[i - left];
     i++;
     }
     else if (tmp[i - left] < tmp[j - left]) {
     arr[k] = tmp[i - left];
     i++;
     }
     else {
     arr[k] = tmp[j - left];
     j++;
     }
     }
     delete[] tmp;
    }
    
    int main() {
     int arr[9] = { 1,5,6,78,12,5,1,12,54 };
     mergeSortButton2Top(arr,9);
     for (int i = 0; i < 9; i++) {
     cout << arr[i]<<" ";
     }
     return 0;
    }
    
    

    GoLang实现:

    func mergeSortButton2Top(arr [] int) {
     var lenth int = len(arr)
     for size := 1; size <= lenth; size += size {
     for i := 0; i+size < lenth; i += 2 * size { //对[i,i+size-1]和[i+size,i+2*size-1]进行归并
      merge(arr, i, i+size-1, int(math.Min(float64(i+2*size-1), float64(lenth-1))))// arr left mid right 如果i+2*size>n了,越界了,就取n-1
     }
     }
    }
    
    func merge(arr []int, left, mid, right int) {
     // 将要合并的部分做个拷贝
     var tmp []int = make([]int, right-left+1)
     for i, j := left, 0; i <= right; i++ {
     tmp[j] = arr[i]
     j++
     }
     // i做为左半部分的指针 j作为右半部分的指针
     var i, j int = left, mid+1
     for k := left; k <= right; k++ {
     if i > mid { // 左半部分 已经合入完了,将右半部分剩下的 全部合入
      arr[k] = tmp[j-left]
      j++
     } else if j > right { // 右半部分 已经合入完了,将左半部分剩下的 全部合入
      arr[k] = tmp[i-left]
      i++
     } else if tmp[i-left] > tmp[j-left] {
      arr[k] = tmp[j-left]
      j++
     } else {
      arr[k] = tmp[i-left]
      i++
     }
     }
    }
    
    

    用golang对两种归并排序进行计时,观察性能:

    func createRandomArray(count int) []int {
     rand.Seed(time.Now().UnixNano())
     var arr [] int = make([]int, 0)
     for i := 0; i < count; i++ {
     arr = append(arr, rand.Intn(100))
     }
     return arr
    }
    
    func main() {
     count := 10000
     arr := createRandomArray(count)
     var arr2 []int = make([]int, count)
     copy(arr2, arr)
     start := time.Now()
     mergeSort(arr, 0, len(arr)-1)
     fmt.Println("自顶向下归并排序 用时:", time.Since(start))
    
     start = time.Now()
     mergeSortButton2Top(arr2)
     fmt.Println("自底向上归并排序 用时:", time.Since(start))
    }
    
    //输出:
    //自顶向下归并排序 用时: 4.997ms
    //自底向上归并排序 用时: 3.9987ms
    
    

    因为自底向上少了二分那个步骤,性能要优于自顶向下的归并排序

    总结

    到此这篇关于C++/GoLang如何实现自底向上的归并排序的文章就介绍到这了,更多相关C++/GoLang自底向上的归并排序内容请搜索码农之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持码农之家!

    展开阅读

    上一篇:C++实现会员管理程序的具体方案

    下一篇:C语言扫雷游戏实例代码

    相关内容

    • C++标准库中sstream与strstream的区别点总结

      以下是对C++标准库中sstream与strstream的区别进行了详细的分析介绍,需要的朋友可以过来参考下

      06-08C++标准库中sstream与strstream知识点总结

      阅读更多
    • C/C++实现控制台输出不同颜色字体的实例讲解

      这篇文章主要介绍了C/C++实现控制台输出不同颜色字体的方法,涉及C++控制台文字属性相关设置操作技巧,需要的朋友可以参考下

      05-30C/C++控制台输出不同颜色字体

      阅读更多
    • C++实现会员管理程序的具体方案

      这篇文章主要为大家详细介绍了C++实现会员管理程序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

      06-01C++会员管理程序

      阅读更多
    • C++编译器无法捕捉到的8种错误实例分析

      这篇文章主要介绍了C++编译器无法捕捉到的8种错误,是深入学习C++所必须加以掌握的排错技能,需要的朋友可以参考下

      06-09C++编译器无法捕捉到的8种错误

      阅读更多
    • c++读取数据文件到数组的实例

      今天小编就为大家分享一篇c++读取数据文件到数组的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧

      05-11c++读取数据文件到数组

      阅读更多
    • C语言实现C++继承和多态的实例内容

      本文主要给大家简单讲诉了C和C++的区别以及如何使用C语言模拟实现C++继承和多态,并附上示例代码,是篇相当不错的文章,推荐给喜欢C语言的小伙伴们

      06-10C语言实现C++继承和多态

      阅读更多
    • C++和Java命令行绘制心形图代码分享

      这篇文章主要为大家详细介绍了C++和Java命令行绘制心形图案,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

      04-21C++和Java命令行绘制心形图案

      阅读更多
    • C++语法详解

      C++语法详解

      C++语法详解适合有一定C++基础、对C++的语法有疑惑、想深入了解C++语法细节的人员阅读。《C++语法详解》同时也可以作为解决C++语法问题的参考书;对于学习过C++或已精通C++的人员,也是一本不错的资料查阅手册

      大小:117 MBC++编程

      点击下载
    • C++程序设计语言(第1-3部分)

      C++程序设计语言(第1-3部分)

      《C 程序设计语言》(原书第4版) 是C 领域最经典的参考书,介绍了C 11的各项新特性和新功能。全书共分四部分。第一部分(第1~5章)是引言,包括C 的背景知识,C 语言及其标准库的简要介绍

      大小:157.9 MBC++

      点击下载
    • C++17标准语言新特性

      C++17标准语言新特性

      2017年,C++ 17标准发布,基于 C++ 11,C++ 17旨在使C++成为一个不那么臃肿复杂的编程语言,以简化该语言的日常使用,使开发者可以更简单地编写和维护代码。 C++ 17是对C++语言的重大更新,引入了许多新的语言特性,不过,许多C++程序员对C++ 17还不是很了解,今天和大家推荐一本免费电子书《C++ 17 in detail》 这本书的作者是Bart#322;omiejFilipek,他是C ++社区中最活跃的博客作者之一,下面就和大家一起介绍一下这本书。 在计算机科学世界中,有许多

      大小:1.05 MBC++

      点击下载

    学习笔记

    38小时6分钟前回答

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

    本文实例为大家分享了C++实现归并排序的具体代码,供大家参考,具体内容如下 一、思路:稳定排序 (1)划分:一直调用划分过程,直到子序列为空或只有一个元素为止,共需log2(n); (2)归并:将两个子序列从小到大合并为一个序列 二、实现程序: // 归并排序:(二路归并)// (1)递归分解数组;// (2)合并有序的序列#include iostreamusing namespace std; // 合并两个有序的序列template typename Tvoid Merge(T arr[], int start, int mid, int end) { int i, j, k, n1, n2; k=0; n1 = mid - start + 1; n2 = end - mid; T *L = new T[n1], *R = new T[n2]; for(i = 0; i n1; i++) // 将arr的左部分赋给L L[i] = arr[start+i]; for(j = 0; j n2; j++) // 将arr的右部分赋给R R[j] = arr[m……

    7小时39分钟前回答

    C++实现自顶向下的归并排序算法

    本文实例讲述了C++实现自顶向下的归并排序算法。分享给大家供大家参考,具体如下: 一. 算法描述 自顶向下的归并排序:采用分治法进行自顶向下的程序设计方式,分治法的核心思想就是分解、求解、合并。 1. 先将长度为N的无序序列分割平均分割为两段 2. 然后分别对前半段进行归并排序、后半段进行归并排序 3. 最后再将排序好的前半段和后半段归并 过程(2)中进行递归求解,最终下图详细的分解了自顶向下的合并算法的实现过程: 二. 算法实现 /*=============================================================================## FileName: mergeSort.c# Algorithm: 归并排序(自顶向下)# Author: Knife# Created: 2014-06-14 16:40:02#======……