国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

【算法系列篇】分治-歸并

2年前作者：不能再留遺憾了分類：Toy博客閱讀(24)違法舉報

這篇具有很好參考價值的文章主要介紹了【算法系列篇】分治-歸并。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

【算法系列篇】分治-歸并,算法,算法,排序算法,數(shù)據(jù)結(jié)構(gòu),分治,歸并

前言

上一篇算法文章，我們介紹了分治-快排的算法，今天我將為大家分享關(guān)于分治的另外一種算法——歸并。

什么是歸并算法

【算法系列篇】分治-歸并,算法,算法,排序算法,數(shù)據(jù)結(jié)構(gòu),分治,歸并
歸并算法是一種常用的排序算法，它采用分治策略將待排序的數(shù)組分解為更小的子數(shù)組，然后逐步合并這些子數(shù)組以獲得最終的有序數(shù)組。歸并排序的主要思想是將兩個有序的子數(shù)組合并成一個有序的數(shù)組。

歸并算法通常包含以下步驟：

分解（Divide）：將待排序的數(shù)組遞歸地分解為規(guī)模更小的子數(shù)組，直到每個子數(shù)組只有一個元素或為空。
解決（Conquer）：通過遞歸地排序子數(shù)組，將其轉(zhuǎn)化為有序的子數(shù)組。這通常是通過繼續(xù)將子數(shù)組進(jìn)一步分解并排序的方式實現(xiàn)的。
合并（Merge）：將兩個有序的子數(shù)組合并成一個有序的數(shù)組。該步驟的實現(xiàn)方式是比較兩個子數(shù)組的元素，并按照順序合并到一個新的數(shù)組中，直到所有元素都被合并。

歸并排序的時間復(fù)雜度是O(nlogn)，其中n是待排序數(shù)組的長度。它的主要優(yōu)點包括：

穩(wěn)定性：歸并排序是一種穩(wěn)定的排序算法，即相等元素的相對順序不會被改變。
適用性：歸并排序適用于各種數(shù)據(jù)結(jié)構(gòu)，尤其在外部排序中，它對于大規(guī)模數(shù)據(jù)的排序效果明顯。

然而，歸并排序也存在一些缺點：

額外空間消耗：歸并排序需要額外的空間來存儲臨時的子數(shù)組和合并結(jié)果，這可能對內(nèi)存消耗造成一定影響。
遞歸調(diào)用：歸并排序的實現(xiàn)通常使用遞歸調(diào)用，對于大規(guī)模數(shù)據(jù)的排序可能導(dǎo)致遞歸深度增加，從而增加了額外的函數(shù)調(diào)用開銷。

總結(jié)而言，歸并排序是一種高效、穩(wěn)定的排序算法，通過分治策略將待排序的數(shù)組分解為更小的子數(shù)組，然后逐步合并這些子數(shù)組以獲得最終的有序數(shù)組。盡管歸并排序需要額外的空間和函數(shù)調(diào)用開銷，但它在實踐中被廣泛使用，特別適用于對大規(guī)模數(shù)據(jù)進(jìn)行排序。

1. 排序數(shù)組

https://leetcode.cn/problems/sort-an-array/

1.1 題目要求

給你一個整數(shù)數(shù)組 nums，請你將該數(shù)組升序排列。

示例 1：

輸入：nums = [5,2,3,1]
輸出：[1,2,3,5]

示例 2：

輸入：nums = [5,1,1,2,0,0]
輸出：[0,0,1,1,2,5]

提示：

1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104

class Solution {
    public int[] sortArray(int[] nums) {

    }
}

1.2 做題思路

不知道大家是否做過將兩個有序數(shù)組合并為一個有序數(shù)組，我們的歸并算法就是通過將兩個數(shù)組合并為一個有序數(shù)組來實現(xiàn)的。而歸并的思想就是就一整個數(shù)組從中間將數(shù)組分為兩個數(shù)組，然后再繼續(xù)將這兩個數(shù)組分別從中間分開，直到將這兩部分的數(shù)組分為只有一個元素的兩部分?jǐn)?shù)組，然后將這兩個數(shù)組通過合并兩個數(shù)組的操作來進(jìn)行合并，合并完成之后的數(shù)組就成為了一個有序的數(shù)組，然后繼續(xù)將這兩個有序的數(shù)組通過合并數(shù)組的操作繼續(xù)進(jìn)行合并，直到將這些數(shù)組合并為一個最大的數(shù)組。
【算法系列篇】分治-歸并,算法,算法,排序算法,數(shù)據(jù)結(jié)構(gòu),分治,歸并

