C++实现归并排序（MergeSort）

2024-12-02 17:54:31

本文实例为大家分享了C++实现归并排序的具体代码，供大家参考，具体内容如下

一、思路：稳定排序

（1）划分：一直调用划分过程，直到子序列为空或只有一个元素为止，共需log2(n)；

（2）归并：将两个子序列从小到大合并为一个序列

二、实现程序：

// 归并排序：（二路归并）
// （1）递归分解数组；
// (2)合并有序的序列
#include <iostream>
using namespace std;

// 合并两个有序的序列
template <typename T>
void 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[mid+j+1];
  i = 0;
  j = 0;
  k= start;
  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];
    k++;
    i++;
  }
  while(j < n2) { // 右部分没处理完
    arr[k] = R[j];
    k++;
    j++;
  }
  delete []L;
  delete []R;
}

// 归并排序
template <typename T>
void MergeSort(T arr[], int start, int end) {
  int mid;

  if(start >= end)
    return;

  mid = (start + end) / 2;
  MergeSort(arr, start, mid);
  MergeSort(arr, mid+1, end);
  Merge(arr, start, mid, end);
}

// 输出数组
template <typename T>
void Print(T arr[], int n) {
  int i;

  for(i = 0; i < n; i++)
    cout << arr[i] << " ";
  cout << endl;
}

int main(int argc, const char * argv[]) {
  int n, i, arr[50];

  cout << "请输入要排序的数的个数：";
  cin >> n;
  srand((int)time(NULL)); // 设置时间为随机点
  for(i = 0; i < n; i++) // 产生n个随机数
    arr[i] = rand() % 100;
  cout << "排序前：";
  Print(arr, n);
  MergeSort(arr, 0, n-1); // 调用归并排序
  cout << "排序后：";
  Print(arr, n);
  return 0;
}

测试结果：

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

C++归并排序算法实例

归并排序归并排序算法是采用分治法的一个非常典型的应用.归并排序的思想是将一个数组中的数都分成单个的:对于单独的一个数,它肯定是有序的,然后,我们将这些有序的单个数在合并起来,组成一个有序的数列.这就是归并排序的思想.它的时间复杂度为O(N*logN). 代码实现复制代码代码如下: #include <iostream> using namespace std; //将有二个有序数列a[first...mid]和a[mid...last]合并. void mergearray(int
c++归并排序详解

说一说归并排序归并排序:归并排序(英语:Merge sort,或mergesort),是创建在归并操作上的一种有效的排序算法,效率为O(n log n).1945年由约翰·冯·诺伊曼首次提出.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行. 归并排序的核心思想是将两个有序的数列合并成一个大的有序的序列.通过递归,层层合并,即为归并. 如图,从下到上,每一步都需要将两个已经有序的子数组合并成一个大的有序数组,如下是实现合并的具体代码,请
C++实现自底向上的归并排序算法

