遞歸合並排序c語言

❶ c語言歸並排序 的合並是靠什麼實現的。

是靠優化的插入排序實現的。按遞歸的思路將要排序的部分，拆分成不可拆分的小段再兩兩合並。
之所以說優化後的插入排序是因為合並的兩端都是有序的，所以只需要每次比較最前方的一個元素，當一列完全插入後，在後面追加另一列。

你給出的例子沒有拆分到底，所以先拆分

比如：49, 38,65, 97,76, 13, 27
先拆分
（49, 38,65, 97）,（76, 13, 27）
（49, 38）,（65, 97）,（76, 13）,（ 27）你的例子
(49),(38),(65),(97),(76),(13),(27)
(38,49),(65,97),(13,76),(27)
（38,49,65,97）,(13,27,76)
(13,27,49,65,76,97)

❷ 歸並排序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]);
/*將排序後的結構輸出*/
}


❸ C語言利用遞歸實現插入排序，選擇排序，快速排序，歸並排序演算法。 要求有注釋 ！ 謝謝各位大神！

//InsertionSort
void insertionSort(int a[], int size) {
int i, j, key;

for (i = 0; i < size; i++) {
key = a[i];
j = i-1;
while (j >= 0 && key < a[j]) { //把元素插入到之前的有序元組中
a[j+1] = a[j];
j--;
}
a[j+1] = key;
}
}

//MergeSort
void merge(int a[], int p, int q, int r) { //合並兩個子元組
int i, j, k, n1, n2;
int *array1, *array2;
n1 = q - p + 1,
n2 = r - q;

array1 = (int *)calloc(n1+1, sizeof(int));
array2 = (int *)calloc(n2+1, sizeof(int));
if (array1 == NULL || array2 == NULL) {
printf("Error: calloc failed in concat\n");
exit(EXIT_FAILURE);
}
for(i = 0; i < n1; i++)
array1[i] = a[p + i];
for(i = 0; i < n2; i++)
array2[i] = a[q + 1 + i];
array1[n1] = MAXNUMBER;
array2[n2] = MAXNUMBER;
i = 0, j = 0;
for(k = p; k <= r; k++)
if(array1[i] <= array2[j])
a[k] = array1[i++];
else
a[k] = array2[j++];
free(array1);
free(array2);
}

void mergeSort(int a[], int p, int r) {//歸並的遞歸調用
int q;
if (p < r) {
q = (p+r)/2;
mergeSort(a,p,q);
mergeSort(a,q+1,r);
merge(a,p,q,r);
}
}

//QuickSort
int partition(int a[], int p, int r) {//快排的分組函數
int i, j, x, temp;
x = a[r];
i = p - 1;

for (j = p; j < r; j++)
if (x > a[j]) {
temp = a[++i];
a[i] = a[j];
a[j] = temp;
}
temp = a[++i];
a[i] = a[r];
a[r] = temp;

return i;
}

void quickSort(int a[], int p, int r) { //快排
int q;
if (p < r) {
q = partition(a, p, r);
quickSort(a, p, q-1);
quickSort(a, q+1, r);
}
}

//隨即版的quickSort
int randomPartition(int a[], int p, int r){

int i, temp;
i = rand();
while( i < p || i > r)
i = rand();
temp = a[i];
a[i] = a[r];
a[r] = temp;
return partition(a,p,r);
}

