TZC 1283: 简单排序 —— 归并排序

我们以TZC 1283为例简单说明一下排序（含十大经典排序算法）的python实现方法和C实现方法。归并排序原理请参见：https://www.jianshu.com/p/33cffa1ce613 或 https://www.runoob.com/w3cnote/merge-sort.html

原题链接：1283: 简单排序

python代码如下：

import math


# 归并排序
def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r - m

    # 创建临时数组
    L = [0] * n1
    R = [0] * n2

    # 拷贝数据到临时数组 arrays L[] 和 R[]
    for i in range(0, n1):
        L[i] = arr[l + i]

    for j in range(0, n2):
        R[j] = arr[m + 1 + j]

        # 归并临时数组到 arr[l..r]
    i = 0  # 初始化第一个子数组的索引
    j = 0  # 初始化第二个子数组的索引
    k = l  # 初始归并子数组的索引

    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    # 拷贝 L[] 的保留元素
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    # 拷贝 R[] 的保留元素
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1


def merge_sort(arr, l, r):
    if l < r:
        m = int((l + (r - 1)) / 2)

        merge_sort(arr, l, m)
        merge_sort(arr, m + 1, r)
        merge(arr, l, m, r)


T = int(input())
for i in range(T):
    s = input().split()
    lt = [int(x) for x in s]
    lt1 = lt[::-1]
    lt1.pop()
    lt1 = lt1[::-1]
    n = len(lt1)

    merge_sort(lt1, 0, n - 1)

    for j in range(n):
        if j != n - 1:
            print(lt1[j], end=' ')
        else:
            print(lt1[j])

C语言代码如下：

#include 
#include 
#define N 1010
int a[N],b[N],r[N];
void msort(int s,int t) //归并排序 
{
    int i,j,mid,k;
    if(s==t)      		//如果只有一个数字则返回，无需排序 
        return;
    mid=(s+t)/2;
    
    msort(s,mid);		//分解左序列 
    msort(mid+1,t);		//分解有序列 
    
    i=s;
    j=mid+1;
    k=s;
    
    while(i<=mid && j<=t)	//接下来合并 
    {
        if(a[i]<=a[j])
        {
            r[k]=a[i];
            k++;
            i++;
        }
        else
        {
            r[k]=a[j];
            k++;
            j++;
        }
    }
    while(i<=mid)	//复制左边子序列剩余 
    {
        r[k]=a[i];
        k++;
        i++;
    }
    while(j<=t)		//复制右边子序列剩余 
    {
        r[k]=a[j];
        k++;
        j++;
    }
    for(i=s;i<=t;i++)
        a[i]=r[i];
}
int main()
{
	int m,n,i,j,t;
	scanf("%d",&m);
	while(m--)
	{
		scanf("%d",&n);
		memset(a,0,n);			//初始化数组
		for(i=0;i<=n-1;i++)		//输入
			scanf("%d",&a[i]);
		
		msort(0,n-1);

		for(i=0;i<=n-1;i++)		//输出 
		{
			if(i!=n-1)
				printf("%d ",a[i]);
			else
				printf("%dn",a[i]);
		}
	}
	return 0;
}