首页 > 代码库 > 数据结构之归并排序

数据结构之归并排序

2024-07-15 06:47:08   216人阅读

归并排序Merging Sort,将两个或两个以上的有序表组合成一个新表。

1.基本思想

假设初始化系列含有n个记录，则可以看出n个有序的子序列，每一个子序列的长为1，然后两两归并，得到【n/2】个长度为1或2的子序列，再两两归并……如此重复，知道最后得到一个长度为n的有序序列位置，这种排序方法称为2-路归并排序

2.归并排序代码

main.cpp

  1 #include <stdio.h>  2 #include <stdlib.h>  3 #include <time.h>  4 #define MAXSIZE 100000000  5 #define INCREMENTNUM 200000  6 #define EQ(a,b) ((a)==(b))  7 typedef struct List{  8     int*elem;  9     int length; 10     int size; 11 }List; 12  13 void initList(List &list) 14 { 15     list.elem=(int*)malloc(sizeof(int)*(MAXSIZE+1)); 16     if(!list.elem){ 17          printf("%s\n","初始化失败"); 18         exit(0); 19     } 20     list.length=0; 21     list.size=MAXSIZE; 22     printf("%s\n","初始化成功"); 23 } 24  25 void insert(List &list ,int value) 26 { 27     if(list.length>=list.size){ 28         list.elem=(int*)realloc(list.elem,sizeof(int)*(list.length+INCREMENTNUM)); 29         if(!list.elem){ 30          printf("%s\n","内存重新分配失败"); 31         exit(0); 32         } 33         printf("%s\n","内存重新分配成功"); 34     list.size+=INCREMENTNUM; 35     } 36     list.elem[++list.length]=value; //第一从1开始 37     //printf("%d%s  位置：%d\n",value,"\t插入成功",list.length); 38 } 39  40  41 void printList(List list) 42 { 43     //printf("共%d数据\n",list.length); 44     int i; 45     for(i=1;i<=list.length;i++){ 46         printf("%d\t",list.elem[i]); 47     } 48     printf("\n"); 49  50 } 51 //归并 52 void Merge(List L1,List &L2,int i,int m,int n) 53 { 54     int j; 55     int k; 56     for(j=m+1,k=i;j<=n&&i<=m;++k) 57     { 58         if(L1.elem[i]<L1.elem[j]) L2.elem[k]=L1.elem[i++]; 59         else  L2.elem[k]=L1.elem[j++]; 60     } 61     if(i<=m) 62     { 63         while(i<=m){ 64             L2.elem[k++]=L1.elem[i++]; 65         } 66     } 67     if(j<=n) 68     { 69         while(j<=n){ 70             L2.elem[k++]=L1.elem[j++]; 71         } 72     } 73 } 74 void MSort(List L1,List &L2,int s,int t) 75 { 76     if(s==t) L2.elem=L1.elem; 77     else 78     { 79         List L3; 80         L3.elem=(int*)malloc(sizeof(int)*(t-s+1)); 81         int m=(s+t)/2; 82         MSort(L1,L3,s,m); 83         MSort(L1,L3,m+1,t); 84         Merge(L3,L2,s,m,t); 85     } 86  87 } 88 void MergeSort(List &L) 89 { 90     MSort(L,L,1,L.length); 91 } 92  93  94 int main() 95 { 96  97     List list; 98     initList(list); 99     insert(list,49);insert(list,38);insert(list,65);insert(list,97);insert(list,76);100     insert(list,13);insert(list,27);insert(list,49);101     printList(list);102     MergeSort(list);103     printf("排序后\n");104     printList(list);105     return 0;106 }

3.归并排序性能

实现归并排序需要和待排序记录一样的辅助空间O(n),其时间复杂度O(nlogn),通过递归形式的算法在形式上很简洁，但实用性很差，很少利用2路归并排序进行内部排序。


联系
我们