算法基础五：归并排序
一：定义：
归并排序算法是在分治算法基础上设计出来的一种排序算法，它可以对指定序列完成升序（由小到大）或降序（由大到小）排序。
二：基本思路
归并排序算法实现排序的思路是：
- 将整个待排序序列划分成多个不可再分的子序列，每个子序列中仅有 1 个元素；
- 所有的子序列进行两两合并，合并过程中完成排序操作，最终合并得到的新序列就是有序序列。
举个简单的例子，使用归并排序算法对 {7, 5, 2, 4, 1, 6, 3, 0} 实现升序排序的过程是：
1) 将 {7, 5, 2, 4, 1, 6, 3, 0} 分割成多个子序列，每个子序列中仅包含 1 个元素，分割过程如下所示：
图1：归并排序算法分割序列的过程
整个序列不断地被一分为二，最终被分割成 {7}、{5}、{2}、{4}、{1}、{6}、{3}、{0} 这几个序列。
2) 将 {7}、{5}、{2}、{4}、{1}、{6}、{3}、{0} 以“两两合并”的方式重新整合为一个有序序列，合并的过程如下图所示：
图2：归并排序算法整合所有子序列的过程
三：代码实现
如下是用归并排序算法对 {7, 5, 2, 4, 1, 6, 3, 0} 进行升序排序的C语言程序：
#include <stdio.h>
//实现分割的函数
void merge_sort(int arr[], int p, int q);
//实现归并的函数
void merge(int arr[], int p, int min, int q);
int main()
{
int i = 0;
int arr[8] = { 7,5,2,4,1,6,3,0 };
//对 arr 数组中第 1 至 8 个元素进行归并排序
merge_sort(arr, 1, 8);
while(i<8)
{
printf("%d ", arr[i]);
i++;
}
return 0;
}
//实现分割操作的函数，[p,q] 用于指定归并排序的区域范围，
void merge_sort(int arr[], int p, int q)
{
int mid;
if (arr == NULL || p > q || p == q)
{
return;
}
mid = (q + p) / 2;
//将 [p,q] 分为[p,mid] 和 [mid+1,q] 区域
merge_sort(arr, p, mid);
merge_sort(arr, mid + 1, q);
//对分好的 [p,mid] 和 [mid,q] 进行归并操作
merge(arr, p, mid, q);
}
//实现归并操作的函数，归并的 2 个区域分别为 [p,mid] 和 [mid+1,q]
void merge(int* arr,int p,int mid,int q)
{
int i, j, k;
int lefter[100], righter[100];
int numL = mid - p + 1;
int numR = q - mid;
//将 arr 数组中 [p,mid] 区域内的元素逐一拷贝到 leftarr 数组中
for (i = 0; i < numL; i++)
{
lefter[i] = arr[p - 1 + i];
}
//将 arr 数组中 [mid+1,q] 区域内的元素逐一拷贝到 rightarr 数组中
lefter[i] = 2147483647;
for (i = 0; i < numR; i++)
{
righter[i] = arr[mid + i];
}
righter[i] = 2147483647;
i = 0;
j = 0;
//逐一比较 leftarr 和 rightarr 中的元素，每次将较小的元素拷贝到 arr 数组中的 [p,q] 区域内
for (k = p; k <= q; k++)
{
if (lefter[i] < righter[j])
{
arr[k - 1] = lefter[i];
i++;
}
else
{
arr[k - 1] = righter[j];
j++;
}
}
}如下是用归并排序算法对 {7, 5, 2, 4, 1, 6, 3, 0} 进行升序排序的 Python 程序：
#实现归并排序算法中的分割操作，[p,q]为指定分割区域
def merge_sort(arr,p,q):
#列表中没有数据，或者 [p,q]区域不存在
if len(arr) == 1 or p >= q:
return
#对 [p,q] 区域进行分割
mid = int( (p + q) / 2 )
merge_sort(arr,p,mid)
merge_sort(arr,mid+1,q)
#归并 [p,mid] 和 [mid+1,q] 区域
merge(arr,p,mid,q)
#实现归并排序算法中的归并操作，归并区域为 [p.mid] 和 [mid+1,q]
def merge(arr,p,mid,q):
numL = mid - p + 1;
numR = q - mid;
#分别将 [p,mid] 和 [mid+1,q] 区域内的元素拷贝到 leftarr 和 rightarr 列表中
leftarr = arr[p-1:p+numL-1]
rightarr = arr[mid:mid+numR]
# 2 个列表末尾添加一个足够大的数
leftarr.append(float('inf'))
rightarr.append(float('inf'))
i=0
j=0
k=p
#逐个比较 leftarr 和 rightarr 列表中的元素，每次将较小的元素添加到 arr 列表中的 [p,q] 区域内
while k <= q:
if leftarr[i] <= rightarr[j]:
arr[k-1] = leftarr[i]
i = i + 1
else:
arr[k-1] = rightarr[j]
j = j + 1
k = k + 1
arr = [7, 5, 2, 4, 1, 6, 3, 0]
#对 arr 数组中第 1 至 8 个元素做归并排序操作
merge_sort(arr, 1, 8)
print(arr)四：代码解析
1、merge_sort函数
数组为空直接返回
if (arr == NULL || p > q || p == q)
{
return;
}现将数组分为p到mid、mid+1到q，然后将其合并放回arr数组
merge_sort(arr, p, mid);
merge_sort(arr, mid + 1, q);
//对分好的 [p,mid] 和 [mid,q] 进行归并操作
merge(arr, p, mid, q);2、merge函数
定义一对左右数组接收，左右数字大小代表所在地址
int lefter[100], righter[100];
int numL = mid - p + 1;
int numR = q - mid;3：将要排序的数组从mid一次往左（包括min），往右放入定义好的数组，最后给他一个无穷大数
for (i = 0; i < numL; i++)
{
lefter[i] = arr[p - 1 + i];
}
//将 arr 数组中 [mid+1,q] 区域内的元素逐一拷贝到 rightarr 数组中
lefter[i] = 2147483647;
for (i = 0; i < numR; i++)
{
righter[i] = arr[mid + i];
}
righter[i] = 2147483647; 4：开始回归排序，将新的顺序覆盖原来数组，两边那个小就往里进
i = 0;
j = 0;
//逐一比较 leftarr 和 rightarr 中的元素，每次将较小的元素拷贝到 arr 数组中的 [p,q] 区域内
for (k = p; k <= q; k++)
{
if (lefter[i] < righter[j])
{
arr[k - 1] = lefter[i];
i++;
}
else
{
arr[k - 1] = righter[j];
j++;
}
}