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

归并排序也称合并排序，其算法思想是将待排序序列分为两部分，依次对分得的两个部分再次使用归并排序，之后再对其进行合并。仅从算法思想上了解归并排序会觉得很抽象，接下来就以对序列A[0], A[l]…, A[n-1]进行升序排列来进行讲解，在此采用自顶向下的实现方法。

操作步骤如下：

(1)将所要进行的排序序列分为左右两个部分，如果要进行排序的序列的起始元素下标为first，最后一个元素的下标为last，那么左右两部分之间的临界点下标mid=(first+last)/2，这两部分分别是A[first … mid]和A[mid+1 … last]。

(2)将上面所分得的两部分序列继续按照步骤(1)继续进行划分，直到划分的区间长度为1。

(3)将划分结束后的序列进行归并排序，排序方法为对所分的n个子序列进行两两合并，得到n/2或n/2+l个含有两个元素的子序列，再对得到的子序列进行合并，直至得到一个长度为n的有序序列为止。

下面通过一段代码来看如何实现归并排序。

#include <stdio.h>
#include <stdlib.h>
#define N 7
void merge(int arr[], int low, int mid, int high){
 int i, k;
 int *tmp = (int *)malloc((high-low+1)*sizeof(int));
 //申请空间，使其大小为两个
 int left_low = low;
 int left_high = mid;
 int right_low = mid + 1;
 int right_high = high;
 for(k=0; left_low<=left_high && right_low<=right_high; k++){ // 比较两个指针所指向的元素
  if(arr[left_low]<=arr[right_low]){
   tmp[k] = arr[left_low++];
  }else{
   tmp[k] = arr[right_low++];
  }
 }
 if(left_low <= left_high){ //若第一个序列有剩余，直接复制出来粘到合并序列尾
 //memcpy(tmp+k, arr+left_low, (left_high-left_low+l)*sizeof(int));
 for(i=left_low;i<=left_high;i++)
  tmp[k++] = arr[i];
 }
 if(right_low <= right_high){
 //若第二个序列有剩余，直接复制出来粘到合并序列尾
 //memcpy(tmp+k, arr+right_low, (right_high-right_low+1)*sizeof(int));
  for(i=right_low; i<=right_high; i++)
   tmp[k++] = arr[i];
 }
 for(i=0; i<high-low+1; i++)
  arr[low+i] = tmp[i];
 free(tmp);
 return;
}
void merge_sort(int arr[], unsigned int first, unsigned int last){
 int mid = 0;
 if(first<last){
  mid = (first+last)/2; /* 注意防止溢出 */
  /*mid = first/2 + last/2;*/
  //mid = (first & last) + ((first ^ last) >> 1);
  merge_sort(arr, first, mid);
  merge_sort(arr, mid+1,last);
  merge(arr,first,mid,last);
 }
 return;
}
int main(){
 int i;
 int a[N]={32,12,56,78,76,45,36};
 printf ("排序前 \n");
 for(i=0;i<N;i++)
  printf("%d\t",a[i]);
 merge_sort(a,0,N-1); // 排序
 printf ("\n 排序后 \n");
 for(i=0;i<N;i++)
  printf("%d\t",a[i]); printf("\n");
 system("pause");
 return 0;
}

运行结果：

排序前

32    12    56    78    76    45    36

排序后

12    32    36    45    56    76    78

分析上面的运行结果，通过归并排序成功地实现了对给定序列的排序操作。接下来通过图来了解归并排序的具体操作流程。

在下图先对所要进行排序的序列进行分解，直到分为单个元素为止，然后将其进行两两合并。由于最终分解成单个元素，因此在合并的时候.将小数放在前面，大数放在后面，得到一个有序序列。接下来对两个相连的有序序列进行排序，先比较有序序列中的第一个元素，将较小的元素放入临时数组中，接着将较小元素所在数组的下一个元素与另一个数组中的较小元素比较，同样将较小元素放入临时数组中，依次进行，直到两个数组的所有元素都放入临时数组中，最后再将临时数组的元素放入原始数组中的对应位置。

以上就是对合并排序的详细讲解，希望对你有帮助。

赞 (0)

