如下代碼內(nèi)容是關(guān)于C++算法之合并排序法的代碼，應(yīng)該是對(duì)大伙有些用。
void merge_sort(int array[], int length)?
{?
? ? if(NULL == array || 0 == length)?
? ? ? ? return ;?
? ? _merge_sort(array, 0, length-1);?
}?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
b）進(jìn)行merge函數(shù)迭代操作
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
void _merge_sort(int array[], int start, int end)?
{?
? ? if(start >= end)?
? ? ? ? return;?
?
? ? int middle = start + ((end - start) >> 1);?
? ? _merge_sort(array, start, middle);?
? ? _merge_sort(array, middle + 1, end);?
? ? _merge_data_in_array(array, start, middle, end);?
}?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
c）對(duì)合并后的隊(duì)列進(jìn)行合并操作
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
void _merge_data_in_array(int array[], int start, int middle, int end)?
{?
? ? int length = end - start + 1;?
? ? int left = start;?
? ? int right = middle + 1;?
? ? int all = 0;?
?
? ? assert(NULL != pData);?
? ? memset(pData, 0, length);?
?
? ? while(right <= end){?
? ? ? ? while(array[left] <= array[right] && left <= middle){?
? ? ? ? ? ? pData[all] = array[left]; left ++; all ++;?
? ? ? ? }?
?
? ? ? ? if(left > middle)? {?
? ? ? ? ? ? break;?
? ? ? ? }?
?
? ? ? ? while(array[left] > array[right] && right <= end){?
? ? ? ? ? ? pData[all] = array[right]; right ++; all ++;?
? ? ? ? }?
? ? }?
?
? ? if(left <= middle)?
?
? ? if(right <= end)?
? ? ?
? ? free(pData);?
}?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
注：文中使用的pData動(dòng)態(tài)內(nèi)存不是一種最優(yōu)的處理辦法，實(shí)際開發(fā)中可以由其他形式的數(shù)據(jù)類型代替。d）編寫測試用例
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
static void test1()?
{?
? ? int array[] = {1};?
? ? merge_sort(array, sizeof(array)/sizeof(int));?
}?
?
static void test2()?
{?
? ? int array[] = {2, 1};?
? ? merge_sort(array, sizeof(array)/sizeof(int));?
? ? assert(1 == array[0]);?
? ? assert(2 == array[1]);?
}?
?
static void test3()?
{?
? ? int array[] = {3, 2, 1};?
? ? merge_sort(array, sizeof(array)/sizeof(int));?
? ? assert(1 == array[0]);?
? ? assert(2 == array[1]);?
? ? assert(3 == array[2]);?
}?
?
static void test4()?
{?
? ? int array[] = {4, 3, 5, 1};?
? ? merge_sort(array, sizeof(array)/sizeof(int));?
? ? assert(1 == array[0]);?
? ? assert(3 == array[1]);?
? ? assert(4 == array[2]);?
? ? assert(5 == array[3]);?
}?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
分析快速排序和合并排序的相同點(diǎn)和不同點(diǎn)：相同點(diǎn)：都是迭代操作不同點(diǎn)：快速排序，先分類再迭代；合并排序，先迭代再合并
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ? ?
? ? ? ? ? ?
? ? ? ? ? ? ? ?
