歸并排序的原理及java代碼實(shí)現(xiàn)
概述
歸并(Merge)排序法是將兩個(gè)(或兩個(gè)以上)有序表合并成一個(gè)新的有序表,即把待排序序列分為若干個(gè)子序列,每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。
歸并排序采用的是遞歸來(lái)實(shí)現(xiàn),屬于“分而治之”,將目標(biāo)數(shù)組從中間一分為二,之后分別對(duì)這兩個(gè)數(shù)組進(jìn)行排序,排序完畢之后再將排好序的兩個(gè)數(shù)組“歸并”到一起,歸并排序最重要的也就是這個(gè)“歸并”的過(guò)程,歸并的過(guò)程中需要額外的跟需要?dú)w并的兩個(gè)數(shù)組長(zhǎng)度一致的空間。
效果圖:
步驟
申請(qǐng)空間,使其大小為兩個(gè)已經(jīng)排序序列之和,該空間用來(lái)存放合并后的序列
設(shè)定兩個(gè)指針,最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
比較兩個(gè)指針?biāo)赶虻脑?,選擇相對(duì)小的元素放入到合并空間,并移動(dòng)指針到下一位置
重復(fù)步驟3直到某一指針達(dá)到序列尾
將另一序列剩下的所有元素直接復(fù)制到合并序列尾
實(shí)例
原始數(shù)據(jù):
3 5 2 6 2
歸并的前提是將數(shù)組分開(kāi),一分為二,再一分為二,分到不能再分,進(jìn)行歸并。
第一輪分隔,索引2 ((0+4)/2=2) 為中間
[3 5 2] [6 2]
第二輪分隔,對(duì)[3 5 2]進(jìn)行分隔
[3 5] [2] [6 2]
第三輪分隔,對(duì)[3 5]進(jìn)行分隔
[3] [5] [2] [6 2]
合并[3] [5]
[3 5] [2] [6 2]
合并[3 5] [2]
[2 3 5] [6 2]
第四輪分隔,對(duì)[6 2]進(jìn)行分隔
[2 3 5] [6] [2]
合并[6] [2]
[2 3 5] [2 6]
合并[2 3 5] [2 6]
[2 2 3 5 6]
代碼實(shí)現(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("正在進(jìn)行第" + 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; } /** * 對(duì)數(shù)組進(jìn)行歸并 * * @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++]; } } // 兩個(gè)數(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 + " "); } } }
測(cè)試輸出結(jié)果:
正在進(jìn)行第1次分隔,得到 [0-2] [3-4] 正在進(jìn)行第2次分隔,得到 [0-1] [2-2] 正在進(jìn)行第3次分隔,得到 [0-0] [1-1] 合并:[0-0] 和 [1-1] 合并:[0-1] 和 [2-2] 正在進(jìn)行第4次分隔,得到 [3-3] [4-4] 合并:[3-3] 和 [4-4] 合并:[0-2] 和 [3-4] 最終結(jié)果 2 2 3 5 6
經(jīng)測(cè)試,與實(shí)例中結(jié)果一致。
相關(guān)文章
mybatis-plus?分頁(yè)類(lèi)型轉(zhuǎn)換工具類(lèi)
用mybatis-plus?的分頁(yè)對(duì)象的時(shí)候,因?yàn)橛胢ybatis-puls?查詢(xún)出來(lái)的分頁(yè)對(duì)象的records里的泛型是實(shí)體,有時(shí)候需要將實(shí)體轉(zhuǎn)換為前端展示的對(duì)象,所有寫(xiě)了一個(gè)分頁(yè)數(shù)據(jù)的類(lèi)型轉(zhuǎn)換工具,解決這個(gè)問(wèn)題,對(duì)mybatis-plus?分頁(yè)工具類(lèi)相關(guān)知識(shí)感興趣的朋友一起看看吧2022-03-03Java Swing編寫(xiě)一個(gè)簡(jiǎn)單的計(jì)算器軟件
大家好,本篇文章主要講的是Java Swing編寫(xiě)一個(gè)簡(jiǎn)單的計(jì)算器軟件,感興趣的同學(xué)趕快來(lái)看一看吧,對(duì)你有幫助的話(huà)記得收藏一下,方便下次瀏覽2021-12-12Java中Runnable和Callable分別什么時(shí)候使用
提到 Java 就不得不說(shuō)多線(xiàn)程了,就算你不想說(shuō),面試官也得讓你說(shuō)呀,那說(shuō)到線(xiàn)程,就不得不說(shuō)Runnable和Callable這兩個(gè)家伙了,二者在什么時(shí)候使用呢,下面就來(lái)和簡(jiǎn)單講講2023-08-08淺析Java中為什么要設(shè)計(jì)包裝類(lèi)
我們知道Java是一個(gè)面相對(duì)象的編程語(yǔ)言,基本類(lèi)型并不具有對(duì)象的性質(zhì),為了讓基本類(lèi)型也具有對(duì)象的特征,就出現(xiàn)了包裝類(lèi)型,它相當(dāng)于將基本類(lèi)型“包裝起來(lái)”,使得它具有了對(duì)象的性質(zhì),并且為其添加了屬性和方法,豐富了基本類(lèi)型的操作2021-06-06Mybatis實(shí)現(xiàn)查詢(xún)相冊(cè)數(shù)據(jù)列表流程講解
這篇文章主要介紹了Mybatis實(shí)現(xiàn)查詢(xún)相冊(cè)數(shù)據(jù)列表流程,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)吧2022-12-12JAVA初級(jí)項(xiàng)目——實(shí)現(xiàn)圖書(shū)管理系統(tǒng)
這篇文章主要介紹了JAVA如何實(shí)現(xiàn)圖書(shū)管理系統(tǒng),文中示例代碼非常詳細(xì),供大家參考和學(xué)習(xí),感興趣的朋友可以了解下2020-06-06Java常用HASH算法總結(jié)【經(jīng)典實(shí)例】
這篇文章主要介紹了Java常用HASH算法,結(jié)合實(shí)例形式總結(jié)分析了Java常用的Hash算法,包括加法hash、旋轉(zhuǎn)hash、FNV算法、RS算法hash、PJW算法、ELF算法、BKDR算法、SDBM算法、DJB算法、DEK算法、AP算法等,需要的朋友可以參考下2017-09-09