数据结构java，c，python实现二路归并排序

c语言

#include<stdio.h>
#include<stdlib.h>
void Merge(int *num1,int start,int mid,int end){
    int *res;
    res = (int *)malloc(sizeof(int)*(start+end+1));
    int lp = start;
    int rp = mid+1;
    int Nindex = start;     
    while(lp<=mid&&rp<=end){
        if(num1[lp]<num1[rp]){
            res[Nindex++] = num1[lp++];
        }
        else{
            res[Nindex++] = num1[rp++];
        }       
    }
    while(lp<=mid){
            res[Nindex++] = num1[lp++];
        }
    
    while(rp<=end){
            res[Nindex++] = num1[rp++];
        }
    
    while(start<=end){
        num1[start] = res[start++]; 
    }
}
void MergeSort(int *num,int start,int end){     
        if(start>=end)
            return;     
        int middle = (start+end)/2; 
        MergeSort(num,start,middle);
        MergeSort(num,middle+1,end);
        Merge(num,start,middle,end);

}
int main(){
    int num[]={1,23,-1,15,4,6,8,10};
    int i;
    int len = sizeof(num)/sizeof(int);
    MergeSort(num,0,len-1);
    for(i=0;i<len;i++)
        printf("%d ",num[i]);
}

java

package smile;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int num[] = {1,18,25,-1,8,56,13,6,7,34};
        mergeSort(num,0,num.length-1);
        System.out.println(Arrays.toString(num));
    }
//递归调用归并排序
    public static void mergeSort(int []num,int start,int end) {
        if(start>=end) {
            return;
        }       
        int middle = (end+start)/2;
        mergeSort(num,start,middle);
        mergeSort(num,middle+1,end);
        merge(num,start,end,middle);
        
    }
//合并两个有序数组
    public static void merge(int []num,int start,int end,int middle) {
        int res[] = new int[num.length];
        int i=start;  //左边数组的开始i
        int j=middle+1; //右边数组的开始j
        int k=start;  //新数组的插入索引
        while((i<=middle)&&(j<=end)) {
            if(num[i]<num[j]) {
                res[k++]=num[i++];  //若左边数组中的值小于右边的，则将左边数组中该元素加入到新数组中，并将i后移
            }
            else {
                res[k++]=num[j++];   //若左边数组中的值大于或等于右边的，则将右边数组中该元素加入到新数组中，并将j后移
            }
        }   
//      当两个数组长度不一致导致有一个先结束循环，则将另一个数组剩下的数全部加入到新数组中
        while(j<=end) {
            res[k++] = num[j++];
        }
        while(i<=middle) {
            res[k++] = num[i++];
        }   
//      将排好序的元素放回到原数组中
        while(start<=end) {
            num[start] = res[start++];
        }
    }
}

python

# 合并函数将两个有序的数组合并成一个有序数组
def merge(a,b):
    ap=0
    bp=0
    res=[]
# 用两个指针分别指向两个列表元素，若指向的元素满足条件，则加入新数组且指针后移,再继续比较
    while ap<len(a) and bp<len(b):
        if a[ap]<b[bp]:
            res.append(a[ap])
            ap+=1
        else:
            res.append(b[bp])
            bp+=1

# 若是有其中一个数组提前结束循环，将它剩下的元素直接放入合并后的列表
    if len(a)==ap:
        for i in b[bp:]:
            res.append(i)
    else:
        for i in a[ap:]:
            res.append(i)
    return res

# 递归调用归并算法,当元素少于两个时,返回该元素的值
def mergeSort(num):
    if len(num)<=1:
        return num
    middle = len(num)//2
    l=mergeSort(num[:middle])
    r=mergeSort(num[middle:])
    return merge(l,r)

if __name__ == '__main__':
    num = [1,8,4,3,7,5,6]
    re = mergeSort(num)
    print(re)

由此可见 python写算法是真的爽！！！