合并排序(C语言实现)

其基本模式如下：

分解：把一个问题分解成与原问题相似的子问题

解决：递归的解各个子问题

合并：合并子问题的结果得到了原问题的解。

现在就用递归算法，采用上面的分治思想来解合并排序。

合并排序（非降序）

分解：把合并排序分解成与两个子问题

伪代码：

代码如下:

MERGE_SORT(A, begin, end)

if begin < end

then mid<- int((begin + end)/2)

MERGE_SORT(A, begin, mid)

MERGE_SORT(A, mid+1, end)

MERGE(A, begin, mid, end)

解决：递归的解各个子问题,每个子问题又继续递归调用自己，直到"begin<end"这一条件不满足时，即"begin==end"时，此时只有一个元素，显然是有序的，这样再进行下一步合并。

合并：合并的子问题的结果有个隐含问题，即各个子问题已经是排好序的了（从两个氮元素序列开始合并）。做法是比较两个子序列的第一个元素小的写入最终结果，再往下比较，如下图所示：

图中：待排序数组为2 4 6  1 3 5

把2 4 6和 1 3 5 分别存到一个数组中，比较两个数组的第一个元素大小小者存于大数组中，直到两小数组中元素都为32767.

这里32767 味无穷大，因为 c语言中  int类型是32位，表示范围是-32768-----32768。用无穷大作为靶子可以减少对两个小数组是否为空的判断，有了靶子，直接判断大数组元素个数次就排完了。

在整个过程中执行过程示如下图：

分解+执行时自上向下，合并时自下向上。

代码奉上：

代码如下:

#include <stdio.h>

void MERGE(int *A, int b, int m, int e)

{

int l = m-b+1, r = e-m, i;

int L[l+1], R[r+1];

for(i=0; i< l; i++)

{

L[i] = A[b+i];

}

for (i=0; i< r; i++)

{

R[i] = A[m+i+1];

}

L[l] = 32767;

R[r] = 32767;

l = 0;

r = 0;

for(i=0; i< e-b+1; i++)

{

if(L[l] < R[r])

{

A[b+i] = L[l];

l ++;

}

else            {

A[b+i] = R[r];

r ++;

}

}

}

void MERGE_SORT(int *A, int b, int e)

{

if(b < e)

{

int m = (b + e) / 2;

MERGE_SORT(A, b, m);

MERGE_SORT(A, m+1, e);

MERGE(A, b, m, e);

}

}

int main()

{

int A[500];

int lens, i;

printf("Please Enter the lenghth of array:");

scanf("%d", &lens);

printf("Please Enter the elements of the array:");

for(i=0; i< lens; i++)

scanf("%d", &A[i]);

MERGE_SORT(A, 0, lens-1);

printf("the result of the sort is:\n");

for(i=0; i< lens; i++)

{

printf("%d ", A[i]);

}

return 0;

}

赞 (0)

相关推荐

  • Ruby实现的合并排序算法

    算法课的作业,利用分治法,合并排序. #encoding: utf-8 #author: xu jin, 4100213 #date: Oct 27, 2012 #MergeSort #to sort an array by using MergeSort algorithm #example output: #The original array is:[4, 32, 84, 58, 49, 40, 75, 29, 82, 21, 70, 37, 70] #The sorted array i

  • Python选择排序、冒泡排序、合并排序代码实例

    前两天刚装了python 3.1.1, 禁不住技痒写点code. 1.选择排序 复制代码 代码如下: >>> def SelSort(L):     length=len(L)     for i in range(length-1):         minIdx=i         minVal=L[i]         j=i+1         while j<length:             if minVal>L[j]:                 mi

  • C语言合并排序及实例代码

    C语言合并排序及实例代码

    归并排序也称合并排序,其算法思想是将待排序序列分为两部分,依次对分得的两个部分再次使用归并排序,之后再对其进行合并.仅从算法思想上了解归并排序会觉得很抽象,接下来就以对序列A[0], A[l]-, A[n-1]进行升序排列来进行讲解,在此采用自顶向下的实现方法. 操作步骤如下: (1)将所要进行的排序序列分为左右两个部分,如果要进行排序的序列的起始元素下标为first,最后一个元素的下标为last,那么左右两部分之间的临界点下标mid=(first+last)/2,这两部分分别是A[first

  • java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述

    算法是在有限步骤内求解某一问题所使用的一组定义明确的规则.通俗点说,就是计算机解题的过程.在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法.前者是推理实现的算法,后者是操作实现的算法. 一个算法应该具有以下五个重要的特征: 1.有穷性: 一个算法必须保证执行有限步之后结束: 2.确切性: 算法的每一步骤必须有确切的定义: 3.输入:一个算法有0个或多个输入,以刻画运算对象的初始情况: 4.输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果.没有输出的算法是毫无意义的:

  • C++实现合并排序的方法

    本文实例讲述了C++实现合并排序的方法.分享给大家供大家参考.具体如下: //合并排序 #include<iostream> #include<cmath> using namespace std; int num[100]; void print(int num[],int len) { for(int i=0;i<len;i++) { cout<<num[i]<<" "; } cout<<endl; } void m

  • Javascript排序算法之合并排序（归并排序）的2个例子

    归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用. 归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序是建立在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个

  • 合并排序(C语言实现)

    合并排序(C语言实现)

    其基本模式如下: 分解:把一个问题分解成与原问题相似的子问题 解决:递归的解各个子问题 合并:合并子问题的结果得到了原问题的解. 现在就用递归算法,采用上面的分治思想来解合并排序. 合并排序(非降序) 分解:把合并排序分解成与两个子问题 伪代码: 复制代码 代码如下: MERGE_SORT(A, begin, end) if begin < end then mid<- int((begin + end)/2) MERGE_SORT(A, begin, mid) MERGE_SORT(A, m

  • PHP实现合并两个排序链表的方法

    本文实例讲述了PHP实现合并两个排序链表的方法.分享给大家供大家参考,具体如下: 问题 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. 解决思路 简单的合并排序.由于两个数列本来就是递增的,所以每次将两个数列中较小的部分拿过来就可以了. 实现代码 <?php /*class ListNode{ var $val; var $next = NULL; function __construct($x){ $this->val = $x; } }*/ f

  • TypeScript合并两个排序链表的方法详解

    TypeScript合并两个排序链表的方法详解

    目录 前言 思路分析 实现代码 测试用例 示例代码 前言 给定两个递增排序的链表,如何将这两个链表合并?合并后的链表依然按照递增排序.本文就跟大家分享一种解决方案,欢迎各位感兴趣的开发者阅读本文. 思路分析 经过前面的学习,我们知道了有关链表的操作可以用指针来完成.同样的,这个问题也可以用双指针的思路来实现: p1指针指向链表1的头节点 p2指针指向链表2的头节点 声明一个变量存储合并后的链表,比对两个指针指向的节点值大小: 如果p1指针指向的节点值比p2指向的值小,合并后的链表节点就取p1节点

  • php实现的常见排序算法汇总

    本文汇总了常见的php排序算法,在进行算法设计的时候有不错的借鉴价值.现分享给大家供参考之用.具体如下: 一.插入排序 用文字简单的描述,比如说$arr = array(4,2,4,6,3,6,1,7,9); 这样的一组数字进行顺序排序: 那么,首先,拿数组的第二个元素和第一元素比较,假如第一个元素大于第二元素,那么就让两者位置互换,接下来,拿数组的第三个元素,分别和第二个,第一个元素比较,假如第三个元素小,那么就互换.依次类推.这就是插入排序,它的时间频度是:1+2+...+(n-1)=(n^

随机推荐