欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

归并排序

程序员文章站 2024-01-11 08:56:34
原创 先来看将两个有序数组合并成一个有序数组是如何操作的; 设有序数组为a和b,结果数组c; 归并排序的思想用的是分治法,假设待排序数组为array[n],再新建一个辅助数组array1[n]。 通过不断的将数组array进行递归折半(int mid=(left+right)/2),最后rihgt= ......

原创


先来看将两个有序数组合并成一个有序数组是如何操作的;

设有序数组为a和b,结果数组c;

int k=0;
while(i<=a.length-1 && j<=b.length-1){
    if(a[i]<b[j]) {
        c[k++]=a[i++];
    }
    else {
        c[k++]=b[j++];
    }
}
while(i<=a.length-1) {
    c[k++]=a[i++];
}
while(j<=b.length-1) {
    c[k++]=b[j++];
}

归并排序的思想用的是分治法,假设待排序数组为array[n],再新建一个辅助数组array1[n]。

通过不断的将数组array进行递归折半(int mid=(left+right)/2),最后rihgt==left,将元素array[left]放入辅助数组array1中;

递归回来,递归进去(mid+1,right),最后left==right,再将元素array[left]放入辅助数组array1中;

此时辅助数组有两个元素,用上面的合并算法合并到array中完成一个2路归并,再递归回来排序右边的。。。

import java.util.*;

public class 归并排序 {
    
    static void merge(int array[],int array1[],int s,int m,int t) {    //合并两个已排序好的子序列
        int i=s;
        int j=m+1;
        int k=s;
        while(i<=m && j<=t) {
            if(array[i]<array[j]) {    //将较小者放入array1
                array1[k++]=array[i++];
            }
            else {
                array1[k++]=array[j++];
            }
        }
        while(i<=m) {
            array1[k++]=array[i++];
        }
        while(j<=t) {
            array1[k++]=array[j++];
        }
        //合并完毕后更新辅助数组的值
        for(int z=s;z<=t;z++) {
            array[z]=array1[z];
        }
    }
    
    static void mergesort(int array[],int array1[],int s,int t) {
        if(s==t) {
            array1[s]=array[s];
        }
        else {
            int m=(s+t)/2;    //折半
            mergesort(array,array1,s,m);    //合并前半段
            mergesort(array,array1,m+1,t);    //合并后半段
            merge(array1,array,s,m,t);
        }
        
    }

    public static void main(string[] args) {
        scanner reader=new scanner(system.in);
        system.out.print("input the size of array:");
        int n=reader.nextint();
        int array[]=new int[n];
        int array1[]=new int[n];    //辅助数组
        system.out.print("input the element of array:");
        for(int i=0;i<n;i++) {
            array[i]=reader.nextint();
        }
        mergesort(array,array1,0,n-1);
        for(int i=0;i<n;i++) {
            system.out.print(array[i]+" ");
        }
    }

}

15:56:29

2018-10-04