歸并排序思想

歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。 該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。 作為一種典型的分而治之思想的算法應(yīng)用，歸并排序的實(shí)現(xiàn)由兩種方法： * 自上而下的遞歸（所有遞歸的方法都可以用迭代重寫，所以就有了第 2 種方法）； * 自下而上的迭代；

一、劃分?

當(dāng)待排序數(shù)組 a[ ] 長度 a.length?>= 3時(shí)，將數(shù)組 a [ ] 從 cennter = ( a.length + 1 ) / 2?劃分為 left [ 0 ~ center-1 ] , right [ center ~ a.length ] 。

將劃分后的數(shù)組 left [ ] 和 right [ ] 合并。?

若數(shù)組a [ ] 長度a.length < 3,對(duì)該數(shù)組直接排序。

最后將處理后的數(shù)組返回。

劃分階段——sort（）函數(shù)進(jìn)行

?二、合并

初始化合并后的數(shù)組為 merge[ ] ,長度為 left.length + right.length 。變量 i ，j，k 初始為0

對(duì)上一步劃分的數(shù)組自底向上合并到merge [ ]。

i 掃描 left [ ] , j 掃描 right [ ] , k 掃描 merge [ ] 。將 left [ i ] 和 right [ j ] 的較小者加入 merge [ k ]。 if (left[i] < right[j]) {merge[k++] = left[i++];} else {merge[k++] = right[j++];}

當(dāng) i 或 j 掃描結(jié)束時(shí)，將剩下的一部分加入 merge [ ] 。 if (i == left.length) {while (j < right.length) {merge[k++] = right[j++];}} else if (j == right.length) {while (i < left.length) {merge[k++] = left[i++];}} 合并階段———merge（）函數(shù)進(jìn)行

?三、完整代碼?

import java.util.Arrays;/*** @author: pikachu* @description: 歸并排序* 歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。* 該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。* 作為一種典型的分而治之思想的算法應(yīng)用，歸并排序的實(shí)現(xiàn)由兩種方法：* 自上而下的遞歸（所有遞歸的方法都可以用迭代重寫，所以就有了第 2 種方法）；* 自下而上的迭代；* @date: 2022/7/29 21:21*/ public class Merge {private static int count=1;/*** Desc:** @param left 待合并數(shù)組左半部分* @param right 待合并數(shù)組右半部分* @return {@link int[]} 合并 left 和 right 后的有序數(shù)組* @author pikachu*/private static int[] merge(int[] left, int[] right) {int[] merge = new int[left.length + right.length];int i = 0;int j = 0;int k = 0;while (i < left.length && j < right.length) {if (left[i] < right[j]) {merge[k++] = left[i++];} else {merge[k++] = right[j++];}}if (i == left.length) {while (j < right.length) {merge[k++] = right[j++];}} else if (j == right.length) {while (i < left.length) {merge[k++] = left[i++];}}return merge;}public static int[] sort(int[] a) {int center = (a.length + 1) / 2;if (center > 1) { // 數(shù)組長度>=3// 分int[] left = Arrays.copyOfRange(a, 0, center); // 拷貝包首不包尾int[] right = Arrays.copyOfRange(a, center, a.length);left = sort(left);right = sort(right);// 治a = merge(left, right);System.out.println("第"+count+++"次合并:"+Arrays.toString(a));} else { // 數(shù)組長度<3if (a[0] > a[a.length - 1]) {int temp = a[0];a[0] = a[a.length - 1];a[a.length - 1] = temp;}}return a;} }class Test16 {public static void main(String[] args) { // int[] arr = new int[]{4, 2, 8, 3, 6, 9, 1, 22, 8, 11};int[] arr = new int[]{7, 6, 1, 1, 7, 6, 8, 3, 5, 7}; // int n = 10; // int[] arr = new int[n]; // int[] arr1 = new int[n]; // for (int i = 0; i < n; i++) { // arr[i] = (int) (Math.random() * n); // arr1[i] = (int) (Math.random() * n); // }System.out.println("歸并排序前:" + Arrays.toString(arr));long start = System.currentTimeMillis();arr = Merge.sort(arr);long end = System.currentTimeMillis();System.out.println("歸并排序后:" + Arrays.toString(arr));System.out.println("耗時(shí):" + (end - start) + "毫秒");// long start1 = System.currentTimeMillis(); // Quick quick = new Quick(); // quick.sort(arr1, 0, arr1.length - 1); // long end1 = System.currentTimeMillis(); // System.out.println("耗時(shí):" + (end1 - start1) + "毫秒");// System.out.println("quick.sort()排序后:" + Arrays.toString(arr1));} }

四、結(jié)果&&速度測試

結(jié)果測試

歸并排序與快速排序速度比較

總結(jié)

以上是生活随笔為你收集整理的归并排序——Java代码实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。