{
int i
// 保证至少有两个元素
if(left <right)
{
i = (left+right)/2
mergeSort(a,left,i)
mergeSort(a,i+1,right)
merge(a,left,right)
}
}
void merge(int a[],int left,int right)
{
int begin1 = left
int mid = (left+right)/2
int begin2 = mid+1
int k=0
int newArrayLen = right-left+1
int *b = (int*)malloc(newArrayLen*sizeof(int))
while(begin1<=mid &&begin2<=right)
{
if(a[begin1]<=a[begin2])
b[k++] = a[begin1++]
else
b[k++] = a[begin2++]
}
while(begin1<=mid)
b[k++] = a[begin1++]
while(begin2<=right)
b[k++] = a[begin2++]
copyArray(b,a,newArrayLen,left)
free(b)
}
/**
* 复制数组
* source:源数组
* dest:目标数组
* len:源数组长度
* first:目标数组起始位置
*
*/
void copyArray(int source[], int dest[],int len,int first)
{
int i
int j=first
for(i=0i<leni++)
{
dest[j] = source[i]
j++
}
}
void mergeSortTest()
{
int a[] = {5, 18, 151, 138, 160, 63, 174, 169, 79, 200}
int len = sizeof(a)/sizeof(int)
showArray(a,len)
mergeSort(a,0,len-1)
showArray(a,len)
}
#include <stdio.h>
int main()
{int a[]={1,3,5,7,9},b[]={2,4,6,8},c[10]
int i,j,k,n1,n2,n3
i=j=k=0
n1=5
n2=4
n3=n1+n2
for(i<n1&&j<n2)
if(a[i]<b[j])c[k++]=a[i++]
else c[k++]=b[j++]
for(i<n1)c[k++]=a[i++]
for(j<n2)c[k++]=b[j++]
for(k=0k<n3k++)
printf("%d ",c[k])
printf("\n")
return 0
}
给你一个归并排序的具体算法和分析：两路归并排序算法思路:
①.
把n个记录看成n个长度为l的有序子表
②.
进行两两归并使记录关键字有序,得到n/2个长度为2的有序子表
③.
重复第②步直到所有记录归并成一个长度为n的有序表为止
具体算法:
//
归并操作
template
static
void
merge
(typearray[],
int
p,
int
q,
int
r){
int
i
,
k
int
begin1
,
end1
,
begin2
,
end2
int*
temp
=
(int*)malloc((r-p)*sizeof(int))
begin1
=
p
end1
=
q
begin2
=
q+1
end2
=
r
k
=
0
while
(begin1
<=
end1
&&
begin2
<=
end2){
if
(array[begin1]
<
array[begin2]){
temp[k]
=
array[begin1]
begin1
++
}
else{
temp[k]
=
array[begin2]
begin2
++
}
k
++
}
while
(begin1
<
end1)
temp[k++]
=
array[begin1++]
while
(begin2
<
end2)
temp[k++]
=
array[begin2++]
for
(i
=
0
i
<
(r-p)
i
++)
array[p+i]
=
temp
free(temp)
}
//--------------------------------------------------------------------------------
template
void
mergesort(typearray[],
unsigned
int
first,
unsigned
int
last){
int
mid
=
0
if
(first
<
last)
{
mid
=
(first+last)/2
mergesort
(array,
first,
mid)
mergesort
(array,
mid+1,
last)
merge
(array,
first,
mid,
last)
}
}
