coderhester
diff --git a/‎notes/algorithms/基础排序算法.md‎
Lines changed: 67 additions & 35 deletions b/‎notes/algorithms/基础排序算法.md‎
Lines changed: 67 additions & 35 deletions
diff --git a/‎notes/pictures/1557906108-5066-20161218163120151-452283750.png‎
244 KB b/‎notes/pictures/1557906108-5066-20161218163120151-452283750.png‎
244 KB
diff --git a/‎notes/pictures/mergeSort.gif‎
326 KB b/‎notes/pictures/mergeSort.gif‎
326 KB
diff --git a/‎src/main/java/com/bruis/algorithminjava/algorithm/sort/MergeSort.java‎
Lines changed: 70 additions & 0 deletions b/‎src/main/java/com/bruis/algorithminjava/algorithm/sort/MergeSort.java‎
Lines changed: 70 additions & 0 deletions
@@ -185,43 +185,75 @@ public class InsertionSort {
 
 #### 4. 归并排序
 
+归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
+
+作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
+
+- 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
+- 自下而上的迭代；
+
 ```
-//归并排序
-aux  [n...mid..mid+1..m]
-nums [a,b,c,d,e,f,g]
-
-
-private void merge(int[] nums, int left, int mid, int right) {
-	int[] aux = Arrays.copyOfRange(nums, left, right + 1);
-	int i = left, j = mid + 1;
-	for(int k = left; k <= right; k++) {
-		if(i > mid) {
-			nums[k] = aux[j - left];
-			j++;
-		} else if(j > right) {
-			nums[k] = aux[i - left];
-			i++;
-		} else if(aux[i - left] < aux[j - left]) {
-			nums[k] = aux[i - left];
-			i++;
-		} else {//aux[i-left] >= aux[j-left]
-			nums[k] = aux[j - left];
-			j++;
-		}
-	}
-}
-private void sort(int[] nums, int left, int right) {
-	if(left >= right) {
-		return;
-	}
-	int mid = (right - left) / 2 + left;
-	sort(nums, left, mid);
-	sort(nums, mid+1, right);
-	merge(nums, left, mid, right);
-}
-public void sort(int[] nums) {
-	sort(nums, 0, nums.length - 1);
+public class MergeSort {
+
+    /**
+     *
+     * 将arr[left...mid]和arr[mid+1...right]两部分进行归并
+     *
+     * @param arr
+     * @param left
+     * @param mid
+     * @param right
+     */
+    public static void merge(int[] arr, int left, int mid, int right) {
+        int[] aux = Arrays.copyOfRange(arr, left, right + 1);
+
+        // i表示左边；j表示右边；
+        int i = left, j = mid + 1;
+        // 从左left遍历到右right, 左闭又开
+        for (int k = left; k <= right; k++) {
+            // 如果左边指针大于mid，则表示左半边数据已经归并完毕
+            if (i > mid) {
+                // j-left计算出相对aux的位置
+                arr[k] = aux[j-left];
+                j++;
+            } else if (j > right) {
+                // j大于right值，则表示右半边数据已经归并完毕
+                arr[k] = aux[i-left];
+                i++;
+            } else if (aux[i-left] < aux[j-left]) {
+                arr[k] = aux[i-left];
+                i++;
+            } else {
+                arr[k] = aux[j-left];
+                j++;
+            }
+        }
+    }
+
+    /**
+     *
+     * 对[left, right]范围进行排序
+     *
+     * @param arr
+     * @param left
+     * @param right
+     */
+    public static void sort(int[] arr, int left, int right) {
+        if (left >= right) {
+            return;
+        }
+        int mid = (left + right) / 2;
+        sort(arr, left, mid);
+        sort(arr, mid + 1, right);
+        merge(arr, left, mid, right);
+    }
+
+    public static void sort(int[] arr) {
+        int n = arr.length;
+        sort(arr, 0, n-1);
+    }
 }
+
 ```
 
 
 
@@ -0,0 +1,70 @@
+package com.bruis.algorithminjava.algorithm.sort;
+
+import java.util.Arrays;
+
+/**
+ *
+ * 归并排序
+ *
+ * @author LuoHaiYang
+ */
+public class MergeSort {
+
+    /**
+     *
+     * 将arr[left...mid]和arr[mid+1...right]两部分进行归并
+     *
+     * @param arr
+     * @param left
+     * @param mid
+     * @param right
+     */
+    public static void merge(int[] arr, int left, int mid, int right) {
+        int[] aux = Arrays.copyOfRange(arr, left, right + 1);
+
+        // i表示左边；j表示右边；
+        int i = left, j = mid + 1;
+        // 从左left遍历到右right, 左闭又开
+        for (int k = left; k <= right; k++) {
+            // 如果左边指针大于mid，则表示左半边数据已经归并完毕
+            if (i > mid) {
+                // j-left计算出相对aux的位置
+                arr[k] = aux[j-left];
+                j++;
+            } else if (j > right) {
+                // j大于right值，则表示右半边数据已经归并完毕
+                arr[k] = aux[i-left];
+                i++;
+            } else if (aux[i-left] < aux[j-left]) {
+                arr[k] = aux[i-left];
+                i++;
+            } else {
+                arr[k] = aux[j-left];
+                j++;
+            }
+        }
+    }
+
+    /**
+     *
+     * 对[left, right]范围进行排序
+     *
+     * @param arr
+     * @param left
+     * @param right
+     */
+    public static void sort(int[] arr, int left, int right) {
+        if (left >= right) {
+            return;
+        }
+        int mid = (left + right) / 2;
+        sort(arr, left, mid);
+        sort(arr, mid + 1, right);
+        merge(arr, left, mid, right);
+    }
+
+    public static void sort(int[] arr) {
+        int n = arr.length;
+        sort(arr, 0, n-1);
+    }
+}