添加归并排序

byhieg · byhieg · commit 5a4753da6357 · 2017-06-18T17:03:55.000+08:00
diff --git a/src/main/java/cn/byhieg/algorithmtutorial/Sort.java b/src/main/java/cn/byhieg/algorithmtutorial/Sort.java
@@ -128,6 +128,59 @@ public void bubbleSort2(int[] nums) {
         }
     }
 
+    /**
+     * 归并排序，将数组一分为二，对于每一子数组继续进行上述步骤，直到子数组只有1个元素，那么自然是有序的。
+     * 然后不断合并两个数组，直到合并到整个数组。
+     * 时间复杂度o(NlgN)
+     * 空间复杂度o(N)
+     * @param nums
+     */
+    public void mergeSort(int[] nums) {
+        int length = nums.length;
+        int low = 0;
+        int high = length - 1;
+        realSort(nums, low, high);
+    }
+
+    /**
+     * 归并排序真正的sort函数
+     * @param nums 待排序的数组
+     * @param low 最低位
+     * @param high 最高位
+     */
+    private void realSort(int[] nums, int low, int high) {
+        int mid = (low + high) / 2;
+        if (low < high) {
+            realSort(nums, low, mid);
+            realSort(nums, mid + 1, high);
+            realMerge(nums, low, mid, high);
+        }
+    }
+
+    private void realMerge(int[] nums, int low, int mid, int high) {
+        int[] tmpNums = new int[high - low + 1];
+        int leftPoint = low;
+        int rightPoint = mid + 1;
+        int index = 0;
+
+        while (leftPoint <= mid && rightPoint <= high) {
+            if (nums[leftPoint] < nums[rightPoint]) {
+                tmpNums[index++] = nums[leftPoint++];
+            }else{
+                tmpNums[index++] = nums[rightPoint++];
+            }
+        }
+
+        while (leftPoint <= mid) {
+            tmpNums[index++] = nums[leftPoint++];
+        }
+        while (rightPoint <= high) {
+            tmpNums[index++] = nums[rightPoint++];
+        }
+
+        System.arraycopy(tmpNums, 0, nums, low, tmpNums.length);
+    }
+
     /**
      * 快速排序，选定一个切分元素，每一轮排序后，都保证切分元素之前的元素都小于切分元素，切分元素之后的元素都大于切分元素
      * 时间复杂度o(NlgN)
@@ -263,4 +316,5 @@ public void sink(int [] nums, int i,int n) {
     }
 
 
+
 }
diff --git a/src/test/java/cn/byhieg/algorithmtutorialtest/SortTest.java b/src/test/java/cn/byhieg/algorithmtutorialtest/SortTest.java
@@ -41,8 +41,13 @@ public void tearDown() throws Exception {
 //        new Sort().quickSort(nums);
 //    }
 
-    public void testHeapSort() throws Exception {
-        new Sort().heapSort(nums);
+//    public void testHeapSort() throws Exception {
+//        new Sort().heapSort(nums);
+//    }
+
+    public void testMergeSort() throws Exception {
+        new Sort().mergeSort(nums);
+
     }
 
 }

Original file line number	Diff line number	Diff line change
`@@ -41,8 +41,13 @@ public void tearDown() throws Exception {`
`41`	`41`	`// new Sort().quickSort(nums);`
`42`	`42`	`// }`
`43`	`43`
`44`		`- public void testHeapSort() throws Exception {`
`45`		`- new Sort().heapSort(nums);`
	`44`	`+// public void testHeapSort() throws Exception {`
	`45`	`+// new Sort().heapSort(nums);`
	`46`	`+// }`
	`47`	`+`
	`48`	`+ public void testMergeSort() throws Exception {`
	`49`	`+ new Sort().mergeSort(nums);`
	`50`	`+`
`46`	`51`	`}`
`47`	`52`
`48`	`53`	`}`