數組歸並演算法

❶ 急求歸並排序演算法:將有序數組A[0, … , n]和B[0 , … , m]合並(C語言)

int guibing(int *a,int *b,int n,int m,int *s)
{
int i=0,j=0;

while(i<n&&j<m)
{
if(a[i]<b[j])
{
s[i+j]=a[i];
i++;
}
else
{
s[i+j]=b[j];
j++;
}
}
while(i<n)
{
s[i+j]=a[i];
i++;
}
while(j<m)
{
s[i+j]=b[j];
j++;
}

return 1;
}

❷ C語言技術題～整型數組的歸並排序～！特急！！！！！！

/*排序函數*/
void Sort( int *p,int n )
{
int i,j,temp;

for( i = 0; i < n; i++ )
{
for( j = i + 1; j < n; j++ )
{
if( *(p+i) < *(p+j) )
{
temp = *(p+i);
*(p+i) = *(p+j);
*(p+j) = temp;
}
}
}
}
/*連接兩個數組*/
void Link_data(int *a,int *b,int *c,int len_a,int len_b)
{
int i = 0,j = 0, k = 0;

while( i < len_a &&j < len_b )
{
/*如果A數組中的元素大，放進c中並且指針i向下移動，否則B數組中的元素放進C中，指針j向下移動*/
if( a[i] > b[j] )
{
c[k] = a[i];
k++;
i++;
}
else
{
c[k] = b[j];
j++;
k++;
}
}

/*如果指針i大於數組a的長度，則表示a已經讀完，則把b剩餘的放進c*/
if( i >= len_a )
{
for( ; j < len_b; j++)
{
c[k] =b[j];
k++;
}
}
/*如果指針j大於數組b的長度，則表示b已經讀完，則把a剩餘的放進c*/
if( j >= len_b )
{
for(;i < len_a; i++ )
{
c[k] = a[i];
k++;
}
}
}
main()
{
int a[5] = {1,70,3,4,10},
b[5] = {6,7,30,9,-1},
c[10];
clrscr();

Sort(a,5);
Sort(b,5);
Link_data(a,b,c,5,5);

for( i = 0; i < 10; i++ )
{
printf("%d ",c[i]);
}

}

❸ 求演算法。有兩個排序好的數組，比如啊a，b。把這兩個數組合並為1個數組，求出中間值。

好久沒寫java代碼了，下面的代碼相當於偽代碼，簡單描述一下演算法吧！
public int merge(int a[], int b[]){
int lengtha = a.length,lengthb = b.length;
int c[] = new array[lengtha + lengthb];
int x = lengtha + lengthb,y = 0;
i = 0;
j = 0;
while(y < x){
if(i < lengtha && j < lengthb){
if(a[i] <= b[j]){
c[y++] = a[i++];
}
else{
c[y++] = b[j++];
}
}
else if(i < lengtha){
c[y++] = a[i++];
}
else{
c[y++] = b[j++];
}
}
return c[y/2];
}

❹ 什麼叫歸並演算法

合並排序（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;
}

❺ 給解析一下這個數組的歸並排序演算法

len = 1 的第一輪歸並： 4 6 1 2 3 5
len = 2 的第二輪歸並： 1 2 4 6 3 5
len = 4 的第三輪歸並： 1 2 3 4 5 6

以上採用的是二路歸並，如果每一段的長度大於2*len，進行二路歸並，如果大於len小於2*len，也進行歸並。。如果小於len，那麼就直接傳遞進行下一輪的歸並

❻ 歸並排序演算法

兩種歸並排序演算法的實現：二路歸並排序和基本歸並排序（虛擬消除遞歸的二路歸並排序）
#define ARRAY_SIZE 1024

int B[1024]; //使用一個全局變數，避免歸並排序中每次都重新申請和釋放空間造成的開銷

