歸并排序的原理及java代碼實現(xiàn)
概述
歸并(Merge)排序法是將兩個(或兩個以上)有序表合并成一個新的有序表,即把待排序序列分為若干個子序列,每個子序列是有序的。然后再把有序子序列合并為整體有序序列。
歸并排序采用的是遞歸來實現(xiàn),屬于“分而治之”,將目標數(shù)組從中間一分為二,之后分別對這兩個數(shù)組進行排序,排序完畢之后再將排好序的兩個數(shù)組“歸并”到一起,歸并排序最重要的也就是這個“歸并”的過程,歸并的過程中需要額外的跟需要歸并的兩個數(shù)組長度一致的空間。
效果圖:
步驟
申請空間,使其大小為兩個已經(jīng)排序序列之和,該空間用來存放合并后的序列
設(shè)定兩個指針,最初位置分別為兩個已經(jīng)排序序列的起始位置
比較兩個指針所指向的元素,選擇相對小的元素放入到合并空間,并移動指針到下一位置
重復步驟3直到某一指針達到序列尾
將另一序列剩下的所有元素直接復制到合并序列尾
實例
原始數(shù)據(jù):
3 5 2 6 2
歸并的前提是將數(shù)組分開,一分為二,再一分為二,分到不能再分,進行歸并。
第一輪分隔,索引2 ((0+4)/2=2) 為中間
[3 5 2] [6 2]
第二輪分隔,對[3 5 2]進行分隔
[3 5] [2] [6 2]
第三輪分隔,對[3 5]進行分隔
[3] [5] [2] [6 2]
合并[3] [5]
[3 5] [2] [6 2]
合并[3 5] [2]
[2 3 5] [6 2]
第四輪分隔,對[6 2]進行分隔
[2 3 5] [6] [2]
合并[6] [2]
[2 3 5] [2 6]
合并[2 3 5] [2 6]
[2 2 3 5 6]
代碼實現(xiàn)(Java)
package com.coder4j.main.arithmetic.sorting; public class Merge { private static int mark = 0; /** * 歸并排序 * * @param array * @param low * @param high * @return */ private static int[] sort(int[] array, int low, int high) { int mid = (low + high) / 2; if (low < high) { mark++; System.out.println("正在進行第" + mark + "次分隔,得到"); System.out.println("[" + low + "-" + mid + "] [" + (mid + 1) + "-" + high + "]"); // 左邊數(shù)組 sort(array, low, mid); // 右邊數(shù)組 sort(array, mid + 1, high); // 左右歸并 merge(array, low, mid, high); } return array; } /** * 對數(shù)組進行歸并 * * @param array * @param low * @param mid * @param high */ private static void merge(int[] array, int low, int mid, int high) { System.out.println("合并:[" + low + "-" + mid + "] 和 [" + (mid + 1) + "-" + high + "]"); int[] temp = new int[high - low + 1]; int i = low;// 左指針 int j = mid + 1;// 右指針 int k = 0; // 把較小的數(shù)先移到新數(shù)組中 while (i <= mid && j <= high) { if (array[i] < array[j]) { temp[k++] = array[i++]; } else { temp[k++] = array[j++]; } } // 兩個數(shù)組之一可能存在剩余的元素 // 把左邊剩余的數(shù)移入數(shù)組 while (i <= mid) { temp[k++] = array[i++]; } // 把右邊邊剩余的數(shù)移入數(shù)組 while (j <= high) { temp[k++] = array[j++]; } // 把新數(shù)組中的數(shù)覆蓋array數(shù)組 for (int m = 0; m < temp.length; m++) { array[m + low] = temp[m]; } } /** * 歸并排序 * * @param array * @return */ public static int[] sort(int[] array) { return sort(array, 0, array.length - 1); } public static void main(String[] args) { int[] array = { 3, 5, 2, 6, 2 }; int[] sorted = sort(array); System.out.println("最終結(jié)果"); for (int i : sorted) { System.out.print(i + " "); } } }
測試輸出結(jié)果:
正在進行第1次分隔,得到 [0-2] [3-4] 正在進行第2次分隔,得到 [0-1] [2-2] 正在進行第3次分隔,得到 [0-0] [1-1] 合并:[0-0] 和 [1-1] 合并:[0-1] 和 [2-2] 正在進行第4次分隔,得到 [3-3] [4-4] 合并:[3-3] 和 [4-4] 合并:[0-2] 和 [3-4] 最終結(jié)果 2 2 3 5 6
經(jīng)測試,與實例中結(jié)果一致。
相關(guān)文章
Java中Runnable和Callable分別什么時候使用
提到 Java 就不得不說多線程了,就算你不想說,面試官也得讓你說呀,那說到線程,就不得不說Runnable和Callable這兩個家伙了,二者在什么時候使用呢,下面就來和簡單講講2023-08-08Mybatis實現(xiàn)查詢相冊數(shù)據(jù)列表流程講解
這篇文章主要介紹了Mybatis實現(xiàn)查詢相冊數(shù)據(jù)列表流程,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習吧2022-12-12JAVA初級項目——實現(xiàn)圖書管理系統(tǒng)
這篇文章主要介紹了JAVA如何實現(xiàn)圖書管理系統(tǒng),文中示例代碼非常詳細,供大家參考和學習,感興趣的朋友可以了解下2020-06-06Java常用HASH算法總結(jié)【經(jīng)典實例】
這篇文章主要介紹了Java常用HASH算法,結(jié)合實例形式總結(jié)分析了Java常用的Hash算法,包括加法hash、旋轉(zhuǎn)hash、FNV算法、RS算法hash、PJW算法、ELF算法、BKDR算法、SDBM算法、DJB算法、DEK算法、AP算法等,需要的朋友可以參考下2017-09-09