C语言合并排序及实例代码
归并排序也称合并排序,其算法思想是将待排序序列分为两部分,依次对分得的两个部分再次使用归并排序,之后再对其进行合并。下面是小编分享的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
#include
#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
arr[low+i] = tmp[i];
free(tmp);
return;
}
void merge_sort(int arr[], unsigned int first, unsigned int last){
int mid = 0;
if(first
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 ("排序前");
for(i=0;i
printf("%d ",a[i]);
merge_sort(a,0,N-1); // 排序
printf ("排序后");
for(i=0;i
printf("%d ",a[i]); printf("");
system("pause");
return 0;
}
运行结果:
排序前
32 12 56 78 76 45 36
排序后
12 32 36 45 56 76 78
分析上面的运行结果,通过归并排序成功地实现了对给定序列的排序操作。接下来通过图来了解归并排序的具体操作流程。
在下图先对所要进行排序的序列进行分解,直到分为单个元素为止,然后将其进行两两合并。由于最终分解成单个元素,因此在合并的时候.将小数放在前面,大数放在后面,得到一个有序序列。接下来对两个相连的有序序列进行排序,先比较有序序列中的`第一个元素,将较小的元素放入临时数组中,接着将较小元素所在数组的下一个元素与另一个数组中的较小元素比较,同样将较小元素放入临时数组中,依次进行,直到两个数组的所有元素都放入临时数组中,最后再将临时数组的元素放入原始数组中的对应位置。
以上就是对合并排序的详细讲解,希望对你有帮助。
-
2017年C语言新增无纸化真题练习
C语言的应用范围广泛,具备很强的数据处理能力,不仅仅是在软件开发上,而且各类科研都需要用到C语言,适于编写系统软件,三维,二维图形和动画,具体应用比如单片机以及嵌入式系统开发。以下是小编为大家搜索整理的2017年C语言新增无纸化真题练习,希望能给大家带来帮助!更多...
-
C/C++变量在内存中的分布介绍
变量在内存地址的分布为:堆-栈-代码区-全局静态-常量数据。同一区域的各变量按声明的顺序在内存的中依次由低到高分配空间(只有未赋值的全局变量是个例外)。本文是本站小编搜索整理的关于C/C++变量在内存中的分布介绍,感兴趣的朋友一起学习吧!!想了解更多相关信息...
-
嵌入式C语言优化技巧
嵌入式系统是指完成一种或几种特定功能的计算机系统,具有自动化程度高,响应速度快等优点,目前已广泛应用于消费电子,工业控制等领域。嵌入式系统受其使用的硬件以及运行环境的限制,非常注重代码的时间和空间效率,因此选择一种合适的开发语言十分重要。下面是相关的知...
-
Mac系统怎样使用终端编写c语言程序
C语言是目前较为普遍的程序语言,它功能丰富、表达能力强、使用灵活方便、目标程序效率高,适合编制一般应用软件。下面是应届毕业生小编收集整理的Mac系统怎样使用终端编写c语言程序,希望对大家有帮助~~Mac系统使用终端编写c语言程序的'方法工具/原料Mac系统,终...