template <typename T>
void Merge(T A[], int l, int m, int h)
{
int i = l;
int j = m+1;
int k = 0;

while(i<=m&&j<=h)
{
if(A[i]<A[j])
{
B[k++] = A[i];
i++;
}
else
{
B[k++] = A[j];
j++;
}
}

while(i<=m)
{
B[k++] = A[i++];
}

while(j<=h)
{
B[k++] = A[j++];
}

for(i=l; i<=h; i++)
{
A[i] = B[i-l];
}
}

//二路歸並排序的實現

template <typename T>
void MergeSort(T a[], int l, int h)
{
int m = (h+l)/2;
if(l>=h)
{
return;
}

if(l+1==h)
{
if(a[l]>a[h])
{
std::swap(a[l], a[h]);
}

return;
}

MergeSort(a, l, m);
MergeSort(a, m+1, h);
Merge(a, l, m, h);
}

//將a經過步長s歸並到b中，n表示數組的大小
template <typename T>
void Merge2(T a[], T b[], int s, int n)
{
int m = 0;

//從頭至尾按照步長s進行相鄰數據的合並
for(int i=0; i<n; i+=2*s)
{
int j = i; //合並的第一組數的起始位置
int k = i+s; //合並的第二組數的起始位置
int jE = i+s; //合並的第一組數的起始位置
int kE = i+2*s; //合並的第二組數的起始位置

while((j<jE)&&(k<kE)&&j<n && k<n)
{
if(a[j]<a[k])
{
b[m++] = a[j];
j++;
}
else
{
b[m++] = a[k];
k++;
}
}

while((j<jE)&&(j<n))
{
b[m++] = a[j++];
}

while((k<kE)&&(k<n))
{
b[m++] = a[k++];
}
}
}

//基本歸並排序，虛擬消除遞歸
template <typename T>
void MergeSort2(T a[], int n)
{
int s = 1; //merge 的步長
T* b = new T[n];

while(s<n)
{
Merge2(a, b, s, n); //由a合並到b
s += s;

Merge2(b, a, s, n); //由b合並到a
s += s;
}

delete[] b;
}

//使用如下代碼在VS2005中可以對兩種歸並排序進行性能比較，

//基本歸並排序的時間性能稍微好一點，基本歸並排序直接對數據按步長Merge，

//而二路歸並排序需要將數據先不斷的分層，到為一個或者兩個元素時再進行Merge

void main()
{
int * p = new int[ARRAY_SIZE];
int i = 0;

for(i=0; i<ARRAY_SIZE; i++)
{
*(p+i) = rand()%ARRAY_SIZE;
}
MergeSort(p, 0, ARRAY_SIZE-1);

for(i=0; i<ARRAY_SIZE; i++)
{
*(p+i) = rand()%ARRAY_SIZE;
}
MergeSort2(p, ARRAY_SIZE);

delete[] p;
}

❼ 如何將兩個隨機數組歸並為一從小到大排列的數組

合並後用排序演算法就可以了啊，排序演算法很多的，冒泡法，快速排序法等。

❽ 編寫程序:整型數組的歸並排序

這種題大致的框架給你，具體的你細想下
void fun(int a[],int b[],int c[])
{
int i=0,j=0,k=0;
while(a沒訪問結束&&b沒訪問結束)
{
if(a[i]<b[j])
{
c[k++]=a[i];
j++;
}
else
c[k++]=b[j];
i++
}
if(數組a未訪問完畢)
{
將數組a中的剩餘元素插入C
}
else if（b未訪問完）
{
將數組b中的元素插入C
}
}

❾ 在C語言的數組排序中,歸並法又稱什麼法

在數組中的良好秩序的開始：從小到大，或降序。然後這個數組被妥協，你想找到這個數字，比較大小，（例如，中間的數字：如果我長大了，我會和中間的數字，你正在尋找一些這樣的比較的數組，如果小，這個數字就是你想要找的絕對范圍在左側的中間，如果數量大，要找到絕對范圍的中間到右邊，然後是同樣的道理，慢慢慢慢縮小，誰知看遠）