歸并排序的算法思想:把待排序序列分成相同大小的兩個部分,依次對這兩部分進行歸并排序,完畢之后再按照順序進行合并.
//?歸并排序中的合并算法
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;
????//?拷貝前半部分數組
????for?(int?i?=?0;?i?<?n1;?i++)
????{
????????temp1[i]?=?array[start?+?i];
????}
????//?拷貝后半部分數組
????for?(int?i?=?0;?i?<?n2;?i++)
????{
????????temp2[i]?=?array[mid?+?i?+?1];
????}
????//?把后面的元素設置的很大
????temp1[n1]?=?temp2[n2]?=?1000;
????//?逐個掃描兩部分數組然后放到相應的位置去
????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;
????????//?對前半部分進行排序
????????MergeSort(array,?start,?i);
????????//?對后半部分進行排序
????????MergeSort(array,?i?+?1,?end);
????????//?合并前后兩部分
????????Merge(array,?start,?i,?end);
????}
}