Question

求救！！求数据结构课程设计全文！！

我们正在做数据结构（C语言版）的课程设计小弟我平日学艺不精望各位大大救我一命！！！
用两路归并算法，实现N个无素的排序

Answer 1

合并排序（MERGE SORT）是又一类不同的排序方法，合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列，因此它又叫归并算法。它的基本思想就是假设数组A有N个元素，那么可以看成数组A是又N个有序的子序列组成，每个子序列的长度为1，然后再两两合并，得到了一个 N/2 个长度为2或1的有序子序列，再两两合并，如此重复，值得得到一个长度为N的有序数据序列为止，这种排序方法称为2—路合并排序。 例如数组A有7个数据，分别是： 49 38 65 97 76 13 27，那么采用归并排序算法的操作过程如图7所示： 初始值 [49] [38] [65] [97] [76] [13] [27] 看成由长度为1的7个子序列组成 第一次合并之后 [38 49] [65 97] [13 76] [27] 看成由长度为1或2的4个子序列组成 第二次合并之后 [38 49 65 97] [13 27 76] 看成由长度为4或3的2个子序列组成 第三次合并之后 [13 27 38 49 65 76 97] 合并算法的核心操作就是将一维数组中前后相邻的两个两个有序序列合并成一个有序序列。合并算法也可以采用递归算法来实现，形式上较为简单,但实用性很差。合并算法的合并次数是一个非常重要的量,根据计算当数组中有3到4个元素时,合并次数是2次,当有5到8个元素时,合并次数是3次,当有9到16个元素时,合并次数是4次，按照这一规律,当有N个子序列时可以推断出合并的次数是X(2 >=N,符合此条件的最小那个X)。 其时间复杂度为：O(nlogn).所需辅助存储空间为：O(n)归并算法如下：long merge(long *A,long p,long q,long r) { long n1,n2,i,j,k; long *L,*R; n1=q-p+1; n2=r-q; L=(long *)malloc((n1+2)*sizeof(long)); R=(long *)malloc((n2+2)*sizeof(long)); for(i=1;i<=n1;i++) L=A[p+i-1]; for(j=1;j<=n2;j++) R[j]=A[q+j]; L[n1+1]=R[n2+1]=RAND_MAX; i=j=1; for(k=p;k<=r;k++) { if(L<=R[j]) { A[k]=L; i++; } else { A[k]=R[j]; j++; } } free(L); free(R); return 0; } long mergesort(long *A,long p,long r) { long q; if(p<r) { q=(p+r)/2; mergesort(A,p,q); mergesort(A,q+1,r); merge(A,p,q,r); } return 0; }

Answer 2

#include<iostream>
#include<ctime>
#include<cstdlib>
using namespace std;
//合并两个有序的
//a_temp其实就是一个暂时储存的，其实可以动态申请
void for_one(int a[],int a_temp[],int left,int right,int middle)//没必要传middle 能算出来
{
for(int i=left;i<=right;i++)
a_temp[i]=a[i];
int index1=left;
int index2=middle+1;
int index=left;
while(index1<=middle&&index2<=right)
{
a[index]=a_temp[index1]>a_temp[index2]?a_temp[index2]:a_temp[index1];
index++;
a_temp[index1]>a_temp[index2]?index2++:index1++;
}
while(index1<=middle)
{
a[index]=a_temp[index1];
index++;
index1++;
}
while(index2<right)
{
a[index]=a_temp[index2];
index++;
index2++;
}
}
void all_for_one(int a[],int a_temp[],int left,int right)//归并排序
{
int middle=(left+right)/2;
if(left!=right)
{
all_for_one(a,a_temp,left,middle);
all_for_one(a,a_temp,middle+1,right);
for_one(a,a_temp,left,right,middle);
}
}
//text 随机生成10个数
int main()
{
srand(10);
int a[10];
int a_temp[10];
for(int i=0;i<10;i++)
{
a[i]=rand()%100;
//cout<<a[i]<<endl;
}
all_for_one(a,a_temp,0,9);
for(i=0;i<10;i++)
cout<<a[i]<<endl;
return 0;
}