【算法系列篇】分治-歸并,算法,算法,排序算法,數(shù)據(jù)結(jié)構(gòu),分治,歸并

1.3 Java代碼實現(xiàn)

class Solution {
    //因為每一次遞歸都需要創(chuàng)建臨時的數(shù)組來存儲兩個數(shù)組排序之后的結(jié)果，
    //每次都向申請內(nèi)存，速度會很慢
    //所以我們直接申請一個跟nums同樣大小的數(shù)組
    int[] tmp;
    public int[] sortArray(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        mergeSort(nums,0,n -1);
        return nums;
    }

    private void mergeSort(int[] nums, int left, int right) {
        //當(dāng)數(shù)組中只有一個元素或者區(qū)間不成立的時候，結(jié)束遞歸
        if(left >= right) return;
        int mid = left + (right - left) / 2;
        //先排序mid左右兩邊的數(shù)組，最后在將左右兩邊的有序數(shù)組進(jìn)行合并
        mergeSort(nums,left,mid);
        mergeSort(nums,mid + 1,right);

        int cur1 = left,cur2 = mid + 1,i = 0;
        while(cur1 <= mid && cur2 <= right) {
            tmp[i++] = nums[cur1] < nums[cur2] ? nums[cur1++] : nums[cur2++];
        }

        //處理沒到達(dá)數(shù)組結(jié)尾的數(shù)組
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];

        //將臨時排序之后數(shù)組的結(jié)果更新到我們原本的數(shù)組中
        for(int j = left; j <= right; j++) nums[j] = tmp[j - left];
    }
}

【算法系列篇】分治-歸并,算法,算法,排序算法,數(shù)據(jù)結(jié)構(gòu),分治,歸并

2. 數(shù)組中逆序?qū)?/h2>
https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/

2.1 題目要求

在數(shù)組中的兩個數(shù)字，如果前面一個數(shù)字大于后面的數(shù)字，則這兩個數(shù)字組成一個逆序?qū)?。輸入一個數(shù)組，求出這個數(shù)組中的逆序?qū)Φ目倲?shù)。

示例 1:

輸入: [7,5,6,4]
輸出: 5

限制：

0 <= 數(shù)組長度 <= 50000

class Solution {
    public int reversePairs(int[] nums) {

    }
}

2.2 做題思路

我們先來看看如何使用暴力解法來解決這個問題：用兩層循環(huán)來遍歷數(shù)組，i 從 0 開始，j 則從 i 的下一個位置開始，看 j 所指向的位置是否小于 i 所指的位置，如果是則逆序?qū)倲?shù)加一。這樣雖然簡單，但是時間復(fù)雜度達(dá)到了 O(N^2)，是跑不過去的，那么我們就需要對暴力解法進(jìn)行優(yōu)化，問題就在于我們該如何優(yōu)化呢？

這樣想，如果我們將數(shù)組分為兩個部分，先計算左邊部分的數(shù)組中的所有逆序?qū)Γ缓笥嬎阌疫叢糠謹(jǐn)?shù)組中的所有逆序?qū)?，最后在左邊?shù)組一次選擇一個數(shù)字，看右邊數(shù)組中是否元素能與左邊數(shù)組中的那個元素構(gòu)成逆序?qū)?，這樣的思路其實跟暴力解法是相同的，時間復(fù)雜度都是 O(N^2)，那么當(dāng)我們分別在左邊數(shù)組中和右邊數(shù)組中找到了符合的逆序?qū)Φ脑挘覀兪欠窨梢詫⑦@兩部分?jǐn)?shù)組進(jìn)行排序呢？當(dāng)進(jìn)行了排序之后，再分別在左邊數(shù)組中依次拿元素與右邊數(shù)組中的元素進(jìn)行比較，假設(shè)我們按照升序的方式進(jìn)行排序，當(dāng)左邊部分遇到比右邊數(shù)組部分大的元素的話，那么左邊數(shù)組部分從這個元素開始到左邊部分?jǐn)?shù)組結(jié)束的位置是否都大于右邊數(shù)組的該元素呢？
【算法系列篇】分治-歸并,算法,算法,排序算法,數(shù)據(jù)結(jié)構(gòu),分治,歸并
如果nums[cur1] < nums[cur2] 則繼續(xù)讓 cur1 向右移動，直到出現(xiàn)逆序?qū)Φ那闆r，這樣 cur1 和 cur2 指針都不用返回，就較少了很多的重復(fù)比較，使得時間復(fù)雜度提升為
O(N*logN)。

