歸并排序的算法思想:把待排序序列分成相同大小的兩個(gè)部分,依次對(duì)這兩部分進(jìn)行歸并排序,完畢之后再按照順序進(jìn)行合并.
//?歸并排序中的合并算法
void?Merge(int?array[],?int?start,?int?mid,?int?end)
{
????int?temp1[10],?temp2[10];
????int?n1,?n2;
????n1?=?mid?-?start?+?1;
????n2?=?end?-?mid;
????//?拷貝前半部分?jǐn)?shù)組
????for?(int?i?=?0;?i?<?n1;?i++)
????{
????????temp1[i]?=?array[start?+?i];
????}
????//?拷貝后半部分?jǐn)?shù)組
????for?(int?i?=?0;?i?<?n2;?i++)
????{
????????temp2[i]?=?array[mid?+?i?+?1];
????}
????//?把后面的元素設(shè)置的很大
????temp1[n1]?=?temp2[n2]?=?1000;
????//?逐個(gè)掃描兩部分?jǐn)?shù)組然后放到相應(yīng)的位置去
????for?(int?k?=?start,?i?=?0,?j?=?0;?k?<=?end;?k++)
????{
????????if?(temp1[i]?<=?temp2[j])
????????{
????????????array[k]?=?temp1[i];
????????????i++;
????????}
????????else
????????{
????????????array[k]?=?temp2[j];
????????????j++;
????????}
????}
}
//?歸并排序
void?MergeSort(int?array[],?int?start,?int?end)
{
????if?(start?<?end)
????{
????????int?i;
????????i?=?(end?+?start)?/?2;
????????//?對(duì)前半部分進(jìn)行排序
????????MergeSort(array,?start,?i);
????????//?對(duì)后半部分進(jìn)行排序
????????MergeSort(array,?i?+?1,?end);
????????//?合并前后兩部分
????????Merge(array,?start,?i,?end);
????}
}