Algorithm - Merge Sort（Java）-蒲公英云

Algorithm - Merge Sort（Java）

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击http://www.captainbed.net

package chimomo.learning.java.algorithm.sort;
import java.util.Arrays;
/**
 * @author Chimomo
 *
 * <p>
 * Introduction:
 *
 * Merge Sort is built on Merge operation,
 * it is a typical application of "Divide and Conquer" strategy.
 * The sorting speed of Merge Sort is second only to Quick Sort,
 * Generally applied on the sequence
 * that overall unordered but relatively ordered on its subsequences.
 * </p>
 *
 * <p>
 * Algorithm:
 *
 * The principle of Merge operation:
 * 1. Apply for memory to store the merged sequence,
 *    its size equals to the sum of the two ordered sequences.
 * 2. Set two pointers,
 *    each points to the start position of the ordered sequence separately.
 * 3. Compare the elements the two pointers pointed,
 *    put the smaller one into merged sequence,
 *    and move the pointer to the next position.
 * 4. Repeat step 3 until one pointer exceeds the rear of the sequence.
 * 5. Copy the remaining elements of the other sequence
 *    to the rear of the merged sequence.
 *
 * The principle of Merge Sort (suppose sequence has n elements):
 * 1. Divide: divide n elements into 2 subsequences
 *    and each subsequence contains ceil(n/2) elements at most.
 * 2. Conquer: merge sort each subsequence recursively.
 * 3. Merge: merge the two ordered sequences into one ordered sequence.
 * </p>
 *
 * <p>
 * Stability:
 *
 * Merge Sort is a stable sorting algorithm.
 * </p>
 */
public class MergeSort {
    private MergeSort() {
    }
    /**
     * Merge Sort
     *
     * @param a The array to be sorted
     * @param low The low index of array a
     * @param high The high index of array a
     */
    private static void mergeSort(int[] a, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            mergeSort(a, low, mid);
            mergeSort(a, mid + 1, high);
            merge(a, low, mid, high);
            System.out.println(Arrays.toString(a));
        }
    }
    /**
     * The 2-way merge operation: merge two ordered sequences to one ordered sequence
     *
     * @param a The array to be merged
     * @param low The start subscript of the first ordered sequence
     * @param mid The end subscript of the first ordered sequence
     *            (so the start subscript of the second ordered sequence is "mid + 1")
     * @param high The end subscript of the second ordered sequence
     */
    private static void merge(int[] a, int low, int mid, int high) {
        // Apply for memory whose size is the sum of the two ordered sequences,
        // this memory stores the merged sequence.
        int[] tmp = new int[high - low + 1];
        // Set two pointers,
        // their initial values are the starting positions of the two ordered sequence.
        int i = low;
        int j = mid + 1;
        int k = 0;
        // Repeat the following operations until one pointer exceeds the rear of sequence:
        // Comparing the elements the two pointers pointed,
        // put the smaller one into the merged sequence,
        // and move the pointer to the next position.
        while (i <= mid && j <= high) {
            if (a[i] < a[j]) {
                tmp[k++] = a[i++];
            } else {
                tmp[k++] = a[j++];
            }
        }
        // Copy all the remaining elements of the other sequence to the rear of the merged sequence
        while (i <= mid) {
            tmp[k++] = a[i++];
        }
        while (j <= high) {
            tmp[k++] = a[j++];
        }
        // Copy the merged sequence back to a
        System.arraycopy(tmp, 0, a, low, tmp.length);
    }
    /**
     * Test program
     *
     * @param args The arguments
     */
    public static void main(String[] args) {
        int[] a = {11, 16, 22, -3, 99, 0, 16, 6, -1, 99};
        System.out.println("Before merge sort:");
        System.out.println(Arrays.toString(a));
        System.out.println("In merge sort:");
        MergeSort.mergeSort(a, 0, a.length - 1);
        System.out.println("After merge sort:");
        System.out.println(Arrays.toString(a));
    }
}
/* ------ Running Results ------
Before merge sort:
[11, 16, 22, -3, 99, 0, 16, 6, -1, 99]
In merge sort:
[11, 16, 22, -3, 99, 0, 16, 6, -1, 99]
[11, 16, 22, -3, 99, 0, 16, 6, -1, 99]
[11, 16, 22, -3, 99, 0, 16, 6, -1, 99]
[-3, 11, 16, 22, 99, 0, 16, 6, -1, 99]
[-3, 11, 16, 22, 99, 0, 16, 6, -1, 99]
[-3, 11, 16, 22, 99, 0, 6, 16, -1, 99]
[-3, 11, 16, 22, 99, 0, 6, 16, -1, 99]
[-3, 11, 16, 22, 99, -1, 0, 6, 16, 99]
[-3, -1, 0, 6, 11, 16, 16, 22, 99, 99]
After merge sort:
[-3, -1, 0, 6, 11, 16, 16, 22, 99, 99]
*/