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

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

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

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

时间: 2016-07-15

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

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

分析C语言一个简单程序

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

深入解析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语言选择排序算法及实例代码

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

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语言二分查找算法及实现代码

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

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

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

详解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语言中Char型指针数组与字符数组的区别

详解C语言中Char型指针数组与字符数组的区别 1.char 类型的指针数组:每个元素都指向一个字符串,指向可以改变 char *name[3] = { "abc", "def", "gbk" }; for(int i = 0 ; i < strlen(name); i ++){ printf("%s\n", *(name+i)); //printf("%s\n", name[i]); } //指向改

详解 Go 语言中 Map 类型和 Slice 类型的传递

Map 类型 先看例子 m1: func main() { m := make(map[int]int) mdMap(m) fmt.Println(m) } func mdMap(m map[int]int) { m[1] = 100 m[2] = 200 } 结果是 map[2:200 1:100] 我们再修改如下 m2: func main() { var m map[int]int mdMap(m) fmt.Println(m) } func mdMap(m map[int]int) {

详解C语言中return与exit的区别

详解C语言中return与exit的区别 1,exit用于在程序运行的过程中随时结束程序,exit的参数是返回给OS的.main函数结束时也会隐式地调用exit函数.exit函数运行时首先会执行由atexit()函数登记的函数,然后会做一些自身的清理工作,同时刷新所有输出流.关闭所有打开的流并且关闭通过标准I/O函数tmpfile()创建的临时文件.exit是结束一个进程,它将删除进程使用的内存空间,同时把错误信息返回父进程,而return是返回函数值并退出函数 2,return是语言级别的,它

详解Go语言中for range的&quot;坑&quot;

前言 Go 中的for range组合可以和方便的实现对一个数组或切片进行遍历,但是在某些情况下使用for range时很可能就会被"坑",下面用一段代码来模拟下: func main() { arr1 := []int{1, 2, 3} arr2 := make([]*int, len(arr1)) for i, v := range arr1 { arr2[i] = &v } for _, v := range arr2 { fmt.Println(*v) } } 代码解析

详解C语言中rand函数的使用

前言 我们在编程实现算法的过程中,往往需要使用到随机数.由于计算机是一台以逻辑为基础的机器,没法做到真正的随机(大概量子计算机可以?).所以计算机生成的是伪随机数,供我们使用. 我们使用C语言的rand函数,生成的也是伪随机数. c语言之rand函数的使用 1.写入头文件 #include <stdlib.h> #include <stdio.h> #include <time.h> 2.变量的定义 void main( void ) { int i,k; 3.sran

详解C语言中printf输出的相关函数

C语言printf()函数:格式化输出函数 printf()函数是最常用的格式化输出函数,其原型为: int printf( char * format, ... ); printf()会根据参数 format 字符串来转换并格式化数据,然后将结果输出到标准输出设备(显示器),直到出现字符串结束('\0')为止. 参数 format 字符串可包含下列三种字符类型: 一般文本,将会直接输出 ASCII 控制字符,如\t.\n 等有特定含义 格式转换字符 格式转换为一个百分比符号(%)及其后的格式字

详解C语言中的memset()函数

C语言memset()函数:将内存的前n个字节设置为特定的值 头文件: #include <string.h> memset() 函数用来将指定内存的前n个字节设置为特定的值,其原型为: void * memset( void * ptr, int value, size_t num ); 参数说明: ptr 为要操作的内存的指针. value 为要设置的值.你既可以向 value 传递 int 类型的值,也可以传递 char 类型的值,int 和 char 可以根据 ASCII 码相互转换.

详解C语言中strcpy()函数与strncpy()函数的使用

C语言strcpy()函数:复制字符串 头文件:#include <string.h> 定义函数: char *strcpy(char *dest, const char *src); 函数说明:strcpy()会将参数src 字符串拷贝至参数dest 所指的地址. 返回值:返回参数dest 的字符串起始地址. 附加说明:如果参数 dest 所指的内存空间不够大,可能会造成缓冲溢出(buffer Overflow)的错误情况,在编写程序时请特别留意,或者用strncpy()来取代. 范例 #i

详解C语言中scanf函数使用的一些注意点

 (一)基本介绍 Scanf是系统自带的函数,声明包含在stdio.h文件中,因此要是有该函数,必须加载#include<stdio.h>头文件.当执行到scanf函数时,程序就暂停等待用户输入,该函数只接受变量的地址,格式为&变量名.是一个阻塞式的函数,2用户输入完毕后,则将值赋值给变量,至此函数调用完毕.敲回车键告知计算机键入完毕. (二)使用注意 ①. 使用scanf函数输入一个字符变量.Char a; scanf("%c",&a); ②. 同时输入多