merge sort

今天家教差点被学生问倒了,好险!
赶紧复习一下归并排序!:

MERGE(A, p, q, r)
 1  n1 ← q – p + 1//修改为 n1 ← q – p
 2  n2 ← r – q    //修改 n2 ← r – q + 1
 3  create arrays L[1 ‥ n1 + 1] and R[1 ‥ n2 + 1]
 4  for i ← 1 to n1
 5       do L[i] ← A[p + i – 1]
 6  for j ← 1 to n2
 7       do R[j] ← A[q + j]
 8  L[n1 + 1] ← ∞
 9  R[n2 + 1] ← ∞
10  i ← 1
11  j ← 1
12  for k ← p to r
13       do if L[i] ≤ R[j]
14             then A[k] ← L[i]
15                  i ← i + 1
16             else A[k] ← R[j]
17                  j ← j + 1MERGE-SORT(A, p, r)
1 if p < r
2   then q ← (p + r)/2
3        MERGE-SORT(A, p, q)
4        MERGE-SORT(A, q + 1, r)
5        MERGE(A, p, q , r)//修改为MERGE(A, p, q + 1, r)

关键是merge方法,开两个新数组存放要合并的数,将两个数组的最后一个元素设为无穷大(便于比较和确保所有元素加入到原来数组)。
然后分别给两个数组设定游标,小的就加入数组,并且其游标往后移!当到最后一个元素时,就开始加另外一个数组的数字!(两个数组都是排序过的,所以顺序加入没有问题!)

public class MergeSortAlgorithm {
    final static int MAXVALUE = 10000;
    static int[] L;
    static int[] R;
    public static void Merge(int[] A, int p, int q, int r) {
        int n1 = q – p; //correct
        int n2 = r – q + 1; //correct
        //int n1 = q-p; 
        // int n2 = r – q;
        L = new int[n1 + 1];
        R = new int[n2 + 1];
        for (int i = 0; i < n1; i++) {
            L[i] = A[p + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = A[q + j];
        }
        L[n1] = MAXVALUE;
        R[n2] = MAXVALUE;
        int i = 0, j = 0;
        for (int k = p; k <= r; k++) {
            //for(int k = p; k < r ;k++)
            {
                if (L[i] <= R[j]) {
                    A[k] = L[i];
                    i++;
                } else {
                    A[k] = R[j];
                    j++;
                }
            }
        }
    }
        public static void MergeSort(int[] A, int p, int r) {
            int q;
            if (p < r) {
                q = (p + r) / 2;
                /*correctness*/
                MergeSort(A, p, q);
                MergeSort(A, q + 1, r);
                Merge(A, p, q + 1, r);
                /*test*/
                /*
                 MergeSort(A,p,q);
                  MergeSort(A,q,r);
                    Merge(A,p,q,r);*/
            }
        }
        public static void main(String[] args) {
            int[] inputArray = {1, 3, 2, 6, 5, 2, 4, 7, 1, 3, 2, 6, 5, 2, 4, 7,
                               1, 3, 2, 6, 5, 2, 4, 7, 1, 3};
            MergeSort(inputArray, 0, inputArray.length – 1);
            for (int i = 0; i < inputArray.length; i++) {
                System.out.println(“intArray[” + i + “]=” + inputArray[i]);
            }
        }
    }

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s