相关推荐

  • 详解C语言中的char数据类型及其与int类型的转换

    C语言中的char变量 char是C/C++整型数据中比较古怪的一个,其它的如int/long/short等不指定signed/unsigned时都默认是signed.虽然char在标准中是unsigned(因为char类型提出的初衷是用来表示ascii码,ascii码的范围是0~127),但实际情况中究竟是signed还是unsigned取决于编译器. 可通过下面程序判断编译器的默认char类型: void char_type() { char c=0xFF; if(c==-1) printf

  • C语言 数据类型详细介绍

    C语言 数据类型详细介绍

    C 数据类型 在 C 语言中,数据类型指的是用于声明不同类型的变量或函数的一个广泛的系统.变量的类型决定了变量存储占用的空间,以及如何解释存储的位模式. C 中的类型可分为以下几种: 序号 类型与描述 1 基本类型: 它们是算术类型,包括两种类型:整数类型和浮点类型. 2 枚举类型: 它们也是算术类型,被用来定义在程序中只能赋予其一定的离散整数值的变量. 3 void 类型: 类型说明符 void 表明没有可用的值. 4 派生类型: 它们包括:指针类型.数组类型.结构类型.共用体类型和函数类型.

  • 浅谈C语言编程中的布尔bool数据类型

    我们知道在C++里有专门的bool类型,用来表示真或假.但是在C语言里没有这样的类型(至少我是一直这么认为的),表达式的值0为假,非0为真.所以条件判断语句( if(-).while(-) )非常灵活,甚至一个指针类型都可以是条件表达式. 为了使程序更清晰,我们常常会给出如下的宏定义: typedef int BOOL; #define TRUE 1 #define FALSE 0 这是最常见的写法,能被任何C语言编译器认可. 今天我在一段程序里看见这么一行 #include ,这个陌生的头文件

  • C语言选择排序算法及实例代码

    选择排序是排序算法的一种,这里以从小到大排序为例进行讲解. 基本思想及举例说明 选择排序(从小到大)的基本思想是,首先,选出最小的数,放在第一个位置:然后,选出第二小的数,放在第二个位置:以此类推,直到所有的数从小到大排序. 在实现上,我们通常是先确定第i小的数所在的位置,然后,将其与第i个数进行交换. 下面,以对 3  2  4  1 进行选择排序说明排序过程,使用min_index 记录当前最小的数所在的位置. 第1轮 排序过程 (寻找第1小的数所在的位置) 3  2  4  1(最初, m

  • 分析C语言一个简单程序

    首先给大家一个简单的例子,让读者有个整体的认识,代码如下: #include <stdio.h> int main() { puts("我们"); return 0; } 函数的概念 先来看第4行代码,这行代码会在显示器上输出"我们".前面我们已经讲过,puts 后面要带( ),字符串也要放在( )中. 在C语言中,有的语句使用时不能带括号,有的语句必须带括号.带括号的称为函数(Function) . C语言提供了很多功能,例如输入输出.获得日期时间.文

  • C语言数据类型转换实例代码

    C语言数据类型转换实例代码

    数据类型转换就是将数据(变量.表达式的结果)从一种类型转换到另一种类型.例如,为了保存小数你可以将int类型的变量转换为double类型. 数据类型转换的一般格式为: (type_name) expression type_name为要转换到的数据类型,expression为表达式.例如: (float) a; //把a转换为实型 (int)(x+y); //把x+y的结果转换为整型 (float) 100; //将一个常量转换为实型 [示例]将整数转换为浮点数: #include <stdio

  • C语言二分查找算法及实现代码

    C语言二分查找算法及实现代码

    二分査找也称折半査找,其优点是查找速度快,缺点是要求所要査找的数据必须是有序序列.该算法的基本思想是将所要査找的序列的中间位置的数据与所要査找的元素进行比较,如果相等,则表示査找成功,否则将以该位置为基准将所要査找的序列分为左右两部分.接下来根据所要査找序列的升降序规律及中间元素与所查找元素的大小关系,来选择所要査找元素可能存在的那部分序列,对其采用同样的方法进行査找,直至能够确定所要查找的元素是否存在,具体的使用方法可通过下面的代码具体了解. #include <stdio.h> binar

  • 深入解析C语言中常数的数据类型

    废话不多说,上代码 复制代码 代码如下: //编译环境:codeblocks+gcc#include <stdio.h>#include <stdint.h>int Fun(){    uint64_t y;    uint32_t x1, x2; //y = 3000 * 24000000 / 1000;//常数默认作为32位数据,临时运算结果也是32位,溢出错误    //y = (uint64_t)3000 * (uint64_t)24000000 / 1000;//常数强制

  • C语言冒泡排序算实现代码

    冒泡排序是排序算法的一种,思路清晰,代码简洁,常被用在大学生计算机课程中. "冒泡"这个名字的由来是因为越大的元素会经由交换慢慢"浮"到数列的顶端,故名. 这里以从小到大排序为例进行讲解. 基本思想及举例说明 冒泡排序的基本思想就是不断比较相邻的两个数,让较大的元素不断地往后移.经过一轮比较,就选出最大的数:经过第2轮比较,就选出次大的数,以此类推. 下面以对 3  2  4  1 进行冒泡排序说明. 第一轮 排序过程 3  2  4  1    (最初) 2  3

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

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

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

  • c语言5个常用的排序算法实例代码

    1.插入排序 基本思想:插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置,直到全部插入完毕. void insertSort(vector<int>& nums) { int k = 0; for (int i = 0; i < nums.size(); ++i) { int temp = nums[i]; int j = i; for (; j > 0 && temp < nums[j-1]; --j) nums[j] =

  • Go语言实现遗传算法的实例代码

    在没介绍正文之前先给大家补充点go语言基本知识及实例. Go 语言教程 Go 是一个开源的编程语言,它能让构造简单.可靠且高效的软件变得容易. Go是从2007年末由Robert Griesemer, Rob Pike, Ken Thompson主持开发,后来还加入了Ian Lance Taylor, Russ Cox等人,并最终于2009年11月开源,在2012年早些时候发布了Go 1稳定版本.现在Go的开发已经是完全开放的,并且拥有一个活跃的社区. Go 语言特色 简洁.快速.安全 并行.有

  • iOS对数组进行排序的实例代码

    一,代码. - (void)viewDidLoad { [super viewDidLoad]; // Do any additional setup after loading the view, typically from a nib. //直接排序对象 NSSortDescriptor *descriptor = [NSSortDescriptor sortDescriptorWithKey:nil ascending:YES]; NSArray *descriptors = [NSAr

  • python 日期排序的实例代码

    问题1:如果日期中有千年以前的情况(没法用格式化函数),如('2010-11-23','1989-3-7','2010-1-5','978-12-1','2010-2-4')参照方法1 问题2:如果日期中没有千年以前的情况,做法就很多了.参照方法2和方法3 # -*- coding: utf-8 -*- import time from operator import itemgetter arr=('2010-11-23','1989-3-7','2010-1-5','978-12-1','2

  • python两个_多个字典合并相加的实例代码

    这只是符合比较正常的需求和场景. #一.适用合并两个字典(key不能相同否则会被覆盖),简单,好用. A = {'a': 11, 'b': 22} B = {'c': 48, 'd': 13} #update() 把字典B的键/值对更新到A里 A.update(B) print(A) #二.适用多种场合,多字典存在相同key需要合并相加的场景比较适用. def sum_dict(a,b): temp = dict() # python3,dict_keys类似set: | 并集 for key

  • C语言动态顺序表实例代码

    C语言动态顺序表实例代码

    目录 顺序表概念: 一.准备工作 二.顺序表的基本操作  1.顺序表的初始化函数 2.尾插函数(在尾部插入数据) 3.头插函数(在数组头部插入数据)  4.尾删函数 5.头删函数 6.在第pos的位置插入数据 7.删除第pos个位置的数据 8.修改第pos个位置的数据 9.查找函数. 10.销毁函数 11.打印函数 三.总代码: 顺序表概念:         顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构.一般情况下用数组存储.在数组上完成数据的增删查改. 代码解析: 一.准备工

  • C语言打印各种图案实例代码

    1.线段图案 #include<stdio.h> int main() { int a = 0; while(~scanf("%d",&a)) { int i = 0; for(i=0;i<a;i++) { printf("*"); } printf("\n"); } return 0; } 2.正方形图案 #include<stdio.h> int main() { int a = 0; while(~sc

  • C语言实现三子棋实例代码

    我是半自主的完成了这个程序,看了B站鹏哥视频并仔细思索后才做出来的,我没有完全采用他的方法,导致程序还有一些不足之处,还请各位大佬指出. 首先,我将该程序的实现分为3个板块,main,game.h,和game.c; 代码如下: #define _CRT_SECURE_NO_WARNINGS #include"game.h" void menu() { printf("****************************************\n"); prin

  • go语言睡眠排序算法实例分析

    本文实例讲述了go语言睡眠排序算法.分享给大家供大家参考.具体分析如下: 睡眠排序算法是一个天才程序员发明的,想法很简单,就是针对数组里的不同的数开多个线程,每个线程根据数的大小睡眠,自然睡的时间越长的,数越大,哈哈,搞笑吧,这种算法看起来很荒唐,但实际上很天才,它可以充分利用多核cpu进行计算. 复制代码 代码如下: package main import (     "fmt"     "time" ) func main() {     tab := []in

随机推荐