2.3 Java代碼實現(xiàn)

（1）升序方法

class Solution {
    int[] tmp;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        return mergeSort(nums,0,n-1);
    }

    private int mergeSort(int[] nums, int left, int right) {
        if(left >= right) return 0;
        int mid = left + (right - left) / 2;
        //統(tǒng)計逆序?qū)Φ臄?shù)量
        int ret = 0;
        //計算左邊數(shù)組中逆序?qū)Φ臄?shù)量
        ret += mergeSort(nums,left,mid);
        //計算右邊數(shù)組中逆序?qū)Φ臄?shù)量
        ret += mergeSort(nums,mid + 1,right);

        int cur1 = left, cur2 = mid + 1,i = 0;
        while(cur1 <= mid && cur2 <= right) {
            //當(dāng)nums[cur1] <= nums[cur2] 的時候，只需要進(jìn)行合并數(shù)組的操作
            if(nums[cur1] <= nums[cur2]) tmp[i++] = nums[cur1++];
            //當(dāng)nums[cur1] > nums[cur2] 的時候，需要更新逆序?qū)Φ臄?shù)量，同時也需要合并數(shù)組
            else {
                ret += mid - cur1 + 1;
                tmp[i++] = nums[cur2++];
            }
        }

        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];

        for(int j = left; j <= right; j++) nums[j] = tmp[j - left];

        return ret;
    }
}

【算法系列篇】分治-歸并,算法,算法,排序算法,數(shù)據(jù)結(jié)構(gòu),分治,歸并
（2）降序方法
我們也可以用降序排列的方式來實現(xiàn)歸并排序，只是當(dāng)使用降序的時候，需要在右邊數(shù)組中統(tǒng)計逆序?qū)Φ臄?shù)量，因為當(dāng)遇到 nums[cur1] > nums[cur2] 的時候，如果還是統(tǒng)計左邊數(shù)組 mid - cur1 + 1 作為逆序?qū)Φ臄?shù)量的話，那么當(dāng) cur2 向后移動的時候，再遇到 nums[cur1] > nums[cur2] 的時候就會出現(xiàn)重復(fù)的情況，所以當(dāng)我們以降序的方式排序的時候需要在右邊數(shù)組中統(tǒng)計逆序?qū)Φ臄?shù)量。
【算法系列篇】分治-歸并,算法,算法,排序算法,數(shù)據(jù)結(jié)構(gòu),分治,歸并

class Solution {
    int[] tmp;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        return mergeSort(nums,0,n-1);
    }

    private int mergeSort(int[] nums, int left, int right) {
        if(left >= right) return 0;
        int mid = left + (right - left) / 2;
        //統(tǒng)計逆序?qū)Φ臄?shù)量
        int ret = 0;
        //計算左邊數(shù)組中逆序?qū)Φ臄?shù)量
        ret += mergeSort(nums,left,mid);
        //計算右邊數(shù)組中逆序?qū)Φ臄?shù)量
        ret += mergeSort(nums,mid + 1,right);

        int cur1 = left, cur2 = mid + 1,i = 0;
        while(cur1 <= mid && cur2 <= right) {
            //當(dāng)nums[cur1] <= nums[cur2] 的時候，只需要進(jìn)行合并數(shù)組的操作
            if(nums[cur1] <= nums[cur2]) tmp[i++] = nums[cur2++];
            //當(dāng)nums[cur1] > nums[cur2] 的時候，需要更新逆序?qū)Φ臄?shù)量，同時也需要合并數(shù)組
            else {
                ret += right - cur2 + 1;
                tmp[i++] = nums[cur1++];
            }
        }

        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];

        for(int j = left; j <= right; j++) nums[j] = tmp[j - left];

        return ret;
    }
}

