歸並排序c語言_C語言歸並排序的完整代碼

1. 歸並排序c語言版

#include <stdio.h>
void merge(int r[], int s[], int x1, int x2, int x3) /*實現一次歸並排序函數*/
{
int i, j, k;
i = x1; /*第一部分的開始位置*/
j = x2 + 1; /*第二部分的開始位置*/
k = x1;
while ((i <= x2) && (j <= x3))
/*當i和j都在兩個要合並的部分中*/
if (r[i] <= r[j])
/*篩選兩部分中較小的元素放到數組s中*/
{
s[k] = r[i];
i++;
k++;
}
else
{
s[k] = r[j];
j++;
k++;
}
while (i <= x2)
/*將x1~x2范圍內的未比較的數順次加到數組r中*/
s[k++] = r[i++];
while (j <= x3)
/*將x2+1~x3范圍內的未比較的數順次加到數組r中*/
s[k++] = r[j++];
}
void merge_sort(int r[], int s[], int m, int n)
{
int p;
int t[20];
if (m == n)
s[m] = r[m];
else
{
p = (m + n) / 2;
merge_sort(r, t, m, p);
/*遞歸調用merge_sort函數將r[m]~r[p]歸並成有序的t[m]~t[p]*/
merge_sort(r, t, p + 1, n); /*遞歸調用merge_sort函數將r[p
+1]~r[n]歸並成有序的t[p+1]~t[n]*/
merge(t, s, m, p, n); /*調用函數將前兩部分歸並到s[m]~s[n]*/
}
}
main()
{
int a[11];
int i;
printf("please input 10 numbers:\n");
for (i = 1; i <= 10; i++)
scanf("%d", &a[i]);
/*從鍵盤中輸入10個數*/
merge_sort(a, a, 1, 10); /*調用merge_sort函數進行歸並排序*/
printf("the sorted numbers:\n");
for (i = 1; i <= 10; i++)
printf("%5d", a[i]);
/*將排序後的結構輸出*/
}

2. C語言歸並排序的完整代碼

#include<stdio.h>
voidmain()
{
inti,j,k,n=4,a[9]={1,3,5,7,9},b[]={2,4,6,8};
for(i=0;i<4;i++)
for(j=0;j<n+1;j++)
{
if(b[i]<a[j])
{
for(k=++n;k>j;k--)
a[k]=a[k-1];
a[j]=b[i];
break;
}
}
for(i=0;i<9;i++)
printf("%d",a[i]);
}

3. 求大神解釋下二路歸並排序法，C語言。

#include <stdio.h>
#include<malloc.h>
void merge(int *a, int beg, int mid, int end)// 合並子序列
{
int i=beg, j=mid+1, cnt=0;
int *a1;
a1=(int*)malloc((end-beg+1)*sizeof(int));

while(i<=mid && j<=end)
{
a1[cnt++]=a[i]<=a[j]? a[i++]:a[j++];
}
while(i<=mid)
{
a1[cnt++]=a[i++];
}
while(j<=end)
{
a1[cnt++]=a[j++];
}
for(cnt=0, i=beg; i<=end; cnt++,i++)
{
a[i]=a1[cnt];
}

}
void merge_sort(int*a, int beg, int end)//二路歸並排序
{
int mid=0;
if(beg<end)
{
mid=(beg+end)/2;//左右兩部分分解
merge_sort(a, beg, mid);//左半部分排序
merge_sort(a, mid+1, end);//右半部分排序
merge(a, beg, mid, end);//左右兩部分合並
}
}

int main(void)
{
int a[10]={12,54,14,25,21,87,48,1,547,12};

int i=0,j=0,k=0;
for(i=0;i<10;i++)
{
printf("%4d",a[i]);
}
putchar('\n');
merge_sort(a, 0, 9);
for(i=0;i<10;i++)
{
printf("%4d",a[i]);
}
putchar('\n');

}

4. c語言歸並排序。。。。。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void Merge(int *R,int low,int m,int high)
{
int i=low,j=m+1,p=0;
int *R1;
R1=(int *)malloc((high-low+1)*sizeof(int));
if(!R1)
return;
while(i<=m&&j<=high)
R1[p++]=(R[i]<=R[j])?R[i++]:R[j++];
while(i<=m)
R1[p++]=R[i++];
while(j<=high)
R1[p++]=R[j++];
for(p=0,i=low;i<=high;p++,i++)
R[i]=R1[p];
}
void MergeSort(int R[],int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
MergeSort(R,low,mid);
MergeSort(R,mid+1,high);
Merge(R,low,mid,high);
}
}
int main(void)
{
int i;
int a[10]=;
int low=0,high=9;
srand( (unsigned int)time(NULL) );
for (i = 0; i < 10; i++)
{
a[i] = rand() % 100;
}
MergeSort(a,low,high);
for(i=low;i<=high;i++)
printf("%d ",a[i]);
printf("\n");
return 0;
}

5. c語言歸並排序

直接上源碼，僅供參考：
#include<stdio.h>

// 一個遞歸函數
void mergesort(int *num,int start,int end);
// 這個函數用來將兩個排好序的數組進行合並
void merge(int *num,int start,int middle,int end);

