C语言 实现归并排序算法

  • 更新时间:2022-06-26 08:08:07
  • 编辑:何安易
本站精选了一篇C语言相关的编程文章,网友班敏智根据主题投稿了本篇教程内容,涉及到归并排序算法、归并排序算法实例、归并排序算法详解、归并排序算法相关内容,已被771网友关注,下面的电子资料对本篇知识点有更加详尽的解释。

参考资料

正文内容

归并排序算法

C语言 实现归并排序算法

归并排序(Merge sort)是创建在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

一个归并排序的例子:对一个随机点的链表进行排序

算法描述

归并操作的过程如下:

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
  4. 重复步骤3直到某一指针到达序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

特点:归并排序是稳定的排序.即相等的元素的顺序不会改变,  速度仅次于快速排序,但较稳定。

归并操作

归并操作(merge),也叫归并算法,指的是将两个顺序序列合并成一个顺序序列的方法。

如:设有数列 [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;

算法实现

// Completed on 2014.10.11 17:20
// Language: C99
//
// 版权所有(C)codingwu  (mail: oskernel@126.com) 
// 博客地址:http://www.cnblogs.com/archimedes/
#include<stdio.h>
#include<stdlib.h>void merge_sort(int *list, const int first, const int last)
{
  int len= last-first+1; 
  int left_min,left_max;  //左半区域边界 
  int right_min,right_max; //右半区域边界 
  int index;
  int i;
  int *tmp;
  tmp = (int *)malloc(sizeof(int)*len);
  if( tmp == NULL || len <= 0 )
    return;
  
  for( i = 1; i < len; i *= 2 )
  {
    for( left_min = 0; left_min < len - i; left_min = right_max)
    {
      int j;
      right_min = left_max = left_min + i;
      right_max = left_max + i;
      j = left_min;
      if ( right_max > len )
        right_max = len;
      index = 0;
      while( left_min < left_max && right_min < right_max )
      {
        tmp[index++] = (list[left_min] > list[right_min] ? list[right_min++] : list[left_min++]);
      }
      while( left_min < left_max )
      {
        list[--right_min] = list[--left_max];
      }
      while( index > 0 )
      {
        list[--right_min] = tmp[--index];
      }
    }
  }
  free(tmp);
}
int main()
{
  int a[] = {288, 52, 123, 30, 212, 23, 10, 233};
  int n, mid;
  n = sizeof(a) / sizeof(a[0]);
  mid = n / 2;
  merge_sort(a, 0, n - 1);
  for(int k = 0; k < n; k++)
    printf("%d ", a[k]);
  printf("\n");
  return 0;
}

使用递归实现:

// Completed on 2014.10.11 18:20
// Language: C99
//
// 版权所有(C)codingwu  (mail: oskernel@126.com) 
// 博客地址:http://www.cnblogs.com/archimedes/
#include<stdio.h>
#include<stdlib.h>
void merge(int *array,const int first, const int mid, const int last)
{
  int i,index;
  int first1,last1;
  int first2,last2;
  int *tmp;
  tmp = (int *)malloc((last-first+1)*sizeof(int));
  if( tmp == NULL )
    return;
  first1 = first;
  last1 = mid;
  first2 = mid+1;
  last2 = last;
  index = 0;
  while( (first1 <= last1) && (first2 <= last2) )
  {
    if( array[first1] < array[first2] )
    {
      tmp[index++] = array[first1];
      first1++;
    }
    else{
      tmp[index++] = array[first2];
      first2++;
    }
  }
  while( first1 <= last1 )
  {
    tmp[index++] = array[first1++];
  }
  while( first2 <= last2 )
  {
    tmp[index++] = array[first2++];
  }
  for( i=0; i<(last-first+1); i++)
  {
    array[first+i] = tmp[i];
  }
  free(tmp);
}
void merge_sort(int *array, const int first, const int last)
{
  int mid = 0;
  if(first < last)
  {
    mid = (first + last) / 2;
    merge_sort(array, first, mid);
    merge_sort(array, mid + 1, last);
    merge(array, first, mid, last);
  }
}
int main()
{
  int a[] = {288, 52, 123, 30, 212, 23, 10, 233};
  int n, mid;
  n = sizeof(a) / sizeof(a[0]);
  mid = n / 2;
  merge_sort(a, 0, n - 1);
  for(int k = 0; k < n; k++)
    printf("%d ", a[k]);
  printf("\n");
  return 0;
}

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

C语言相关教程

  • VScode上配置 c语言环境的图文教程

    这篇文章主要介绍了配置VScode c语言环境,本文通过图文并茂的形式给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下

    发布时间:2022-04-16

  • C语言中指针 int *p=0;和int *p;*p=0;和”&“的关系和区别详解

    这篇文章主要介绍了C语言中指针 int *p=0;和int *p;*p=0;和”&“有什么关系和区别,本文给大家介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下

    发布时间:2022-04-13

  • c语言和python之间有什么区别

    c语言和python之间有什么区别

    为网友们分享了关于python的教程,c语言和python之间的主要区别是:Python是一种面向对象的解释型语言,通过缩进来表示语句体,在Python中每一条语句结尾后没有分号;C是一种面向过程的编译型语言,通过{}来表示语句体,C语言

    发布时间:2022-06-22

  • 关于python和c语言学哪个好

    现在很多外国的初学者都使用python作为编程语言,主要是python见效快,并且可以使用高级端口,c语言是比较低层的,一般不建议学习,学习起来也是比较枯燥。

    发布时间:2020-03-14

  • C语言扫雷游戏实例代码

    这篇文章主要为大家详细介绍了C语言代码实现扫雷游戏,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

    发布时间:2021-06-02

  • C语言文件操作总结

    本篇文章给大家通过代码示例讲述了C语言文件操作的相关知识点,对此有兴趣的朋友可以参考学习下。

    发布时间:2022-04-06

  • C语言原码、反码、补码和移码知识点总结

    这篇文章主要介绍了C语言基础 原码、反码、补码和移码详解的相关资料,需要的朋友可以参考下

    发布时间:2021-06-02

  • C语言数据输入与输出实例详解

    这篇文章主要介绍了C语言数据输入与输出实例详解的相关资料,需要的朋友可以参考下

    发布时间:2022-04-16

用户留言