Algorithm - Merge Sort（Java）

浅浅的花香味﹌ 2022-05-22 00:19 125阅读 0赞

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

package chimomo.learning.java.algorithm.sort;
 
 import java.util.Arrays;
 
 /**
 * @author Chimomo
 *
 * 
 * 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.
 * 
 *
 * 
 * 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.
 * 
 *
 * 
 * Stability:
 *
 * Merge Sort is a stable sorting algorithm.
 * 
 */
 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]
 
 */

[http_www.captainbed.net]: http://www.captainbed.net/troubleshooter