int main()
{
// 測試數組
int num[10]= {12,54,23,67,86,45,97,32,14,65};
int i;
// 排序之前
printf("Before sorting:\n");
for (i=0; i<10; i++)
{
printf("%3d",num[i]);
}
printf("\n");
// 進行合並排序
mergesort(num,0,9);
printf("After sorting:\n");
// 排序之後
for (i=0; i<10; i++)
{
printf("%3d",num[i]);
}
printf("\n");
return 0;
}

//這個函數用來將問題細分

void mergesort(int *num,int start,int end)
{
int middle;
if(start<end)
{
middle=(start+end)/2;
// 歸並的基本思想
// 排左邊
mergesort(num,start,middle);
// 排右邊
mergesort(num,middle+1,end);
// 合並
merge(num,start,middle,end);
}
}

//這個函數用於將兩個已排好序的子序列合並

void merge(int *num,int start,int middle,int end)
{

int n1=middle-start+1;
int n2=end-middle;
// 動態分配內存，聲明兩個數組容納左右兩邊的數組
int *L=new int[n1+1];
int *R=new int[n2+1];
int i,j=0,k;

//將新建的兩個數組賦值
for (i=0; i<n1; i++)
{
*(L+i)=*(num+start+i);
}
// 哨兵元素
*(L+n1)=1000000;
for (i=0; i<n2; i++)
{
*(R+i)=*(num+middle+i+1);
}
*(R+n2)=1000000;
i=0;
// 進行合並
for (k=start; k<=end; k++)
{
if(L[i]<=R[j])
{
num[k]=L[i];
i++;
}
else
{
num[k]=R[j];
j++;
}
}
delete [] L;
delete [] R;
}

6. C語言歸並排序

7. c語言歸並排序問題

前一個是把兩個數組中小的排好序，但是兩個數組中自己並沒有排序，那是收尾工作
while((begin1
<=
end1)&&(
begin2
<=
end2))的結束條件是:要麼begin1
>
end1
要麼begin2>end2
所以下面兩個其實只會做其中一個

8. C語言關於歸並排序的問題，高分等待

歸並需要額外空間，穩定排序，如果需要排列的內容大到不能裝到主存，歸並就發揮優勢了，典型的外排序。

9. C語言歸並排序代碼

void mergeSort(int a[],int left,int right)
{
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++];
Array(b,a,newArrayLen,left);
free(b);
}
/**
* 復制數組
* source:源數組
* dest:目標數組
* len:源數組長度
* first:目標數組起始位置
*
*/
void Array(int source[], int dest[],int len,int first)
{
int i;
int j=first;
for(i=0;i<len;i++)
{
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);
}

10. C語言-歸並排序-大家看我的程序哪裡錯了

用結構體？使用遞歸調用和分治法的歸並排序c語言完整程序如下，我所見過最簡潔的程序,win-tc和tc下通過：
/* 歸並排序 */
# include <stdio.h>
# include <stdlib.h>
# include <conio.h>
# define MAX 255
int R[MAX];

void Merge(int low,int m,int high)
{/* 將兩個有序的子文件R[low..m]和R[m+1..high]歸並成一個有序的 */
/* 子文件R[low..high] */
int i=low,j=m+1,p=0; /* 置初始值 */
int *R1; /* R1是局部向量，若p定義為此類型指針速度更快 */
R1=(int *)malloc((high-low+1)*sizeof(int));
if(!R1) /* 申請空間失敗 */
{
puts("Insufficient memory available!");
return;
}
while(i<=m&&j<=high) /* 兩子文件非空時取其小者輸出到R1[p]上 */
R1[p++]=(R[i]<=R[j])?R[i++]:R[j++];
while(i<=m) /* 若第1個子文件非空，則復制剩餘記錄到R1中 */
R1[p++]=R[i++];
while(j<=high) /* 若第2個子文件非空，則復制剩餘記錄到R1中 */
R1[p++]=R[j++];
for(p=0,i=low;i<=high;p++,i++)
R[i]=R1[p];/* 歸並完成後將結果復制回R[low..high] */
} /* end of Merge */

void Merge_SortDC(int low,int high)
{/* 用分治法對R[low..high]進行二路歸並排序 */
int mid;
if(low<high)
{/* 區間長度大於1 */
mid=(low+high)/2; /* 分解 */
Merge_SortDC(low,mid); /* 遞歸地對R[low..mid]排序 */
Merge_SortDC(mid+1,high); /* 遞歸地對R[mid+1..high]排序 */
Merge(low,mid,high); /* 組合，將兩個有序區歸並為一個有序區 */
}
}/* end of Merge_SortDC */

void main()
{
int i,n;
clrscr();
puts("Please input total element number of the sequence:");
scanf("%d",&n);
if(n<=0||n>MAX)
{
printf("n must more than 0 and less than %d.\n",MAX);
getch();
exit(0);
}
puts("Please input the elements one by one:");
for(i=1;i<=n;i++)
scanf("%d",&R[i]);
puts("The sequence you input is:");
for(i=1;i<=n;i++)
printf("%4d",R[i]);
Merge_SortDC(1,n);
puts("\nThe sequence after merge_sortDC is:");
for(i=1;i<=n;i++)
printf("%4d",R[i]);
puts("\n Press any key to quit...");
getch();
}

歸並排序c語言

與歸並排序c語言相關的內容