C语言分治法实现归并排序

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

归并排序的基本思想：

将两个及其以上的有序表合并为一张有序表，把待排序序列通过分治法分为若干个有序子序列，然后每两个子序列合并为一个子序列，经过多次合并后整合为一张有序表。

排序过程如图：

代码如下：

#include "stdio.h"
#define MAX 100
int is1[MAX],is2[MAX];//原数组is1，临时空间数组is2
void merge(int low,int mid,int high){
  int i=low,j=mid+1,k=low;
  while(i<=mid&&j<=high)
    if(is1[i]<is1[j])
      is2[k++]=is1[i++];
    else
      is2[k++]=is1[j++];
  while(i<=mid)
    is2[k++]=is1[i++];
  while (j<=high)
    is2[k++]=is1[j++];
  for ( i = low; i <=high ; i++) {
    is1[i]=is2[i];
    printf("%5d",is1[i]);
  }
  printf("\n");
}

void mergeSort(int a, int b){
  if(a<b){
    int mid=(a+b)/2;
    mergeSort(a,mid);
    mergeSort(mid+1,b);
    merge(a,mid,b);
  }
}

void main(){
  int i,n;
  printf("请输入元素个数：");
  scanf("%d",&n);
  printf("请依次输入每个元素：\n");
  for ( i = 1; i <=n ; ++i) {
    scanf("%d",&is1[i]);
  }
  mergeSort(1,n);
  printf("排序后的序列为：\n");
  for ( i = 1; i <=n ; ++i) {
    printf("%4d",is1[i]);
  }
}

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

赞 (0)