void randomQuickSort(int a[], int p, int r){
int q;
if(p < r){
q = randomPartition(a,p,r);
randomQuickSort(a,p,q-1);
randomQuickSort(a,q+1,r);
}
}
//BubbleSort();//冒泡排序
void bubbleSort(int a[], int size) {
int i, j, temp;

for (i = size -1; i >= 0; i--)
for (j = 0; j < i; j++)
if (a[j] < a[j+1]) {
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}

❹ 怎樣使用遞歸實現歸並排序

第一步：先寫一個合並兩個排序好數組的方法，方法名就叫做merge，如下：

[java]view plain

• publicstaticvoidmerge(int[]a,intaSize,int[]b,intbSize,int[]c){

• inttempA=0,tempB=0,tempC=0;

• while(tempA<aSize&&tempB<bSize){

• if(a[tempA]>b[tempB]){

• c[tempC++]=b[tempB++];

• }else{

• c[tempC++]=a[tempA++];

• }

• }

• while(tempA<aSize){

• c[tempC++]=a[tempA++];

• }

• while(tempB<bSize){

• c[tempC++]=b[tempB++];

• }


這個方法非常簡單，一共有著5個參數（也可以簡化為3個參數）,其中a，b數組是待合並數組，aSize，bSize是數組長度（這兩個參數可以去掉）,c為目標數組。主要的流程就是不斷的比較a，b數組的大小，然後將較小數據復制進c中。這裡面關鍵的一點就是使用了3個臨時變數，用於標志每個數組對應的位置，這樣子可以極大簡化我們的代碼設計。下面是對應的圖示過程：



有了這個方法之後，我們就可以開始寫歸並排序的主體方法了。寫主體方法也很簡單，思想就是分治演算法。

• 第一步：就是將大數組分成兩個小的數組

• 第二部：排序這兩個數組，使用的是遞歸排序方法，也就是自己調用自己

• 第三部：調用上面的合並方法合並起來即可

代碼非常簡單，直接貼上

[java]view plain

• publicclassTowersApp{

• publicstaticvoidmain(String[]args){

• int[]a={1,1,0,1,1,5,3};

• mergeSort(a);

• for(inti=0;i<a.length;i++){

• System.out.print(a[i]);

• }

• }

• publicstaticvoidmergeSort(int[]source){

• //遞歸出口

• if(source.length==1)return;

• //將大數組分成兩個小數組

• intmiddle=source.length/2;

• int[]left=newint[middle];

• for(inti=0;i<middle;i++){

• left[i]=source[i];

• }

• int[]right=newint[source.length-middle];

• for(inti=middle;i<source.length;i++){

• right[i-middle]=source[i];

• }

• //對數據進行排序（這里使用遞歸排序）

• mergeSort(left);

• mergeSort(right);

• //合並排序好的數據

• merge(left,left.length,right,right.length,source);

• }

• publicstaticvoidmerge(int[]a,intaSize,int[]b,intbSize,int[]c){

• inttempA=0,tempB=0,tempC=0;

• while(tempA<aSize&&tempB<bSize){

• if(a[tempA]>b[tempB]){

• c[tempC++]=b[tempB++];

• }else{

• c[tempC++]=a[tempA++];

• }

• }

• while(tempA<aSize){

• c[tempC++]=a[tempA++];

• }

• while(tempB<bSize){

• c[tempC++]=b[tempB++];

• }

• }

• }






總結：要記住歸並排序演算法的核心核心思想：分而治之。

❺ 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;
}

❻ 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;
}

❼ 用c語言編寫歸並排序代碼，要求易懂，本人只是c語言的初學者，越簡單越好。

