MergeSort 归并排序（java）

MergeSort 归并排序

排序思想：1，分解待排序的n个元素为两个子列，各为n/2个元素

		  2，若子列没有排好序，重复1步骤，每个子列继续分解为两个子列，直至被分解的子列个数为1

		  3，子列元素个数为1，说明这个子列已经排好序，开始逐级合并子序列进行排序

该算法需要合并分解的子序列，所以需要额外一个辅助过程Merge(A,p,q,r)来完成两个子列的合并，A为数组，p,q,r为数组下标，其中A[p,q]和A[q+1,r]为两个已经排好序的子序列，∞代表哨兵值。

Merge伪代码：

	Merge(A,p,q,r)

	n1 = q - p + 1

	n2 = r - q

	let L[1..n1+1] and R[1..n2+1] be new arrays

	for i = 1 to n1

		L[i] = A[p+i-1]

	for j = 1 to n2

		R[j] = a[q+j]

	L[n1+1] = ∞

	R[n2+1] = ∞

	i = 1

	j = 1

	for k = p to r

		if L[i] <=R[j]

			A[k] = L[i]

			i = i + 1

		else

			A[k] = R[j]

			j = j + 1

MergeSort(归并排序)伪代码:

	MergeSort(A,p,r)

	if p < r

		q = (p+r)/2

		MergeSort(A,p,q)

		MergeSort(A,q+1,r)

		Merge(A,p,q,r)

public class MergeSort{

    public static void main(String[] args) {

        int A[] = {

            1,6,4,5,2,9,7,23,56,43,98,56

        };

        int[] temp = new int[A.length];

        MergeSort(A,temp,0,A.length-1);

        for (int i:A){

            System.out.print(i+" ");

        }

    }

    public static void MergeSort(int[] A,int[] temp,int start,int end){

        if (start<end){

            int mid = (start+end)/2;

            //把数组分解为两个子列

            MergeSort(A,temp,start,mid);

            MergeSort(A,temp,mid+1,end);

            //逐级合并两个子列

            Merge(A,temp,start,mid,end);

        }

    }

    public static void Merge(int[] A,int[] temp,int start,int mid,int end){

        int i = start;

        int j = mid+1;

        int k = 0;

        while(i<=mid&&j<=end){

            if (A[i]<=A[j]) {

                temp[k] = A[i];

                i++;

                k++;

            }else {

                temp[k] = A[j];

                j++;

                k++;

            }

        }

        while(i<=mid){

            temp[k] = A[i];

            k++;

            i++;

        }

        while(j <= end){

            temp[k] = A[j];

            k++;

            j++;

        }

        for (int m = 0; m<k; m++) {

            A[start+m] = temp[m];

        }

    }

}

巴特西

MergeSort 归并排序（java）

最新文章

热门文章