[C/C++ 演算法]-資料結構與演算法(文魁)：合併排序 – jashliao部落格

[C/C++ 演算法]-資料結構與演算法(文魁)：合併排序

線上執行結果：http://www.tutorialspoint.com/compile_c_online.php

code2html：http://tohtml.com/

/* =============== Program Description =============== */
/* 程式名稱 : 6_9.cpp				       */
/* 程式目的 : 合併排序				       */
/* 輸    入 : 排序前的整數陣列資料		       */
/* 輸    出 : 排序後的整數陣列資料		       */
/* =================================================== */
#define n 20
// 宣告標頭檔
#include "stdio.h"
// 宣告函式原型
// 利用傳址的方式把Array A傳進merge_sort函式中
void merge_sort(int *A,int left,int right);
// 利用傳址的方式把Array A1,A2,A3傳進merge函式中
// 利用傳值的方式把整數A1_start,A2_start,A2_end,
// A3_start,A3_end傳進merge函式中
void merge(int *A1, int A1_start,
int *A2, int A2_start, int A2_end,
int *A3, int A3_start, int A3_end);
void main(void)
{
int i;
int A[n]={1,21,0,47,60,
15,84,65,77,88,
100,93,8,17,36,
5,24,63,72,20};
// 排序前的資料
printf(" Data before sorting \n");
for(i=0;i<n;i++)
printf("%d",A[i]);
printf("\n");
merge_sort(A,0,n-1);
// 排序後的資料
printf(" Data after sorting \n");
for(i=0;i<n;i++)
printf("%d",A[i]);
printf("\n");
getchar();
}
void merge_sort(int *A,int left,int right)
{
int half;
if (left < right)
{
half=(left+right)/2; 			/* 先找中間的位置 */
merge_sort(A,left,half); 		/* 將左邊到中間的一半數列作排序 */
merge_sort(A,half+1,right);		/* 將中間到右邊的一半數列作排序 */
merge(A,left,A,left,half,A,half+1,right);/* 將左右兩個數列合併 */
}
}
// 合併二個子數列合併成新數列的merge演算法
void merge(int *A1, int A1_start,
int *A2, int A2_start, int A2_end,
int *A3, int A3_start, int A3_end)
{
int i, j, k=0 , h;
int B[n];	/* 暫��陣列 */
i = A2_start;
j = A3_start;
while(i <= A2_end && j <= A3_end) {
if(A2[i] <= A3[j])
B[k++] = A2[i++];
else
B[k++] = A3[j++];
}
while (i<=A2_end) B[k++]=A2[i++];
while (j<=A3_end) B[k++]=A3[j++];
for(h=0;h<k;h++)
A1[A1_start+h] = B[h];    /* 將暫��陣列中的資料取出��到原本的陣列中 */
}