您好,登錄后才能下訂單哦!
本篇內(nèi)容介紹了“Java中歸并排序算法的原理是什么及如何實(shí)現(xiàn)”的有關(guān)知識(shí),在實(shí)際案例的操作過(guò)程中,不少人都會(huì)遇到這樣的困境,接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧!希望大家仔細(xì)閱讀,能夠?qū)W有所成!
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法(Divide and Conquer)的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并,得到完全有序的序列;即先使每個(gè)子序列有序,再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表,稱為2-路歸并。
把長(zhǎng)度為n的輸入序列分成兩個(gè)長(zhǎng)度為n/2的子序列;對(duì)這兩個(gè)子序列分別采用歸并排序;將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列。
(1)、現(xiàn)在我們將拆分項(xiàng) [1] (指數(shù)從 0 到 0,兩邊都包括) 和 [28] 指數(shù)從 1 到 1 ,兩邊都包括) 歸并在一起。
(2)、因?yàn)?1 (左拆分) <= 28 (右拆分), 我們將 {rightPart} 拷進(jìn)新的數(shù)組。
(3)、因?yàn)樽蟛鸱质强盏?,我們?28 (右拆分)拷進(jìn)新的數(shù)組。
(4)、我們將新數(shù)組中的元素拷貝回原來(lái)的數(shù)組中。
(5)、因?yàn)?3 (左拆分) <= 21 (右拆分), 我們將 {rightPart} 拷進(jìn)新的數(shù)組。
(6)、因?yàn)樽蟛鸱质强盏?,我們?21 (右拆分)拷進(jìn)新的數(shù)組。
(7)、現(xiàn)在我們將拆分項(xiàng) [1,28] (指數(shù)從 0 到 1,兩邊都包括) 和 [3,21] 指數(shù)從 2 到 3 ,兩邊都包括) 歸并在一起。
(8)、因?yàn)?1 (左拆分) <= 3 (右拆分), 我們將 {rightPart} 拷進(jìn)新的數(shù)組。
(9)、因?yàn)?28 (左拆分) > 3 (右拆分), 我們將 {rightPart} 拷進(jìn)新的數(shù)組。
(10)、因?yàn)?28 (左拆分) > 21 (右拆分), 我們將 {rightPart} 拷進(jìn)新的數(shù)組。
(11)、因?yàn)橛也鸱质强盏?,我們?8 (左拆分) 拷貝進(jìn)新的數(shù)組。
(12)、我們將新數(shù)組中的元素拷貝回原來(lái)的數(shù)組中。
(13)、現(xiàn)在我們將拆分項(xiàng) [11] (指數(shù)從 4 到 4,兩邊都包括) 和 [7] 指數(shù)從 5 到 5 ,兩邊都包括) 歸并在一起。
(14)、因?yàn)?11 (左拆分) > 7 (右拆分), 我們將 {rightPart} 拷進(jìn)新的數(shù)組。
(15)、因?yàn)橛也鸱质强盏?,我們?1 (左拆分) 拷貝進(jìn)新的數(shù)組。
(16)、我們將新數(shù)組中的元素拷貝回原來(lái)的數(shù)組中。
(17)、以此類推
(18)、因?yàn)?1 (左拆分) <= 6 (右拆分), 我們將 {rightPart} 拷進(jìn)新的數(shù)組。
(19)、因?yàn)?3 (左拆分) <= 6 (右拆分), 我們將 {rightPart} 拷進(jìn)新的數(shù)組。
(20)、因?yàn)?21 (左拆分) > 6 (右拆分), 我們將 {rightPart} 拷進(jìn)新的數(shù)組。
(21)、因?yàn)?21 (左拆分) > 7 (右拆分), 我們將 {rightPart} 拷進(jìn)新的數(shù)組。
(22)、以此類推,我們將新數(shù)組中的元素拷貝回原來(lái)的數(shù)組中。
package com.algorithm.tenSortingAlgorithm; import java.util.Arrays; public class MergeSort { private static void mergeSort(int[] arr, int low, int high) { if (low < high) { //當(dāng)子序列中只有一個(gè)元素時(shí)結(jié)束遞歸 int mid = (low + high) / 2; //劃分子序列 mergeSort(arr, low, mid); //對(duì)左側(cè)子序列進(jìn)行遞歸排序 mergeSort(arr, mid + 1, high); //對(duì)右側(cè)子序列進(jìn)行遞歸排序 merge(arr, low, mid, high); //合并 } } private static void merge(int[] arr, int low, int mid, int high) { int[] temp = new int[arr.length]; //輔助數(shù)組 int k = 0, i = low, j = mid + 1; //i左邊序列和j右邊序列起始索引,k是存放指針 while (i <= mid && j <= high) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } //如果第一個(gè)序列未檢測(cè)完,直接將后面所有元素加到合并的序列中 while (i <= mid) { temp[k++] = arr[i++]; } //同上 while (j <= high) { temp[k++] = arr[j++]; } //復(fù)制回原數(shù)組 for (int t = 0; t < k; t++) { arr[low + t] = temp[t]; } } public static void main(String[] args) { int[] arr = {1,28,3,21,11,7,6,18}; mergeSort(arr, 0, arr.length - 1); System.out.println(Arrays.toString(arr)); } }
“Java中歸并排序算法的原理是什么及如何實(shí)現(xiàn)”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站,小編將為大家輸出更多高質(zhì)量的實(shí)用文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。