學(xué)習(xí)目標(biāo)

• 掌握歸并排序的基本原理
• 使用python語言解答歸并排序題目

歸并排序

原理及過程

1. 將兩個(gè)有序的數(shù)組合并成一個(gè)有序數(shù)組稱為
2. 從上往下分解：把當(dāng)前區(qū)間一分為二，直至分解為若干個(gè)長度為1的子數(shù)組
3. 從上往下的合并：兩個(gè)有序的子區(qū)域兩兩向上合并；
4. 體現(xiàn)了分治思想，穩(wěn)定排序
   

復(fù)雜度

平均時(shí)間復(fù)雜度：O(NlogN)
最壞時(shí)間復(fù)雜度：O(NlogN)

歸并排序合并過程

• temp數(shù)組用于存儲合并結(jié)果，合并后拷貝回原數(shù)組；

• 雙指針法：

  • 初始分別指向兩個(gè)有序區(qū)間的開始位置；
  • 指針應(yīng)該如何移動(dòng)

• 當(dāng)合并左右兩個(gè)有序區(qū)間時(shí)，分為以下幾種情況；

  • 左區(qū)間、右區(qū)間都還有元素，且當(dāng)前左區(qū)間元素值大于右區(qū)間元素值；
  • 左區(qū)間、右區(qū)間都還有元素，且當(dāng)前左區(qū)間元素值小于等于右區(qū)間元素值；
  • 左區(qū)間元素值用完、右區(qū)間還剩有元素值；
  • 右區(qū)間元素用完、左區(qū)間還剩有元素值。

算法代碼實(shí)現(xiàn)過程

• 分解：把當(dāng)前區(qū)間一分為二，分解點(diǎn)即中間點(diǎn)mid=(start + end) / 2
• 求解：分別遞歸左右兩個(gè)子區(qū)間[start… end] 和[mid+1 … end]進(jìn)行歸并排序，遞歸的終結(jié)條件是子區(qū)間的長度為1
• 合并：使用雙指針法將兩個(gè)有序區(qū)間歸并成一個(gè)臨時(shí)有序區(qū)間[start … end]，并將結(jié)果拷貝到原數(shù)組的區(qū)間[start …end]，是原數(shù)組[start… end]變?yōu)橛行颉?/li>

def merge(nums, start, mid, end):
    # 使用雙指針法將兩個(gè)有序區(qū)間歸并成一個(gè)臨時(shí)有序區(qū)間
    i, j, temp = start, mid + 1, []
    while i <= mid and j <= end:
        if nums[i] <= nums[j]:
            temp.append(nums[i])
            i += 1
        else:
            temp.append(nums[j])
            j += 1
    while i <= mid:
        temp.append(nums[i])
        i += 1
    while j <= end:
        temp.append(nums[j])
        j += 1
    for i in range(len(temp)):
        nums[start + i] = temp[i]


def mergesort(nums, start, end):
    if start >= end:
        return

    mid = (start + end) >> 1
    mergesort(nums, start, mid)  # 遞歸左區(qū)間
    mergesort(nums, mid + 1, end)  # 遞歸右區(qū)間
    merge(nums, start, mid, end)
    return nums

num_list = [8, 4, 5, 7, 1, 3, 6, 2]
print(mergesort(num_list, 0, len(num_list)- 1))

LCR 170. 交易逆序?qū)Φ目倲?shù)

https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/

解法：歸并排序

class Solution:
    def reversePairs(self, record: List[int]) -> int:
        self.cnt = 0
        def merge(nums, start, mid, end):
            # 使用雙指針法將兩個(gè)有序區(qū)間歸并成一個(gè)臨時(shí)有序區(qū)間
            i, j, temp = start, mid + 1, []
            while i <= mid and j <= end:
                if nums[i] <= nums[j]:
                    temp.append(nums[i])
                    i += 1
                else:
                    self.cnt += mid - i + 1 #更新逆序?qū)Φ膫€(gè)數(shù)
                    temp.append(nums[j])
                    j += 1
            while i <= mid:
                temp.append(nums[i])
                i += 1
            while j <= end:
                temp.append(nums[j])
                j += 1
            for i in range(len(temp)):
                nums[start + i] = temp[i]


        def mergesort(nums, start, end):
            if start >= end:
                return

            mid = (start + end) >> 1
            mergesort(nums, start, mid)  # 遞歸左區(qū)間
            mergesort(nums, mid + 1, end)  # 遞歸右區(qū)間
            merge(nums, start, mid, end)
        
        mergesort(record, 0, len(record) - 1)
        return self.cnt

315. 計(jì)算右側(cè)小于當(dāng)前元素的個(gè)數(shù)（力扣題目）

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

排序+二分解法

• 使用sorted_num數(shù)組按照從小到大的順序存儲當(dāng)前已經(jīng)遍歷過的元素；

• 倒序遍歷nums數(shù)組中的各個(gè)元素n，對于n，完成以下迭代

• 迭代

  • 通過二分法找到n在sorted_nums數(shù)組中的插入位置index，這個(gè)index便是數(shù)組sorted_nums中在n右側(cè)且小于n的元素的個(gè)數(shù)，添加到ans中
  • 把n插入到sorted_nums這一有序數(shù)組中

• 輸出：由于sorted_nums是從右往左添加的，因此最后輸出的時(shí)候要重新調(diào)整回來

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        if not nums:
            return []
        # 按照從小到大的順序存儲當(dāng)前已經(jīng)遍歷過的所有元素
        sorted_num = []
        #存儲最終結(jié)果
        ans = []
        # 倒序遍歷
        for n in nums[::-1]:
            # 通過二分法找到n在sorted_nums數(shù)組中的插入位置index
            index = bisect.bisect_left(sorted_num, n)
            #把n插入到sorted_nums這一有序數(shù)組中
            bisect.insort(sorted_num, n)
            ans.append(index)
        #輸出時(shí)順序調(diào)整
        return ans[::-1]

附錄基礎(chǔ)

python數(shù)據(jù)結(jié)構(gòu)與算法理論基礎(chǔ)（專欄）

數(shù)據(jù)結(jié)構(gòu)與算法（python）

程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法；而且在面試過程中這些是必考，必問的內(nèi)容。內(nèi)容大綱：基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)（樹、鏈表、棧、隊(duì)列等）、常見算法（排序算法、遞歸算法等）。

專欄是基于python的基礎(chǔ)知識，是很好的入門學(xué)習(xí)資料。幫助大家快速理解這些數(shù)據(jù)結(jié)構(gòu)和常見算法的概念，同時(shí)結(jié)合力扣題目，也能更好的掌握這些知識，達(dá)到在面試中游刃有余的效果。

python基礎(chǔ)語法

python基礎(chǔ)精講

本專欄主要針對python基礎(chǔ)語法，幫助學(xué)習(xí)者快速接觸并掌握python大部分最重要的語法特征。
1、基本數(shù)據(jù)類型和變量
2、分支結(jié)構(gòu)與循環(huán)結(jié)構(gòu)
3、函數(shù)與異常處理
4、類與模塊
5、文件讀寫

通過本專欄可以快速掌握python的基礎(chǔ)語法。文章來源地址http://www.zghlxwxcb.cn/news/detail-811994.html

到了這里，關(guān)于python算法與數(shù)據(jù)結(jié)構(gòu)---排序和歸并排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！