//#include<iostream>
//
//using namespace std;
//
//void Guibing(int*arr,int low,int high)
//{
// int m_Begin1 = low;
// int m_End1 = (low+high)/2;
// int m_Begin2 = m_End1+1;
// int m_End2 = high;
//
// int* temp = new int[high-low+1];
// //申請一個這兩組的空間
// //要看 只要有一組到結尾就要結束
// int k=0;
// for (;m_Begin1 <= m_End1 && m_Begin2 <= m_End2;k++)
// {
// // 然後找小的往裡存
// if (arr[m_Begin1] < arr[m_Begin2])
// {
// temp[k] = arr[m_Begin1];
// m_Begin1++;
// }
// else
// {
// temp[k] = arr[m_Begin2];
// m_Begin2++;
// }
// }
//
// //如果第一組沒到結尾 順序存
// while(m_Begin1 <= m_End1)
// {
// temp[k] = arr[m_Begin1];
// k++;
// m_Begin1++;
// }
// //如果第二組沒到結尾 順序存
// while(m_Begin2 <= m_End2)
// {
// temp[k] = arr[m_Begin2];
// k++;
// m_Begin2++;
// }
// //把已經排好序的 temp 放回到原來對應的位置
// for (k = 0;k<high-low+1;k++)
// {
// arr[low+k] = temp[k];
// }
// delete[] temp;
//}
//
//void Digui(int*arr,int low,int high)
//{
// if (low < high)
// {
// int mid = (low+high)/2;
// Digui(arr,low,mid);
// Digui(arr,mid+1,high);
// Guibing(arr,low,high);
// }
//}
//
//int main()
//{
// int arr[10] = {9,11,5,3,17,13,1,17,25,8};
//
// Digui(arr,0,9);
//
// for (int i =0 ;i<10;i++)
// {
// cout << arr[i] << " ";
// }
//
// system("pause");
// return 0;
//}

❽ C語言，二路歸並排序，遞歸調用到底是怎麼調用的求詳解！

程序代碼都是順序執行的，當然是把一路調用完再做第二路調用，最後把排好序的2路進行合並；

在排序每一路的時候也是使用歸並的方式，把一路分成2路，層層深入。

理解的話，你可以這樣：

比如8個數，你從上到下豎著排成一列，然後中間一條橫線分割。

橫線上面的部分再從中間分割成2部分，2部分放在第二列；

依次往後分割。得到形如這樣的圖：

然後按照紅色箭頭先按A反推一層，再按B向下一層，這樣就會合並一次產生排好序的前一層。如此反復，這就是遞歸實際的執行流程。

❾ 用C語言,隨機輸入十個整數,用合並排序法對這些整數進行排序~

用遞歸函數實現：

#include<stdlib.h>
#include<stdio.h>
/* 將a的兩個有序子序列（a[l]~a[m]和a[m+1]~a[r]）合並為一個有序序列 */
void merge(int a[], int l, int m, int r)
{
int i,j,k;
int *t=(int*)malloc((r-l+1)*sizeof(int)); /* 建立臨時數組，保存合並結果 */
i=l; /* i為前一序子序列的待合並元素位置 */
j=m+1; /* j為後一序子序列的待合並元素位置 */
k=0; /* k為即將加入到合並結果序列的元素位置 */
while(i<=m && j<=r) /* 條件：兩個序子序列均未合並完 */
{
/* 將兩個序子序列的待合並元素中較小的一個元素合並到t */
if(a[i]<a[j])
t[k]=a[i++];
else
t[k]=a[j++];
k++;
}

/* 前一序子序列未合並完，將剩餘部分傳入t */
while(i<=m)
t[k++]=a[i++];

/* 後一序子序列未合並完，將剩餘部分傳入t */
while(j<=r)
t[k++]=a[j++];

/* 合並結果傳回數組a的a[l] ~ a[r] */
for (i=0; i<k; i++)
a[l+i]=t[i];
free(t);
}

void sort(int a[], int l, int r)
{
if(l<r)
{
int m=(l+r)/2; /* 分解成兩組：l ~ m 和 m+1 ~ r */
sort(a, l, m); /* 遞歸：對前半段排序 */
sort(a, m+1, r); /* 遞歸：對後半段排序 */
merge(a, l, m, r); /* 合並結果 */
}
}

void main()
{
int a[10];
int i;
for(i=0; i<10; i++)
scanf("%d",&a[i]);
sort(a,0,9);
for(i=0; i<10; i++)
printf("%d ",a[i]);
printf("\n");
}

❿ c語言遞歸排序怎麼寫、

哪有什麼遞歸排序，遞歸只是一種函數調用方式，只是很多排序方法有用到遞歸，比如快速排序，搜索中的二分法，深搜，廣搜。