合併就是把兩堆已經排序好的資料
按大小重新排列成一堆 //---------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
//---------------------------------------------------------------------------
#define LEFT 'L'
#define RIGHT 'R'
//---------------------------------------------------------------------------
int g_icount = 1;
//---------------------------------------------------------------------------
void mergeSort(int *list, int *tmp, char type, int left, int right)
{
if(left >= right) return;
int middle = (left+right)/2;
mergeSort(list, tmp, LEFT, left, middle);
mergeSort(list, tmp, RIGHT, middle+1, right);
int indexL = left;
int indexR = middle+1;
int index = 0;
while(indexL <= middle && indexR <= right)
{
if(list[indexL] <= list[indexR])
{
tmp[index++] = list[indexL++];
}
else
{
tmp[index++] = list[indexR++];
}
}
//Copy from Left
for(int i = indexL; i <= middle; i++)
tmp[index++] = list[i];
//Copy from Right
for(int i = indexR; i <= right; i++)
tmp[index++] = list[i];
//Debug
printf("[%02d] %c ", g_icount++, type);
for(int i = 0; i < index; i++)
printf("%d ", tmp[i]);
printf("\n");
//Copy to list
int j;
for(int i = left, j = 0; i <= right; i++, j++)
list[i] = tmp[j];
}
//---------------------------------------------------------------------------
int main(void)
{
int list[] = {12,15,49,22,15,10};
int max = sizeof(list)/sizeof(int);
int tmp[6];
mergeSort(list, tmp, LEFT, 0, max-1);
printf("\nResult: ");
for(int i = 0; i < max; i++)
printf("%d ", list[i]);
printf("\n\n");
system("pause");
return 0;
}
//---------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
//---------------------------------------------------------------------------
#define LEFT 'L'
#define RIGHT 'R'
//---------------------------------------------------------------------------
int g_icount = 1;
//---------------------------------------------------------------------------
void mergeSort(int *list, int *tmp, char type, int left, int right)
{
if(left >= right) return;
int middle = (left+right)/2;
mergeSort(list, tmp, LEFT, left, middle);
mergeSort(list, tmp, RIGHT, middle+1, right);
int indexL = left;
int indexR = middle+1;
int index = 0;
while(indexL <= middle && indexR <= right)
{
if(list[indexL] <= list[indexR])
{
tmp[index++] = list[indexL++];
}
else
{
tmp[index++] = list[indexR++];
}
}
//Copy from Left
for(int i = indexL; i <= middle; i++)
tmp[index++] = list[i];
//Copy from Right
for(int i = indexR; i <= right; i++)
tmp[index++] = list[i];
//Debug
printf("[%02d] %c ", g_icount++, type);
for(int i = 0; i < index; i++)
printf("%d ", tmp[i]);
printf("\n");
//Copy to list
int j;
for(int i = left, j = 0; i <= right; i++, j++)
list[i] = tmp[j];
}
//---------------------------------------------------------------------------
int main(void)
{
int list[] = {12,15,49,22,15,10};
int max = sizeof(list)/sizeof(int);
int tmp[6];
mergeSort(list, tmp, LEFT, 0, max-1);
printf("\nResult: ");
for(int i = 0; i < max; i++)
printf("%d ", list[i]);
printf("\n\n");
system("pause");
return 0;
}
//---------------------------------------------------------------------------