【算法系列篇】分治-歸并,算法,算法,排序算法,數(shù)據(jù)結(jié)構(gòu),分治,歸并

3. 計算右側(cè)小于當(dāng)前元素的個數(shù)

https://leetcode.cn/problems/count-of-smaller-numbers-after-self/description/

3.1 題目要求

給你一個整數(shù)數(shù)組 nums ，按要求返回一個新數(shù)組 counts 。數(shù)組 counts 有該性質(zhì)： counts[i] 的值是 nums[i] 右側(cè)小于 nums[i] 的元素的數(shù)量。

示例 1：

輸入：nums = [5,2,6,1]
輸出：[2,1,1,0] 
解釋：
5 的右側(cè)有 2 個更小的元素 (2 和 1)
2 的右側(cè)僅有 1 個更小的元素 (1)
6 的右側(cè)有 1 個更小的元素 (1)
1 的右側(cè)有 0 個更小的元素

示例 2：

輸入：nums = [-1]
輸出：[0]

示例 3：

輸入：nums = [-1,-1]
輸出：[0,0]

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104

class Solution {
    public List<Integer> countSmaller(int[] nums) {

    }
}

3.2 做題思路

這道題目跟上面的找逆序?qū)Φ臄?shù)量是類似的，逆序?qū)κ钦仪懊娴脑卮笥诤竺嬖氐膫€數(shù)，而這道題是需要找到數(shù)組中每個元素的之后的小于該元素的個數(shù)，也就是說這個題目返回的是多個數(shù)，而不是一個數(shù)。那么我們在使用分冶算法的過程中該如何記住對應(yīng)數(shù)字的下標(biāo)呢？因為在分冶的過程中加上排序，數(shù)組中元素的位置是不斷變化的，但是這道題目按順序返回數(shù)組中對用位置右邊部分大小小于該位置元素的數(shù)量，所以這道題目如何記住原本數(shù)組對應(yīng)元素的下標(biāo)是很重要的。

那么我們?nèi)绾斡涀≡緮?shù)組元素的對應(yīng)下標(biāo)呢？我們可以創(chuàng)建一個 index 數(shù)組，當(dāng)數(shù)組進(jìn)行合并排序的時候，相應(yīng)的 index 數(shù)組也跟著變化，這樣就能使排序后數(shù)組對應(yīng)位置的 index 數(shù)組中存放的是原本數(shù)組的下標(biāo)。

【算法系列篇】分治-歸并,算法,算法,排序算法,數(shù)據(jù)結(jié)構(gòu),分治,歸并

3.3 Java代碼實現(xiàn)

class Solution {
    int[] ret; //該數(shù)組中存放右側(cè)小于當(dāng)前元素的個數(shù)
    int[] index; //存放對應(yīng)元素的下標(biāo)
    int[] tmpNums; //排序后的臨時數(shù)組
    int[] tmpIndex; //排序后對應(yīng)元素的原本下標(biāo)
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        ret = new int[n];
        index = new int[n];
        //index 數(shù)組初始化
        for(int i = 0; i < n; i++) index[i] = i;
        tmpNums = new int[n];
        tmpIndex = new int[n];
        mergerSort(nums,0,n-1);
        List<Integer> list = new ArrayList<>();
        for(int x : ret) list.add(x);
        return list;
    }

    private void mergerSort(int[] nums, int left, int right) {
        if(left >= right) return;
        int mid = left + (right - left) / 2;
        mergerSort(nums,left,mid);
        mergerSort(nums,mid + 1,right);
        int cur1 = left, cur2 = mid + 1, i = 0;
        //降序
        while(cur1 <= mid && cur2 <= right) {
            if(nums[cur1] <= nums[cur2]) {
                tmpNums[i] = nums[cur2];
                tmpIndex[i++] = index[cur2++];
            }else {
            //因為前面的遞歸中可能出現(xiàn)了右側(cè)小于當(dāng)前位置的數(shù)，所以需要使用+=
                ret[index[cur1]] += right - cur2 + 1;
                tmpNums[i] = nums[cur1];
                tmpIndex[i++] = index[cur1++];
            }
        }

        while(cur1 <= mid) {
            tmpNums[i] = nums[cur1];
            tmpIndex[i++] = index[cur1++];
        }
        while(cur2 <= right) {
            tmpNums[i] = nums[cur2];
            tmpIndex[i++] = index[cur2++];
        }

        for(int j = left; j <= right; j++) {
            nums[j] = tmpNums[j - left];
            index[j] = tmpIndex[j - left];
        }
    } 
}

