首页 > 代码库 > C语言归并排序
C语言归并排序
这篇文章是学习了小甲鱼-数据结构与算法结合自考教材编写出的代码，希望自己逐渐在算法造诣上能更上一层楼。
归并排序（递归实现）
“归并”一词在中文含义中就是合并的意思，而在数据结构中的定义是将两个或者两个以上的有序表组合成一个新的有序表，就叫归并。
归并排序（Merge Sort）就是利用归并的思想实现的排序方法。它的原理是假设初始序列有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到⌈n/2⌉个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。
#include <stdio.h>#define MAXSIZE 10// 递归的方式实现归并排序// 实现归并，并把结果存放到list1void merging(int *list1, int list1_size, int *list2, int list2_size){ int i,j,k, m; int temp[MAXSIZE]; i = j = k = 0; while(i < list1_size && j < list2_size) { if(list1[i] < list2[j]) { temp[k] = list1[i]; k++; i++; } else { temp[k++] = list2[j++]; } } while(i < list1_size) { temp[k++] = list1[i++]; } while(j < list2_size) { temp[k++] = list2[j++]; } for(m = 0;m < (list1_size + list2_size);m++) { list1[m] = temp[m]; }}void MergeSort(int k[], int n){ if(n > 1) { /* *list1是左半部分，list2是右半部分 */ int *list1 = k; int list1_size = n/2; int *list2 = k + list1_size; int list2_size = n - list1_size; MergeSort(list1, list1_size); MergeSort(list2, list2_size); // 把两个合在一起 merging(list1, list1_size, list2, list2_size); }}int main(){ int i, a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8}; MergeSort(a, 10); printf("排序后的结果是："); for(i = 0;i < 10;i++) { printf("%d", a[i]); } printf("\n\n"); return 0;}
C语言归并排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。