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