【算法系列篇】分治-歸并,算法,算法,排序算法,數(shù)據(jù)結(jié)構(gòu),分治,歸并

4. 翻轉(zhuǎn)對

https://leetcode.cn/problems/reverse-pairs/description/

4.1 題目要求

給定一個數(shù)組 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我們就將 (i, j) 稱作一個重要翻轉(zhuǎn)對。

你需要返回給定數(shù)組中的重要翻轉(zhuǎn)對的數(shù)量。

示例 1:

輸入: [1,3,2,3,1]
輸出: 2

示例 2:

輸入: [2,4,3,5,1]
輸出: 3

注意:

給定數(shù)組的長度不會超過50000。
輸入數(shù)組中的所有數(shù)字都在32位整數(shù)的表示范圍內(nèi)。

class Solution {
    public int reversePairs(int[] nums) {

    }
}

4.2 做題思路

這個題目跟前面的的兩個題目都是類似的，只是這里不能在我們更新翻轉(zhuǎn)對的時候就進(jìn)行排序，因為翻轉(zhuǎn)對的判斷條件是 i < j 且 nums[i] > 2*nums[j]，根據(jù)這個判斷條件，我們不能判斷出 nums[i] 和 nums[j] 哪個大，所以只能在更新完翻轉(zhuǎn)對之后進(jìn)行歸并排序，其他的步驟基本上是類似的。
【算法系列篇】分治-歸并,算法,算法,排序算法,數(shù)據(jù)結(jié)構(gòu),分治,歸并

4.3 Java代碼實現(xiàn)

（1）升序

class Solution {
    int[] tmp;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        return mergeSort(nums,0,n-1);
    }

    private int mergeSort(int[] nums, int left, int right) {
        if(left >= right) return 0;
        int ret = 0;
        int mid = left + (right - left) / 2;
        //統(tǒng)計左右兩部分?jǐn)?shù)組中翻轉(zhuǎn)對的數(shù)量
        ret += mergeSort(nums,left,mid);
        ret += mergeSort(nums,mid + 1,right);
        int cur1 = left, cur2 = mid + 1, i = 0;
        while(cur2 <= right) {
        //這里需要使用nums[cur1] / 2.0 而不是nums[cur2] * 2，
        //因為可能會導(dǎo)致溢出
            while(cur1 <= mid && nums[cur1] / 2.0 <= nums[cur2]) cur1++;
            if(cur1 > mid) break;
            ret += mid - cur1 + 1;
            cur2++;
        }

		//升序
        cur1 = left;
        cur2 = mid + 1;
        while(cur1 <= mid && cur2 <= right) {
            tmp[i++] = nums[cur1] < nums[cur2] ? nums[cur1++] : nums[cur2++];
        }

        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];

        for(int j = left; j <= right; j++) nums[j] = tmp[j - left];

        return ret;
    }
}

【算法系列篇】分治-歸并,算法,算法,排序算法,數(shù)據(jù)結(jié)構(gòu),分治,歸并

（2）降序

class Solution {
    int[] tmp;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        return mergeSort(nums,0,n-1);
    }

    private int mergeSort(int[] nums, int left, int right) {
        if(left >= right) return 0;
        int ret = 0;
        int mid = left + (right - left) / 2;
        ret += mergeSort(nums,left,mid);
        ret += mergeSort(nums,mid + 1,right);
        int cur1 = left, cur2 = mid + 1, i = 0;
        //降序
        while(cur1 <= mid) {
        //這里cur1不動，因為cur1向后移動只會越來越小，所以讓cur2向后移動
            while(cur2 <= right && nums[cur1] / 2.0 <= nums[cur2]) cur2++;
            if(cur2 > right) break;
            ret += right - cur2 + 1;
            cur1++;
        }

        cur1 = left;
        cur2 = mid + 1;
        while(cur1 <= mid && cur2 <= right) {
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur2++] : nums[cur1++];
        }

        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];

        for(int j = left; j <= right; j++) nums[j] = tmp[j - left];

        return ret;
    }
}

