1. 为什么合并排序是思想是基于比较类排序里面最快的，它成功的地方在哪儿
合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。合并排序也叫归并排序。
2. 用以下算法把两个有序表合成一个有序表!高手进！！急求！！！
class Program
{
static void Main(string[] args)
{
var fileNames = Directory.GetFiles("D:\\TestFiles", "*.txt");//指向存放txt文件的目录
List<StreamReader> readers = new List<StreamReader>();
var resultFileContents = new List<string>();
foreach (var fileName in fileNames)
{
readers.Add(File.OpenText(fileName));
}
var itemsToCompare = new List<string>();
var firstRead = true;
var indexOfReaderToMove = -1; ;
while (!AllToEnd(readers))
{
if (firstRead)//假设所有文件都至少有一行
{
foreach (var reader in readers)
{
itemsToCompare.Add(reader.ReadLine());
}
firstRead = false;
}
else
{
if (indexOfReaderToMove >= 0)
{
if (!readers[indexOfReaderToMove].EndOfStream)
{
itemsToCompare[indexOfReaderToMove] = readers[indexOfReaderToMove].ReadLine();
}
else
{
itemsToCompare[indexOfReaderToMove] = string.Empty;
}
}
}
var max = 0;
for (var i = 0; i < itemsToCompare.Count; i++)
{
var segments = itemsToCompare[i].Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);
if (segments.Length == 2 && int.Parse(segments[1]) > max)
{
indexOfReaderToMove = i;
max = int.Parse(segments[1]);
}
}
resultFileContents.Add(itemsToCompare[indexOfReaderToMove]);
}
//itemsToCompare可能还有剩余内容
while (itemsToCompare.Count > 0)
{
var max = 0;
var index = -1;
for (var i = 0; i < itemsToCompare.Count; i++)
{
var segments = itemsToCompare[i].Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);
if (segments.Length == 2 && int.Parse(segments[1]) > max)
{
max = int.Parse(segments[1]);
index = i;
}
}
if (index >= 0)
{
resultFileContents.Add(itemsToCompare[index]);
itemsToCompare.RemoveAt(index);
}
}
WriteToFile(resultFileContents, "test1.txt");
}
private static bool AllToEnd(List<StreamReader> readers)
{
var result = false;
foreach (var reader in readers)
{
result = reader.EndOfStream;
if (result)
{
continue;
}
else
{
break;
}
}
return result;
}
private static void WriteToFile(List<string> fileContents, string fileName)
{
using (var writer = File.CreateText(fileName))
{
foreach (var fileContnet in fileContents)
{
writer.WriteLine(fileContnet);
}
}
}
}
3. 设计两个有序单链表的合并排序算法
方法一:依次取链表2的节点,和链表1中的节点比较,找好位置之后插入到链表1中,然后两个链表指针各加一
方法二:另外建一个空链表,然后分别取两个链表的节点,按照顺序,放入空链表中
方法三:两个链表先连接然后排序(效率最低的)
4. 怎么将两个顺序存储的有序表合并成一个有序表
具体代码如下：
#include<stdio.h>
#include<stdlib.h>
#define MAX 40
typedef struct
{
int data[MAX];
int length;
}LinkList;
void Initial_List(LinkList * &l,int n)//初始化顺序表
{
int i=0;
l=(LinkList *)malloc(sizeof(LinkList));
l->length = 0;
for(;i<n;i++)
scanf("%d",l->data+i);
l->length = n;
}
void Link(LinkList *l1,LinkList *l2,LinkList * &l3)//连接顺序表
{
int i,j;
l3=(LinkList *)malloc(sizeof(LinkList));
l3->length = l1->length + l2->length;
for(i=0;i<l3->length;i++)
{
if(i<l1->length)
{
l3->data[i] = l1->data[i];
}
else
{
l3->data[i] = l2->data[i%(l1->length)];
}
}
for(i=0;i<l3->length;i++)
{
for(j=i+1;j<l3->length;j++)
{
if(l3->data[i]>l3->data[j])
{
int temp=l3->data[i];
l3->data[i]=l3->data[j];
l3->data[j]=temp;
}
}
}
}
void Disp_List(LinkList *l)
{
int i=0;
printf("output: ");
for(;i<l->length;i++)
printf("%d ",l->data[i]);
printf(" ");
}
int main()
{
LinkList *l1,*l2,*l3;
int n;
printf("请输入第一个序列的元素个数: ");
scanf("%d",&n);
printf("请输入第一个序列的所有元素: ");
Initial_List(l1,n);
printf("请输入第二个序列的元素个数: ");
scanf("%d",&n);
printf("请输入第二个序列的所有元素: ");
Initial_List(l2,n);
Link(l1,l2,l3);
Disp_List(l3);
return 0;
}
5. 用C语言编写算法实现将两个递增顺序表合并为一个递增顺序表
1.最容易的办法就是把两个表保存在一个新的表里，然后冒泡排序（就是这么暴力。）
2.不过这个问题用指针实现最方便了。
两个指针分别指着两个递增表：比较指针所指的值大小，将小的那个保存在新的表里，然后将小的那个指针往前走一步。再比较，再保存，再走....直到其中一个表走完，把另一个表剩下的数接在后面。
这样做的好处是原有的两个表的内容不会被修改。因为结果是保存在新的表里的，但是消耗内存。
3.插入排序，同样使用指针比较，把一个表里的数据插到另一个表里。这样省内存，但是被插入的这个表原有的数据就没咯。
6. （C语言数据结构） 设计两个有序顺序表的合并排序算法。
#include
#include
typedef
struct
node//定义结构体
{
int
score;
struct
node
*next;
}node;
node
*create(int
n)//创建链表
{
node
*head,*tail,*p;
head=tail=null;
int
i;
for(i=1;i<=n;i++)
{
p=(node
*)malloc(sizeof(node));
p->next=null;
printf("please
input
%d
score:",i);
scanf("%d",&p->score);
if(head==null)
head=tail=p;
else
{
tail->next=p;
tail=p;
}
}
return
head;
}
node
*range(node
*head)//排序
{
node
*p,*q;
int
score,i,n=0;
p=head;
while(p)
{
n++;
p=p->next;
}
for
(i=0;i
next!=null)//内循环
{
q=p->next;
if
(p->score>q->score)//值交换
{
score=p->score;
p->score=q->score;
q->score=score;
}
p=q;
}
}
return
head;
}
node
*connect(node
*head1,node
*head2)//合并
{
node
*p;
p=head1;
while(p->next!=null)
p=p->next;
p->next=head2;
return
head1;
}
void
output(node
*head)//输出
{
node
*p;
p=head;
while(p)
{
printf("%d
",p->score);
p=p->next;
}
printf("\n");
}
int
main()
{
node
*head,*hea1,*head2;
int
n1,n2;
printf("please
input
a
n1:");//第一个链表的成绩个数
scanf("%d",&n1);
hea1=create(n1);
printf("第一个链表的成绩:");
output(hea1);
printf("please
input
a
n2:");//第二个链表的成绩个数
scanf("%d",&n2);
head2=create(n2);
printf("第二个链表的成绩:");
output(head2);
head=connect(hea1,head2);
head=range(head);
printf("合并后，并排好序:");
output(head);
return
0;
}
7. 写一个软件工程数据结构合并两个顺序表的算法（看补充）
（1）设计一个算法将此两个线性表合并成一个，仍是数据由小到大排列的线性表，存储到另一个顺序表C中
（2）如果顺序表B的大小为（m+n）个单元，是否可以不利用顺序表C而将合并成的线性表存放于顺序表B中？
（3）设顺序表A有m+n个元素，且前m个有序，后n个有序，设计一个算法，使得整个顺序表有序。
8. 编写一个用顺序存储结构实现将两个有序表合成一个有序表的算法
用数组写了个思路，如果你们要求用链表的话改一下就可以了：
/*
把num1 num2 合并，输出到num_merge
*/
void merge(int num1[],int num2[],int num_merge[]){
int length1 = sizeof(num1)/sizeof(int);
int length2 = sizeof(num2)/sizeof(int);
int i = 0,j = 0,length_merge = 0;
while(length_merge < length1 && i< length2){
if(num1[i]<num2[j]){
num_merge[length_merge++] = num1[i++];
}else if(num1[i]>num2[j]){
num_merge[length_merge++] = num2[j++];
}else{
num_merge[length_merge++] = num1[i++];
j++;
}
}
while(length_merge < length1){
num_merge[length_merge++] = num1[i++];
}
while(length_merge < length2){
num_merge[length_merge++] = num2[j++];
}
}
9. 请用算法写出两个有序表合并成一个有序线性表(用C语言
#include "stdio.h" main() { int a,b,c,i,j,k,low,high,mid; int la[50]; int lb[50]; int lc[50]; printf("Please input the width of la,lb,lc:\n"); printf("Input here:"); scanf("%d,%d,%d",&a,&b,&c); printf("a=%d,b=%d,c=%d\n",a,b,c); if (a+b>c) printf("lc overflow,operation halt!\n"); else { printf("Input la:"); for(i=1;i<=a;++i) { scanf("%d",&la[i]); la[0]=la[i]; low=1; high=i; while(low<=high) { mid=(low+high)/2; if(la[0]=low;j--) la[j+1]=la[j]; la[low]=la[0]; } printf("\n"); printf("Input lb:"); for(i=1;i<=b;++i) { scanf("%d",&lb[i]); lb[0]=lb[i]; low=1; high=i; while(low<=high) { mid=(low+high)/2; if(lb[0]=low;j--) lb[j+1]=lb[j]; lb[low]=lb[0]; } printf("\n"); printf("la is:"); for (i=1;i<=a;i++) printf("%d ",la[i]); printf("\n"); printf("lb is:"); for (j=1;j<=b;j++) printf("%d ",lb[j]); i=1;j=1;k=0; while (i<=a && j<=b) if (la[i]>lb[j]) { lc[k]=lb[j];k++;j++;} else { lc[k]=la[i];k++;i++;} while (i<=a) {lc[k]=la[i];k++;i++;} while (j<=b) {lc[k]=lb[j];k++;j++;} printf("\n"); printf("lc is:"); for (i=0;i } getch(); } 把la,lb,lc分别换一下就OK了
希望采纳
10. 试写一个算法，将两个有序线性表合并成一个有序线性表。
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)
{
//已知单链线性表La和Lb的元素按非递减排列
//归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列
AH=La;BH=Lb;CH=Lc;
pa=AH_next;pb=BH_next;
CH=pc=AH;//用La的头结点作为Lc的头结点
while（pa&&pb）
{
if（pa->data<=pb->data){
pc-<next=pa;pc=pa;pa=pa->next;
}
elsr {pc->next=pb;pc=pb;pb=pb->next;}
}
pc->next=pa?pa:pb;//插入剩余段
free（BH）；//释放Lb的头结点
}//MergeList_L