相关推荐

  • C语言演示对归并排序算法的优化实现

    基础 如果有两个数组已经有序,那么可以把这两个数组归并为更大的一个有序数组.归并排序便是建立在这一基础上.要将一个数组排序,可以将它划分为两个子数组分别排序,然后将结果归并,使得整体有序.子数组的排序同样采用这样的方法排序,这个过程是递归的. 下面是示例代码: #include "timsort.h" #include <stdlib.h> #include <string.h> // 将两个长度分别为l1, l2的已排序数组p1, p2合并为一个 // 已排序

  • C语言实现排序算法之归并排序详解

    排序算法中的归并排序(Merge Sort)是利用"归并"技术来进行排序.归并是指将若干个已排序的子文件合并成一个有序的文件. 一.实现原理: 1.算法基本思路 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回R[low..high]中. (1)合并过程 合并过程中,设置i,j和p三个指针,其初值分别指向这三个记录区的起始位置.合并时依次比较R[i

  • C语言 实现归并排序算法

    C语言 实现归并排序算法

    C语言 实现归并排序算法 归并排序(Merge sort)是创建在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用. 一个归并排序的例子:对一个随机点的链表进行排序 算法描述 归并操作的过程如下: 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 设定两个指针,最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置 重复步骤3直到某一指针到达序列尾

  • C语言中数据结构之链表归并排序实例代码

    C语言中数据结构之链表归并排序实例代码

    C语言中数据结构之链表归并排序实例代码 问题 设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增排序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏. 源程序 #include <stdio.h> #include<stdlib.h> #define N1 6 /*链表La的长度*/ #define N2 6 /*链表Lb的

  • C语言开发之归并排序详解及实例

    C语言开发之归并排序详解及实例

     C语言归并排序 即将两个都升序(或降序)排列的数据序列合并成一个仍按原序排列的序列. 上代码: #include <stdio.h> #include <stdlib.h> #define m 6 #define n 4 int main() { int a[m]={-3,6,19,26,68,100} ,b[n]={8,10,12,22}; int i,j,k,c[m+n]; int l ; i=j=k=0; printf("a数组的元素:\n"); for

  • C语言数据结构 链表与归并排序实例详解

    C语言数据结构 链表与归并排序实例详解

    C语言数据结构 链表与归并排序实例详解 归并排序适合于对链表进行原址排序,即只改变指针的连接方式,不交换链表结点的内容. 归并排序的基本思想是分治法:先把一个链表分割成只有一个节点的链表,然后按照一定顺序.自底向上合并相邻的两个链表. 只要保证各种大小的子链表是有序的,那么最后返回的链表就一定是有序的. 归并排序分为分割和合并两个子过程.分割是用递归的方法,把链表对半分割成两个子链表:合并是在递归返回(回朔)的时候,把两个有序链表合并成一个有序链表. (注意:只有一个节点的链表一定是有序的) 这

  • 举例讲解C语言对归并排序算法的基础使用

    基础概念 百度百科是这么描述归并排序的: 归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作. 设有数列 {6,202,100,301,38,8,1} 初始状态: [6] [202] [100] [301] [38] [8] [1] 比较次数 i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 3 i=2 [ 6 100 202 301 ] [ 1 8 38 ] 4 i=3 [ 1 6 8 38 100 202 301 ] 4 总计: 1

  • C语言分治法实现归并排序

    C语言分治法实现归并排序

    本文实例为大家分享了C语言实现归并排序的具体代码,供大家参考,具体内容如下 归并排序的基本思想: 将两个及其以上的有序表合并为一张有序表,把待排序序列通过分治法分为若干个有序子序列,然后每两个子序列合并为一个子序列,经过多次合并后整合为一张有序表. 排序过程如图: 代码如下: #include "stdio.h" #define MAX 100 int is1[MAX],is2[MAX];//原数组is1,临时空间数组is2 void merge(int low,int mid,int

  • C语言实现分治法实例

    本文为大家分享了C语言实现分治法实例代码,供大家参考,具体内容如下 使用分治法求最大值 这个函数将数组a[l]...a[r]分成a[l],...,a[m]和a[m+1],...a[r]两部分,分别求出每一部分的最大元素(递归地),并返回较大的那一个作为整个数组的最大元素.如果数组大小是偶数,则两部分大小相等;如果是奇数,第一部分比第二部分的大小大1. #include <cstdio> #include <cstdlib> #include <algorithm> #i

  • 算法详解之分治法具体实现

    算法详解之分治法具体实现

    分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同.求出子问题的解,就可得到原问题的解. 分治法解题的一般步骤: (1)分解,将要解决的问题划分成若干规模较小的同类问题: (2)求解,当子问题划分得足够小时,用较简单的方法解决: (3)合并,按原问题的要求,将子问题的解逐层合并构成原问题的解. 一言以蔽之:分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之. 在认识分治之前很有必要先了解一下递

  • C语言常见排序算法归并排序

    C语言常见排序算法归并排序

    目录 前言 一.归并排序 1.1 基本思想 1.2 算法思想 1.3 程序设计思想 1.4 程序实现 1.5 归并排序的特性总结 前言 本期为大家带来的是常见排序算法中的归并排序,博主在这里先分享归并排序的递归算法,包您一看就会,快来试试吧~ 一.归并排序 1.1 基本思想 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法 (Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序 列:即先使每个子序列有序,再使

  • python分治法求二维数组局部峰值方法

    题目的意思大致是在一个n*m的二维数组中,找到一个局部峰值.峰值要求大于相邻的四个元素(数组边界以外视为负无穷),比如最后我们找到峰值A[j][i],则有A[j][i] > A[j+1][i] && A[j][i] > A[j-1][i] && A[j][i] > A[j][i+1] && A[j][i] > A[j][i-1].返回该峰值的坐标和值. 当然,最简单直接的方法就是遍历所有数组元素,判断是否为峰值,时间复杂度为O(n^2

  • Python分治法定义与应用实例详解

    本文实例讲述了Python分治法定义与应用.分享给大家供大家参考,具体如下: 分治法所能解决的问题一般具有以下几个特征: 1) 该问题的规模缩小到一定的程度就可以容易地解决 2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质. 3) 利用该问题分解出的子问题的解可以合并为该问题的解: 4) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题. 第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加: 第二条特征是应用

  • python使用分治法实现求解最大值的方法

    本文实例讲述了python使用分治法实现求解最大值的方法.分享给大家供大家参考.具体分析如下: 题目: 给定一个顺序表,编写一个求出其最大值和最小值的分治算法. 分析: 由于顺序表的结构没有给出,作为演示分治法这里从简顺序表取一整形数组数组大小由用户定义,数据随机生成.我们知道如果数组大小为 1 则可以直接给出结果,如果大小为 2则一次比较即可得出结果,于是我们找到求解该问题的子问题即: 数组大小 <= 2.到此我们就可以进行分治运算了,只要求解的问题数组长度比 2 大就继续分治,否则求解子问题

  • Java分治法与二分搜索算法实例分析

    Java分治法与二分搜索算法实例分析

    本文实例讲述了Java分治法与二分搜索算法.分享给大家供大家参考,具体如下: 1.分治法 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题相互独立且与原问题相同.递归的解这些子问题,然后将各子问题的解合并得到原问题的解. 分治法所能解决的问题一般具有以下几个特征: 1) 该问题的规模缩小到一定的程度就可以容易地解决 2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质. 3) 利用该问题分解出的子问题的解可以合并为该问题的解: 4) 该问题所分解

  • Java基于分治法实现的快速排序算法示例

    Java基于分治法实现的快速排序算法示例

    本文实例讲述了Java基于分治法实现的快速排序算法.分享给大家供大家参考,具体如下: package cn.nwsuaf.quick; /** * 随机产生20个数,并对其进行快速排序 * * @author 刘永浪 * */ public class Quick { /** * 交换函数,实现数组中两个数的交换操作 * * @param array * 待操作数组 * @param i * 交换数组的第一个下标 * @param j * 交换数组的第二个下标 */ public static

随机推荐