本文实例讲述了C++实现自底向上的归并排序算法.分享给大家供大家参考,具体如下: 一. 算法描述自底向上的归并排序:归并排序主要是完成将若干个有序子序列合并成一个完整的有序子序列:自底向上的排序是归并排序的一种实现方式,将一个无序的N长数组切个成N个有序子序列,然后再两两合并,然后再将合并后的N/2(或者N/2 + 1)个子序列继续进行两两合并,以此类推得到一个完整的有序数组.下图详细的分解了自底向上的合并算法的实现过程: 二. 算法实现 /*=========================
c++实现二路归并排序的示例代码

二路归并排序基本思想二路归并排序就是将两个有序子表归并成一个有序表.首先我们得有一个算法用于归并:两个有序表放在同一数组的相邻位置上,arr[left]到arr[center-1]为第一个有序表,arr[center]到arr[right]是第二个有序表.每次从两端中取出一个进行比较,小的先放在一个temp数组,最后将比较剩下的直接放到temp中去,最后将temp又复制回arr.这是"治". 所谓"分",就是递归地将前半部分和后半部分的数据各自归并排序即可. 算
C++实现的归并排序算法详解

本文实例讲述了C++实现的归并排序算法.分享给大家供大家参考,具体如下: 归并排序归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法. 该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列: 即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 归并过程 1.比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到temp[k]中,并令i
C++实现自顶向下的归并排序算法

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

归并归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 算法描述归并操作的工作原理如下: 1.申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 2.设定两个指针,最初位置分别为两个已经排序序列的起始位置 3.比较两个指针所指向的元素,选择相对小
C++实现归并排序

定义:归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 简单的来说,归并排序主要分为三步,一是对数组的划分,二是对数组的排序,三是对数组的合并.划分的大小是可以随自己的想法而设置,但是一般都是以2为单位,这样最小的一组的排序就比较方便. 具体一个简单的例子: 设有数
java实现归并排序算法

归并排序算法思想: 分而治之(divide - conquer);每个递归过程涉及三个步骤第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素. 第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作第三, 合并: 合并两个排好序的子序列,生成排序结果. public static void mergeSort(int[] a, int[] tmp, int left, int right) { if (left < righ
golang/python实现归并排序实例代码

归并排序思路:将数组不断二分,然后合并为有序数组 C++实现: void mergeSort(T arr[], int left,int right) { //对arr[left,right]的范围进行排序 if (left >= right) return; int mid = (left + right) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right);
常用Java排序算法详解

一.选择排序(SelectSort) 基本原理:对于给定的一组记录,经过第一轮比较后得到最小的记录,然后将该记录与第一个记录的位置进行交换:接着对不包括第一个记录以外的其他记录进行第二次比较,得到最小的记录并与第二个记录进行位置交换:重复该过程,直到进行比较的记录只有一个为止. public class SelectSort { public static void selectSort(int[] array) { int i; int j; int temp; int flag; for (
Java多种经典排序算法(含动态图)

算法分析一个排序算法的好坏,一般是通过下面几个关键信息来分析的,下面先介绍一下这几个关键信息,然后再将常见的排序算法的这些关键信息统计出来. 名词介绍时间复杂度:指对数据操作的次数(或是简单的理解为某段代码的执行次数).举例:O(1):常数时间复杂度:O(log n):对数时间复杂度:O(n):线性时间复杂度. 空间复杂度:某段代码每次执行时需要开辟的内存大小. 内部排序:不依赖外部的空间,直接在数据内部进行排序: 外部排序:数据的排序,不能通过内部空间来完成,需要依赖外部空间. 稳定排序:
C++实现归并排序（MergeSort）

本文实例为大家分享了C++实现归并排序的具体代码,供大家参考,具体内容如下一.思路:稳定排序 (1)划分:一直调用划分过程,直到子序列为空或只有一个元素为止,共需log2(n): (2)归并:将两个子序列从小到大合并为一个序列二.实现程序: // 归并排序:(二路归并) // (1)递归分解数组: // (2)合并有序的序列 #include <iostream> using namespace std; // 合并两个有序的序列 template <typename T> v
java二路归并排序示例分享

归并排序就是采用分治法进行排序: (1)将一个数组分成小的2个数组分别进行排序: (2)之后将分出来的已经拍好序的数组进行合并: 复制代码代码如下: import java.util.Scanner;public class MergeSort { int[] a=null; int[] b=null; int n; Scanner sin=null; MergeSort() { a=new int[10000]; b=new int[
Java经典排序算法之归并排序详解

一.归并排序归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 归并过程为:比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1:否则将第二个有序表中的元素a[j]复制到r[k]中,并令j和k分别加上1,如此循环下去,直
java 归并排序的实例详解

java 归并排序的实例详解归并排序归并排序,指的是将两个已经排序的序列合并成一个序列的操作. 归并操作的过程如下: 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列设定两个指针,最初位置分别为两个已经排序序列的起始位置比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置重复步骤3直到某一指针到达序列尾将另一序列剩下的所有元素直接复制到合并序列尾 Java代码 /** * 归并排序 * * @param ts */ @SuppressWa
JavaScript希尔排序、快速排序、归并排序算法

以var a = [4,2,6,3,1,9,5,7,8,0];为例子. 1.希尔排序. 希尔排序是在插入排序上面做的升级.是先跟距离较远的进行比较的一些方法. function shellsort(arr){ var i,k,j,len=arr.length,gap = Math.ceil(len/2),temp; while(gap>0){ for (var k = 0; k < gap; k++) { var tagArr = []; tagArr.push(arr[k]) for (i

C++实现归并排序（MergeSort）

相关推荐

随机推荐