常用排序算法实现之归并排序(Merge Sort)

归并排序的算法思想是分而治之(divide - conquer),每个递归过程分为三个步骤:

1) 分解:把待排序的n个元素的序列分解成两个子序列,每个子序列包括n/2个元素

2) 治理:对每个子序列分别调用归并排序(MergeSort),进行归并操作

3) 合并:合并两个排好序的子序列,生成排序结果

 

// 归并排序中的合并算法
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);
　　　 }
}