深入理解java代碼實(shí)現(xiàn)分治算法
分治算法是一種遞歸算法,它將問題劃分為幾個(gè)獨(dú)立的子問題,然后遞歸地解決這些子問題,最后將子問題的解合并起來得到原問題的解。分治算法常用于解決計(jì)算幾何、統(tǒng)計(jì)學(xué)以及數(shù)值分析等領(lǐng)域的問題。
以歸并排序?yàn)槔f明分治算法的思想和實(shí)現(xiàn)過程。
歸并排序的基本思想是將一個(gè)數(shù)組劃分為兩個(gè)子數(shù)組,然后遞歸地對(duì)這兩個(gè)子數(shù)組進(jìn)行排序,并且將這兩個(gè)有序的子數(shù)組合并成一個(gè)有序的數(shù)組。
- 分
將數(shù)組劃分為兩個(gè)子數(shù)組
public static void mergeSort(int[] arr, int left, int right) { if (left < right) { int mid = (left + right) / 2; mergeSort(arr, left, mid); // 對(duì)左半部分進(jìn)行遞歸排序 mergeSort(arr, mid + 1, right); // 對(duì)右半部分進(jìn)行遞歸排序 merge(arr, left, mid, right); // 合并左右兩個(gè)有序的子數(shù)組 } }
- 治
遞歸地對(duì)左右兩個(gè)子數(shù)組進(jìn)行排序
- 合
將兩個(gè)有序的子數(shù)組合并為一個(gè)有序的數(shù)組
public static void merge(int[] arr, int left, int mid, int right) { int[] tmp = new int[right - left + 1]; // 臨時(shí)數(shù)組 int i = left; // 左半部分?jǐn)?shù)組的起始下標(biāo) int j = mid + 1; // 右半部分?jǐn)?shù)組的起始下標(biāo) int k = 0; // 臨時(shí)數(shù)組的起始下標(biāo) // 將左右兩個(gè)有序的子數(shù)組合并為一個(gè)有序的數(shù)組 while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { tmp[k++] = arr[i++]; } else { tmp[k++] = arr[j++]; } } // 將左半部分的剩余元素復(fù)制到臨時(shí)數(shù)組中 while (i <= mid) { tmp[k++] = arr[i++]; } // 將右半部分的剩余元素復(fù)制到臨時(shí)數(shù)組中 while (j <= right) { tmp[k++] = arr[j++]; } // 將臨時(shí)數(shù)組中的元素復(fù)制回原數(shù)組中 for (int x = 0; x < k; x++) { arr[left + x] = tmp[x]; } }
完整代碼如下:
public class MergeSort { public static void mergeSort(int[] arr, int left, int right) { if (left < right) { int mid = (left + right) / 2; mergeSort(arr, left, mid); // 對(duì)左半部分進(jìn)行遞歸排序 mergeSort(arr, mid + 1, right); // 對(duì)右半部分進(jìn)行遞歸排序 merge(arr, left, mid, right); // 合并左右兩個(gè)有序的子數(shù)組 } } public static void merge(int[] arr, int left, int mid, int right) { int[] tmp = new int[right - left + 1]; // 臨時(shí)數(shù)組 int i = left; // 左半部分?jǐn)?shù)組的起始下標(biāo) int j = mid + 1; // 右半部分?jǐn)?shù)組的起始下標(biāo) int k = 0; // 臨時(shí)數(shù)組的起始下標(biāo) // 將左右兩個(gè)有序的子數(shù)組合并為一個(gè)有序的數(shù)組 while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { tmp[k++] = arr[i++]; } else { tmp[k++] = arr[j++]; } } // 將左半部分的剩余元素復(fù)制到臨時(shí)數(shù)組中 while (i <= mid) { tmp[k++] = arr[i++]; } // 將右半部分的剩余元素復(fù)制到臨時(shí)數(shù)組中 while (j <= right) { tmp[k++] = arr[j++]; } // 將臨時(shí)數(shù)組中的元素復(fù)制回原數(shù)組中 for (int x = 0; x < k; x++) { arr[left + x] = tmp[x]; } } public static void main(String[] args) { int[] arr = {5, 3, 9, 1, 7, 2, 8, 4, 6}; mergeSort(arr, 0, arr.length - 1); System.out.println(Arrays.toString(arr)); } }
輸出結(jié)果為:[1, 2, 3, 4, 5, 6, 7, 8, 9]
到此這篇關(guān)于深入理解java代碼實(shí)現(xiàn)分治算法的文章就介紹到這了,更多相關(guān)java 分治算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
java發(fā)送http get請(qǐng)求的兩種方式
這篇文章主要為大家詳細(xì)介紹了java發(fā)送http get請(qǐng)求的兩種方式,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2017-05-05關(guān)于Java中靜態(tài)代碼塊的執(zhí)行淺析
這篇文章主要給大家介紹了關(guān)于Java中靜態(tài)代碼塊執(zhí)行的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。2017-09-09springboot配置文件屬性變量引用方式${}和@@用法及區(qū)別說明
這篇文章主要介紹了springboot配置文件屬性變量引用方式${}和@@用法及區(qū)別說明,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-03-03使用jdk1.8實(shí)現(xiàn)將list根據(jù)指定的值去分組的操作
這篇文章主要介紹了使用jdk1.8實(shí)現(xiàn)將list根據(jù)指定的值去分組的操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-10-10關(guān)于SpringSecurity?Context?中獲取和更改當(dāng)前用戶信息的問題
SpringSecurityContext在異步線程中無法獲取用戶信息,因其與請(qǐng)求線程綁定;此外,用戶信息更新后跳轉(zhuǎn)頁面時(shí),身份會(huì)被降級(jí)為匿名,導(dǎo)致信息無法及時(shí)同步,本文給大家介紹SpringSecurity?Context?中獲取和更改當(dāng)前用戶信息的問題,感興趣的朋友一起看看吧2024-09-09