【算法系列篇】分治-歸并,算法,算法,排序算法,數(shù)據(jù)結(jié)構(gòu),分治,歸并

總結(jié)

歸并排序是一種高效而穩(wěn)定的排序算法，它利用了分治策略，將待排序的數(shù)組分解為更小的子數(shù)組，并逐步合并這些子數(shù)組以獲得最終的有序數(shù)組。

歸并排序算法的核心思想是將待排序數(shù)組遞歸地分解為規(guī)模更小、有序的子數(shù)組，然后通過合并操作將這些子數(shù)組有序地合并成一個大的有序數(shù)組。這種分解和合并的過程直到最終合并成排序后的完整數(shù)組。

歸并排序算法具有以下優(yōu)點：

穩(wěn)定性：歸并排序是一種穩(wěn)定的排序算法，即相等元素的相對順序不會被改變。這使得它特別適用于對具有多關(guān)鍵字排序要求的情況。
高效性：歸并排序的時間復(fù)雜度為O(nlogn)，其中n是待排序數(shù)組的長度。它具有較好的性能表現(xiàn)，并適用于大規(guī)模數(shù)據(jù)的排序。

此外，歸并排序算法還具有一定的彈性和靈活性。它可以通過優(yōu)化合并操作的實現(xiàn)方式，減少額外空間的消耗。此外，歸并排序也適用于外部排序，可以處理存儲在外部存儲介質(zhì)中的大規(guī)模數(shù)據(jù)。

盡管歸并排序算法需要額外的空間和函數(shù)調(diào)用開銷，但由于其穩(wěn)定性和較好的時間復(fù)雜度，它在實際應(yīng)用中被廣泛采用。文章來源地址http://www.zghlxwxcb.cn/news/detail-697925.html

到了這里，關(guān)于【算法系列篇】分治-歸并的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處：如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實不符，請點擊違法舉報進(jìn)行投訴反饋，一經(jīng)查實，立即刪除！

分享到：

領(lǐng)支付寶紅包贊助服務(wù)器費用

