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

更新時間：2023年09月13日 09:48:07 作者：我的頭發(fā)哪去了

分治算法是一種遞歸算法,它將問題劃分為幾個獨立的子問題,然后遞歸地解決這些子問題,最后將子問題的解合并起來得到原問題的解,本文詳細的介紹java分治算法,感興趣的可以了解一下

分治算法是一種遞歸算法，它將問題劃分為幾個獨立的子問題，然后遞歸地解決這些子問題，最后將子問題的解合并起來得到原問題的解。分治算法常用于解決計算幾何、統(tǒng)計學(xué)以及數(shù)值分析等領(lǐng)域的問題。

以歸并排序為例說明分治算法的思想和實現(xiàn)過程。

歸并排序的基本思想是將一個數(shù)組劃分為兩個子數(shù)組，然后遞歸地對這兩個子數(shù)組進行排序，并且將這兩個有序的子數(shù)組合并成一個有序的數(shù)組。

分

將數(shù)組劃分為兩個子數(shù)組

public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid); // 對左半部分進行遞歸排序
        mergeSort(arr, mid + 1, right); // 對右半部分進行遞歸排序
        merge(arr, left, mid, right); // 合并左右兩個有序的子數(shù)組
    }
}

治

遞歸地對左右兩個子數(shù)組進行排序

合

將兩個有序的子數(shù)組合并為一個有序的數(shù)組

public static void merge(int[] arr, int left, int mid, int right) {
    int[] tmp = new int[right - left + 1]; // 臨時數(shù)組
    int i = left; // 左半部分數(shù)組的起始下標
    int j = mid + 1; // 右半部分數(shù)組的起始下標
    int k = 0; // 臨時數(shù)組的起始下標
    // 將左右兩個有序的子數(shù)組合并為一個有序的數(shù)組
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            tmp[k++] = arr[i++];
        } else {
            tmp[k++] = arr[j++];
        }
    }
    // 將左半部分的剩余元素復(fù)制到臨時數(shù)組中
    while (i <= mid) {
        tmp[k++] = arr[i++];
    }
    // 將右半部分的剩余元素復(fù)制到臨時數(shù)組中
    while (j <= right) {
        tmp[k++] = arr[j++];
    }
    // 將臨時數(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); // 對左半部分進行遞歸排序
            mergeSort(arr, mid + 1, right); // 對右半部分進行遞歸排序
            merge(arr, left, mid, right); // 合并左右兩個有序的子數(shù)組
        }
    }
    public static void merge(int[] arr, int left, int mid, int right) {
        int[] tmp = new int[right - left + 1]; // 臨時數(shù)組
        int i = left; // 左半部分數(shù)組的起始下標
        int j = mid + 1; // 右半部分數(shù)組的起始下標
        int k = 0; // 臨時數(shù)組的起始下標
        // 將左右兩個有序的子數(shù)組合并為一個有序的數(shù)組
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                tmp[k++] = arr[i++];
            } else {
                tmp[k++] = arr[j++];
            }
        }
        // 將左半部分的剩余元素復(fù)制到臨時數(shù)組中
        while (i <= mid) {
            tmp[k++] = arr[i++];
        }
        // 將右半部分的剩余元素復(fù)制到臨時數(shù)組中
        while (j <= right) {
            tmp[k++] = arr[j++];
        }
        // 將臨時數(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代碼實現(xiàn)分治算法的文章就介紹到這了,更多相關(guān)java 分治算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: