public class MergeSort {
public static int[] sort(int[] a,int low,int high){
int mid = (low+high)/2; //左右归并
if(low<high){
sort(a,low,mid);
sort(a,mid+1,high);
merge(a,low,mid,high);
}
return a;
}
public static void merge(int[] a, int low, int mid, int high) {
int[] temp = new int[high-low+1];//创建新数组
int i= low;
int j = mid+1;
int k=0;
// 把较小的数先移到新数组中
while(i<=mid && j<=high){
if(a[i]<a[j]){
temp[k++] = a[i++];
}else{
temp[k++] = a[j++];
}
}
// 把左边剩余的数移入数组
while(i<=mid){
temp[k++] = a[i++];
}
// 把右边边剩余的数移入数组
while(j<=high){
temp[k++] = a[j++];
}
// 把新数组中的数覆盖nums数组
for(int x=0;x<temp.length;x++){
a[x+low] = temp[x];
}
}
public static void main(String[] args) {
int[] arr= {55,44,85,16,12,17,99,65};
int[] Last=new int[arr.length];
Last=MergeSort.sort(arr,0,arr.length);
System.out.println("归并排序后的顺序为：");
for(int i=0;i<arr.length;i++) {
System.out.print(arr[i]+" ");
}
}
}
Python实现归并排序
def merge_sort(li):
if len(li)==1:
return li
mid=len(li)//2
Left=li[:mid]
Right=li[mid:]
l1=merge_sort(Left)
r1=merge_sort(Right)
return merge(l1,r1)
def merge(left,right):
result=[] #创建一个空列表
while len(left)>0 and len(right)>0 : #当遇到相等的时候优先把左侧的数放进结果列表，因为left本来也是大数列中比较靠左的
if left[0] <= right[0]:
result.append( left.pop(0) ) #删除left列表中的元素会有返回值并将值追加到result列表后面
else:
result.append( right.pop(0) ) #删除right列表中的元素会有返回值并将值追加到result列表后面
result += left #while循环出来之后 说明其中一个数组没有数据了，我们把另一个数组添加到结果数组后面
result += right
return result
if __name__=="__main__":
arr=[10,20,40,30,90,60,70,80]
temp=merge_sort(arr)
print(temp)