數(shù)據(jù)結(jié)構(gòu)與算法：歸并排序
在講解歸并排序前，我們先看到一個問題：對于這樣兩個有序的數(shù)組，如何將它們合并為一個有序的數(shù)組？在此我們處理這個問題的思路就是：開辟一個新的數(shù)組，然后分別安置一個指針在左右數(shù)組，利用指針遍歷數(shù)組，每次對比將比較小的那個元素插入到數(shù)組的尾部。像
2024年01月21日
瀏覽(34)
python算法與數(shù)據(jù)結(jié)構(gòu)---排序和歸并排序
掌握歸并排序的基本原理使用python語言解答歸并排序題目原理及過程將兩個有序的數(shù)組合并成一個有序數(shù)組稱為從上往下分解：把當(dāng)前區(qū)間一分為二，直至分解為若干個長度為1的子數(shù)組從上往下的合并：兩個有序的子區(qū)域兩兩向上合并；體現(xiàn)了分治思想，穩(wěn)定排序復(fù)雜
2024年01月21日
瀏覽(44)
【數(shù)據(jù)結(jié)構(gòu)】排序算法（二）—＞冒泡排序、快速排序、歸并排序、計數(shù)排序
?? 樊梓慕：個人主頁 ??? 個人專欄：《C語言》《數(shù)據(jù)結(jié)構(gòu)》《藍(lán)橋杯試題》《LeetCode刷題筆記》《實訓(xùn)項目》 ?? 每一個不曾起舞的日子，都是對生命的辜負(fù) 目錄前言 1.冒泡排序 2.快速排序 2.1Hoare版 2.2占坑版 2.3前后指針版 2.4三數(shù)取中對快速排序的優(yōu)化 2.5非遞歸版 3.歸
2024年02月08日
瀏覽(34)
【數(shù)據(jù)結(jié)構(gòu)與算法】：非遞歸實現(xiàn)快速排序、歸并排序
?? 個人主頁： Quitecoder ?? 專欄：數(shù)據(jù)結(jié)構(gòu)與算法上篇文章我們詳細(xì)講解了遞歸版本的快速排序，本篇我們來探究非遞歸實現(xiàn)快速排序和歸并排序快速排序的非遞歸實現(xiàn)主要依賴于棧（stack）來模擬遞歸過程中的函數(shù)調(diào)用棧。遞歸版本的快速排序通過遞歸調(diào)用自身來處理子
2024年03月24日
瀏覽(25)
[數(shù)據(jù)結(jié)構(gòu) -- 手撕排序算法第七篇] 遞歸實現(xiàn)歸并排序
目錄 1、歸并的思想 2、歸并排序的思想 2.1 基本思想 2.2 圖解分析 3、歸并排序遞歸版本代碼實現(xiàn) 3.1 代碼解析 3.2 注意事項 3.2.1錯誤劃分：[begin, mid-1]，[mid, end] 3.2.2 正確劃分：[begin, mid], [mid+1, end] 4、歸并排序的測試 5、時間復(fù)雜度、空間復(fù)雜度分析 5.1 時間復(fù)雜度 5.2 空間復(fù)雜
2024年02月16日
瀏覽(37)
【一起學(xué)數(shù)據(jù)結(jié)構(gòu)與算法】幾種常見的排序(插入排序、選擇排序、交換排序、歸并排序)
排序是計算機內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組 “無序” 的記錄序列調(diào)整為 “有序” 的記錄序列。分內(nèi)部排序和外部排序，若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序。反之，若參加排序的記錄數(shù)量很大，整個序列的排序過程不可能
2023年04月09日
瀏覽(33)
【Java數(shù)據(jù)結(jié)構(gòu)與算法】Day2-高級排序（希爾、歸并、快速、計數(shù)）
?作者簡介：熱愛Java后端開發(fā)的一名學(xué)習(xí)者，大家可以跟我一起討論各種問題喔。 ??個人主頁：Hhzzy99 ??個人信條：堅持就是勝利！ ??當(dāng)前專欄：【Java數(shù)據(jù)結(jié)構(gòu)與算法】 ??本文內(nèi)容：Java數(shù)據(jù)結(jié)構(gòu)與算法中的比較高級的排序，希爾排序、歸并排序、快速排序、計數(shù)排序
2024年02月02日
瀏覽(34)
【數(shù)據(jù)結(jié)構(gòu)】- 排序（詳細(xì)介紹幾種排序算法?。。?直接插入排序，*希爾排序，*選擇排序，*堆排序，*冒泡排序，*快速排序，*歸并排序）
排序無處不在，所謂排序，就是使一串記錄，按照其中的某個或某些的大小，遞增或遞減的排列起來的操作。內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序。外部排序：數(shù)據(jù)元素太多不能同時放在內(nèi)存中，根據(jù)排序過程的要求不能在內(nèi)外存之間移動數(shù)據(jù)的排序。今天
2024年01月20日
瀏覽(57)
【算法與數(shù)據(jù)結(jié)構(gòu)】歸并排序的代碼實現(xiàn)（詳細(xì)圖解）以及master公式的講解
目錄 1、歸并排序 ?1.1、算法描述 ?1.2、圖解說明 2、代碼實現(xiàn)? 3、master公式 3.1、公式以及結(jié)論 3.2、適用于某些特殊的遞歸 3.3、計算歸并排序的時間復(fù)雜度歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用遞歸或者說是分治法（Divide and Conquer）的一個非
2024年02月08日
瀏覽(36)
【數(shù)據(jù)結(jié)構(gòu)與算法】萬字剖析八大排序(直接插入排序、希爾排序、選擇排序、堆排序、冒泡排序、快速排序、歸并排序、計數(shù)排序)
初窺直接插入排序我們先來看一張動圖: 由動圖我們可以分析出直接插入排序是從第二個數(shù)據(jù)開始遍歷，與前面的數(shù)據(jù)進(jìn)行比較如果小于則讓前面的數(shù)據(jù)向前移動自己接著向前面的數(shù)據(jù)比較直到比較到大于等于自己的數(shù)據(jù)或者沒有數(shù)據(jù)能進(jìn)行比較時停止插入當(dāng)前的位
2023年04月13日
瀏覽(107)