|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
#include<stdio.h>
#include<stdlib.h>
#define MAX 10000
struct List
{
int data[MAX];
int length;
};
List list;
void init(List &list,int n);
void MergeSort(List &list);
void Merge(List &list,int a[],int L,int R);
void init(List &list,int n)
{
int i;
list.length=0;
printf("输入序列:");
for(i=0;i<n;i++)
{
scanf("%d",&list.data[i]);
}
}
void MergeSort(List &list)
{
int *a = (int *)malloc(list.length);
Merge(list,a,0,list.length-1);
free(a);
}
void Merge(List &list,int a[],int L,int R)
{
int mid=(L+R)/2;
int L1=L;
int R1=mid;
int L2=mid+1;
int R2=R;
int i=L;
Merge(list,a,L1,R1); //左侧分治
Merge(list,a,L2,R2); //右侧分治
while(L1<=R1&&L2<=R2)
{
a[i++]=list.data[L1]<list.data[L2]? list.data[L1++] : list.data[L2++];
}
while(L1<=R1)
{
a[i++]=list.data[L1++];
}
while(L2<=R2)
{
a[i++]=list.data[L2++];
}
for(i=L;i<=R;i++)
{
list.data[i]=a[i];
}
}
int main(void)
{
int n;
int i;
printf("输入整数个数:");
scanf("%d",&n);
init(list,n);
MergeSort(list);
printf("输出排序结果:");
for(i=0;i<n;i++)
{
printf("%d ",list.data[i]);
}
printf("\n");
return 0;
}
- #include<stdio.h>
- #include<stdlib.h>
- #define MAX 10000
- struct List
- {
- int data[MAX];
- int length;
- };
- List list;
- void init(List &list,int n);
- void MergeSort(List &list);
- void Sort(List &list,int L,int mid,int R);
- void init(List &list,int n)
- {
- int i;
-
- list.length=0;
-
- printf("输入序列:");
- for(i=0;i<n;i++)
- {
- scanf("%d",&list.data[i]);
- list.length++;
- }
- }
- void Merge(int A[], int left, int mid, int right)
- {
- int len = right - left + 1;
- int * temp = (int *)malloc(len);
- int index = 0;
- int i = left;
- int j = mid + 1;
-
- while (i <= mid && j <= right)
- {
- temp[index++] = A[i] <= A[j] ? A[i++] : A[j++];
- }
- while (i <= mid)
- {
- temp[index++] = A[i++];
- }
- while (j <= right)
- {
- temp[index++] = A[j++];
- }
- for (int k = 0; k < len; k++)
- {
- A[left++] = temp[k];
- }
-
- free(temp);
- }
- void MergeSort(int A[],int L,int R)
- {
- if(L>=R)
- {
- return ;
- }
-
- int mid=(L+R)/2;
-
- MergeSort(A,L,mid); //左侧分治
- MergeSort(A,mid+1,R); //右侧分治
- Merge(A,L,mid,R); //排序
- }
- int main(void)
- {
- int n;
- int i;
-
- printf("输入整数个数:");
- scanf("%d",&n);
-
- init(list,n);
- MergeSort(list.data,0,list.length-1);
-
- printf("输出排序结果:");
- for(i=0;i<n;i++)
- {
- printf("%d ",list.data[i]);
- }
-
- printf("\n");
-
- return 0;
- }
复制代码
|
|