欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

深入理解java代碼實(shí)現(xiàn)分治算法

 更新時(shí)間:2023年09月13日 09:48:07   作者:我的頭發(fā)哪去了  
分治算法是一種遞歸算法,它將問題劃分為幾個(gè)獨(dú)立的子問題,然后遞歸地解決這些子問題,最后將子問題的解合并起來得到原問題的解,本文詳細(xì)的介紹java分治算法,感興趣的可以了解一下

分治算法是一種遞歸算法,它將問題劃分為幾個(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)文章

  • springboot中生成文件路徑的問題及解決方法

    springboot中生成文件路徑的問題及解決方法

    這篇文章主要介紹了springboot中生成文件路徑的問題及解決方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2022-01-01
  • java發(fā)送http get請(qǐng)求的兩種方式

    java發(fā)送http get請(qǐng)求的兩種方式

    這篇文章主要為大家詳細(xì)介紹了java發(fā)送http get請(qǐng)求的兩種方式,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2017-05-05
  • Kafka中Producer和Consumer的作用詳解

    Kafka中Producer和Consumer的作用詳解

    這篇文章主要介紹了Kafka中Producer和Consumer的作用詳解,Kafka是一個(gè)分布式的流處理平臺(tái),它的核心是消息系統(tǒng),Producer是Kafka中用來將消息發(fā)送到Broker的組件之一,它將消息發(fā)布到主題,并且負(fù)責(zé)按照指定的分區(qū)策略將消息分配到對(duì)應(yīng)的分區(qū)中,需要的朋友可以參考下
    2023-12-12
  • spring security如何擴(kuò)展自定義登錄

    spring security如何擴(kuò)展自定義登錄

    本文詳細(xì)介紹了Spring Security的認(rèn)證原理和具體實(shí)現(xiàn),認(rèn)證原理基于過濾器鏈,通過驗(yàn)證用戶憑證和構(gòu)建認(rèn)證對(duì)象來保護(hù)應(yīng)用程序資源,實(shí)現(xiàn)自定義認(rèn)證功能的步驟包括創(chuàng)建自定義認(rèn)證提供程序、實(shí)現(xiàn)UserDetailsService接口以及在配置類中進(jìn)行相應(yīng)的配置
    2024-11-11
  • 關(guān)于Java中靜態(tài)代碼塊的執(zhí)行淺析

    關(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-09
  • springboot配置文件屬性變量引用方式${}和@@用法及區(qū)別說明

    springboot配置文件屬性變量引用方式${}和@@用法及區(qū)別說明

    這篇文章主要介紹了springboot配置文件屬性變量引用方式${}和@@用法及區(qū)別說明,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2022-03-03
  • 使用jdk1.8實(shí)現(xiàn)將list根據(jù)指定的值去分組的操作

    使用jdk1.8實(shí)現(xiàn)將list根據(jù)指定的值去分組的操作

    這篇文章主要介紹了使用jdk1.8實(shí)現(xiàn)將list根據(jù)指定的值去分組的操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
    2020-10-10
  • java 類加載與自定義類加載器詳解

    java 類加載與自定義類加載器詳解

    本文主要介紹了java 類加載與自定義類加載器。具有一定的參考價(jià)值,下面跟著小編一起來看下吧
    2017-01-01
  • mybatis的Configuration詳解

    mybatis的Configuration詳解

    這篇文章主要介紹了mybatis的Configuration詳解,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-11-11
  • 關(guān)于SpringSecurity?Context?中獲取和更改當(dāng)前用戶信息的問題

    關(guān)于SpringSecurity?Context?中獲取和更改當(dāng)前用戶信息的問題

    SpringSecurityContext在異步線程中無法獲取用戶信息,因其與請(qǐng)求線程綁定;此外,用戶信息更新后跳轉(zhuǎn)頁面時(shí),身份會(huì)被降級(jí)為匿名,導(dǎo)致信息無法及時(shí)同步,本文給大家介紹SpringSecurity?Context?中獲取和更改當(dāng)前用戶信息的問題,感興趣的朋友一起看看吧
    2024-09-09

最新評(píng)論