欢迎来到入门教程网!

C语言

当前位置:主页 > 软件编程 > C语言 >

归并排序的递归实现与非递归实现代码

来源:本站原创|时间:2020-01-10|栏目:C语言|点击:

归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。值得注意的是归并排序是一种稳定的排序方法。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

算法描述
归并操作的工作原理如下:
第一步:申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
第二步:设定两个指针,最初位置分别为两个已经排序序列的起始位置
第三步:比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置

时间复杂度:
时间复杂度为O(nlogn) 这是该算法中最好、最坏和平均的时间性能。
空间复杂度为 O(n)
比较操作的次数介于(nlogn) / 2和nlogn - n + 1。
赋值操作的次数是(2nlogn)。归并算法的空间复杂度为:0 (n)
归并排序比较占用内存,但却效率高且稳定的算法。
(以上摘抄自百度百科)

代码实现
自顶向上实现:
//使用辅助数组实现归并的过程

复制代码 代码如下:

void MergeSort(int *aux, int *data, int l, int m, int h)
{
 int k=0, i=l, j=m+1;

 for(k=l; k<=h; k++)
 {
  if(i>m)     aux[k]=data[j++];
  else if(j>h)    aux[k]=data[i++];
  else if(data[i]<data[j])        aux[k]=data[i++];
  else    aux[k]=data[j++];
 }
 for(k=l; k<=h; k++)
  data[k]=aux[k];
}

用递归实现排序的过程(自顶向下归并)
复制代码 代码如下:

void Sort(int *aux, int *data, int l, int h)
{
 if(l<h)
 {
  int m=l+(h-l)/2;
  Sort(aux, data, l, m);
  Sort(aux, data, m+1, h);
  MergeSort(aux,data, l, m, h);
 }
}

用非递归实现排序的过程(自底向上归并)
复制代码 代码如下:

void NonRerMerSort(int *aux, int *data, int l, int h)
{
 int i=l, j;
 for(i=l; i<=h; i=2*i)
 {
  for(j=l; j<=h-i; j+=2*i)
   MergeSort(aux, data, j, i+j-1, Min(j+2*i-1,h));
 }
}

上一篇:解析static在C和C++中的用法以及区别

栏    目:C语言

下一篇:一般函数指针和类的成员函数指针深入解析

本文标题:归并排序的递归实现与非递归实现代码

本文地址:https://www.xiuzhanwang.com/a1/Cyuyan/4222.html

网页制作CMS教程网络编程软件编程脚本语言数据库服务器

如果侵犯了您的权利,请与我们联系,我们将在24小时内进行处理、任何非本站因素导致的法律后果,本站均不负任何责任。

联系QQ:835971066 | 邮箱:835971066#qq.com(#换成@)

Copyright © 2002-2020 脚本教程网 版权所有