歸并排序的 3 個優(yōu)化-1

歸并排序的 個優(yōu)化

歸并排序的優(yōu)化有以下 個角度：

1、如果兩個數(shù)組，直接拼起來就是有序的，就無須 merge。即當(dāng) arr[mid]<=arr[mid+1]
的時候是不用 merge 的；

2、前面我們提到過，“插入排序”在小規(guī)模的排序任務(wù)上表現(xiàn)出色，這里，我們就可以在小區(qū)間里使用插入排序了；

3、我們每次做歸并的時候，都 new 了輔助的空間，用完之后就丟棄了。事實上，我們可以全程使用 1 個和待排序數(shù)組一樣長度的數(shù)組作為輔助歸并兩個排序數(shù)組的臨時空間，這樣就避免了頻繁 new 和 delete 數(shù)組空間的操作。

下面我們依次說明。

如果數(shù)組有序無須歸并

例如下面這兩個數(shù)組，直接把它們接在一起就可以了。

歸并排序的 3 個優(yōu)化-2

Python 代碼：

def __merge_sort(nums, left, right):
    if left >= right:
        return
    mid = left + (right - left) // 2  # 這是一個陷阱
    __merge_sort(nums, left, mid)
    __merge_sort(nums, mid + 1, right)
    if nums[mid] <= nums[mid + 1]:
        return
    __merge_of_two_sorted_array(nums, left, mid, right)

小區(qū)間排序使用“插入排序”

我們在介紹“插入排序”的時候，介紹了兩種實現(xiàn)方式，我們不妨都實現(xiàn)一下。只不過，我們這里實現(xiàn)的是對原數(shù)組的子區(qū)間 [left, right] 使用插入排序。

Python 代碼1：

def insert_sort_for_merge_1(nums, left, right):
    """
    逐個向前交換的插入排序
    """
    # n = right - left + 1
    for i in range(left + 1, right + 1):
        for j in range(i, left, -1):  # 這里是 left
            if nums[j - 1] > nums[j]:
                nums[j], nums[j - 1] = nums[j - 1], nums[j]
            else:
                break

Python 代碼2：

def insert_sort_for_merge_2(nums, left, right):
    """
    多次賦值的插入排序
    """
    # n = right - left + 1
    for i in range(left + 1, right + 1):
        temp = nums[i]
        j = i - 1
        # 注意：這里 j 最多到 left
        while j >= left and nums[j] > temp:
            if nums[j] > temp:
                nums[j + 1] = nums[j]
                j -= 1
        nums[j + 1] = temp

把它們之一應(yīng)用在遞歸終止條件：

Python 代碼：

def __merge_sort(nums, left, right):
    if right - left <= 15:
        insert_sort_for_merge_2(nums, left, right)
        return
    mid = left + (right - left) // 2  # 這是一個陷阱
    __merge_sort(nums, left, mid)
    __merge_sort(nums, mid + 1, right)
    if nums[mid] <= nums[mid + 1]:
        return
    __merge_of_two_sorted_array(nums, left, mid, right)

全局使用一個臨時數(shù)組用于歸并

這里我們直接給出完整的歸并排序的代碼：

Python 代碼：

def __merge_of_two_sorted_array(nums, left, mid, right):
    # 將原數(shù)組 [left,right] 區(qū)間內(nèi)的元素復(fù)制到輔助數(shù)組
    for index in range(left, right + 1):
        nums_for_compare[index] = nums[index]

    # [1,  2, 3,   4,5]
    # left    mid    right
    i = left
    j = mid + 1
    for k in range(left, right + 1):
        if i == mid + 1:
            # i 用完了，就拼命用 j
            nums[k] = nums_for_compare[j]
            j += 1
        elif j > right:
            # j 用完了，就拼命用 i
            nums[k] = nums_for_compare[i]
            i += 1
        elif nums_for_compare[i] < nums_for_compare[j]:
            nums[k] = nums_for_compare[i]
            i += 1
        else:
            assert nums_for_compare[i] >= nums_for_compare[j]
            nums[k] = nums_for_compare[j]
            j += 1


def insert_sort_for_merge_1(nums, left, right):
    """
    逐個向前交換的插入排序
    """
    # n = right - left + 1
    for i in range(left + 1, right + 1):
        for j in range(i, left, -1):  # 這里是 left
            if nums[j - 1] > nums[j]:
                nums[j], nums[j - 1] = nums[j - 1], nums[j]
            else:
                break


def insert_sort_for_merge_2(nums, left, right):
    """
    多次賦值的插入排序
    """
    # n = right - left + 1
    for i in range(left + 1, right + 1):
        temp = nums[i]
        j = i - 1
        # 注意：這里 j 最多到 left
        while j >= left and nums[j] > temp:
            if nums[j] > temp:
                nums[j + 1] = nums[j]
                j -= 1
        nums[j + 1] = temp


def __merge_sort(nums, left, right):
    if right - left <= 15:
        insert_sort_for_merge_2(nums, left, right)
        return
    mid = left + (right - left) // 2  # 這是一個陷阱
    __merge_sort(nums, left, mid)
    __merge_sort(nums, mid + 1, right)
    if nums[mid] <= nums[mid + 1]:
        return
    __merge_of_two_sorted_array(nums, left, mid, right)


def merge_sort(nums):
    global nums_for_compare
    nums_for_compare = list(range(len(nums)))
    __merge_sort(nums, 0, len(nums) - 1)

分治思想的應(yīng)用：計算數(shù)組的逆序?qū)?/h2>

這里給出的例題如果對于初學(xué)者來說都偏難，不過其實你只要熟悉歸并排序，按照歸并排序的套路，是不難寫出下面的代碼。反正不過我是寫不出的，不過我會看別人寫的代碼，理解之后，自己寫出來。如果覺得理解這些代碼比較吃力的話，可以暫時跳過，我寫出來還是費了很大力氣，并且也是調(diào)試和一段時間才把代碼寫正確的。

例1：《劍指 Offer》（第 2 版）第 51 題：計算數(shù)組的逆序?qū)?/h3>

傳送門：《劍指 Offer》（第 2 版）第 51 題：計算數(shù)組的逆序?qū)?/a>。

在數(shù)組中的兩個數(shù)字如果前面一個數(shù)字大于后面的數(shù)字，則這兩個數(shù)字組成一個逆序?qū)Α?/p>

輸入一個數(shù)組，求出這個數(shù)組中的逆序?qū)Φ目倲?shù)。

樣例

輸入：[1,2,3,4,5,6,0]

輸出：6

思路1：首先我們應(yīng)該想到，使用定義計算逆序數(shù)，時間復(fù)雜度是：。

class Solution(object):
    def inversePairs(self, nums):
        l = len(nums)
        if l < 2:
            return 0
        res = 0
        for i in range(0, l - 1):
            for j in range(i + 1, l):
                if nums[i] > nums[j]:
                    res += 1
        return res

這種思路雖然很直接，但編寫出錯的概率就很低了，在沒有在線評測系統(tǒng)的時候，它可以作為一個“正確的”參考答案，用以檢驗我們自己編寫的算法是否正確。

思路2：借助歸并排序的分治思想，時間復(fù)雜度為 。

分析：例如：前有序數(shù)組：，后有序數(shù)組：。

做歸并的時候，步驟如下：

第 1 步， 先出列， 比“后有序數(shù)組”中所有的元素都小，構(gòu)成“順序?qū)Α保?/p>

第 2 步， 出列， 比“后有序數(shù)組”中所有的元素都小，構(gòu)成“順序?qū)Α保?/p>

第 3 步， 出列，關(guān)鍵的地方在這里，“前有序數(shù)組”中所有剩下的元素 比 都大，構(gòu)成 個 “逆序?qū)Α?/strong>；

第 4 步， 出列， 比“后有序數(shù)組”中所有剩下的元素都小，構(gòu)成“順序?qū)Α保?/p>

第 5 步， 出列，“前有序數(shù)組”中所有剩下的元素 比 都大，構(gòu)成 個“逆序?qū)Α?/strong>；

第 6 步， 出列，“前有序數(shù)組”中所有剩下的元素 比 都大，構(gòu)成 個“逆序?qū)Α?/strong>；

第 7 步， 出列， 比“后有序數(shù)組”中所有剩下的元素 都小，構(gòu)成 個“順序?qū)Α保?/p>

第 8 步， 出列，此時“前有序數(shù)組”為空。

因此，我們只需要在“前有序數(shù)組”非空，且“后有序數(shù)組”中有元素出列的時候，即上面的第 3、5、6 步計算“逆序?qū)Α本涂梢粤?/strong>。

Python 代碼：

class Solution(object):
    def inversePairs1(self, nums):
        l = len(nums)
        if l < 2:
            return 0
        res = 0
        for i in range(0, l - 1):
            for j in range(i + 1, l):
                if nums[i] > nums[j]:
                    res += 1
        return res

    def inversePairs(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        l = len(nums)
        if l < 2:
            return 0
        temp = [0 for _ in range(l)]
        return self.count_inversion_pairs(nums, 0, l - 1, temp)

    def count_inversion_pairs(self, nums, l, r, temp):
        """
        在數(shù)組 nums 的區(qū)間 [l,r] 統(tǒng)計逆序?qū)?        :param nums:
        :param l: 待統(tǒng)計數(shù)組的左邊界，可以取到
        :param r: 待統(tǒng)計數(shù)組的右邊界，可以取到
        :param temp:
        :return:
        """
        # 極端情況下，就是只有 1 個元素的時候
        if l == r:
            return 0
        mid = l + (r - l) // 2
        left_pairs = self.count_inversion_pairs(nums, l, mid, temp)
        right_pairs = self.count_inversion_pairs(nums, mid + 1, r, temp)

        merge_pairs = 0
        # 代碼走到這里的時候，
        # [l, mid] 已經(jīng)完成了排序并且計算好逆序?qū)?        # [mid + 1, r] 已經(jīng)完成了排序并且計算好逆序?qū)?        # 如果 nums[mid] <= nums[mid + 1]，此時就不存在逆序?qū)?        # 當(dāng) nums[mid] > nums[mid + 1] 的時候，就要繼續(xù)計算逆序?qū)?        if nums[mid] > nums[mid + 1]:
            # 在歸并的過程中計算逆序?qū)?            merge_pairs = self.merge_and_count(nums, l, mid, r, temp)
        # 走到這里有 nums[mid] <= nums[mid + 1] 成立，已經(jīng)是順序結(jié)構(gòu)
        return left_pairs + right_pairs + merge_pairs

    def merge_and_count(self, nums, l, mid, r, temp):
        """
        前：[2,3,5,8]，后：[4,6,7,12]
        我們只需要在后面數(shù)組元素出列的時候，數(shù)一數(shù)前面這個數(shù)組還剩下多少個數(shù)字，
        因為"前"數(shù)組和"后"數(shù)組都有序，
        因此，"前"數(shù)組剩下的元素個數(shù) mid - i + 1 就是與"后"數(shù)組元素出列的這個元素構(gòu)成的逆序?qū)€數(shù)
         
        """
        for i in range(l, r + 1):
            temp[i] = nums[i]
        i = l
        j = mid + 1
        res = 0
        for k in range(l, r + 1):
            if i > mid:
                nums[k] = temp[j]
                j += 1
            elif j > r:
                nums[k] = temp[i]
                i += 1
            elif temp[i] <= temp[j]:
                # 不統(tǒng)計逆序?qū)?，只做排?                nums[k] = temp[i]
                i += 1
            else:
                assert temp[i] > temp[j]
                nums[k] = temp[j]
                j += 1
                # 快就快在這里，一次可以數(shù)出一個區(qū)間的個數(shù)的逆序?qū)?                # 例：[7,8,9][4,6,9]，4 與 7 以及 7 前面所有的數(shù)都構(gòu)成逆序?qū)?                res += (mid - i + 1)
        return res

說明：歸并兩個有序數(shù)組的時候，我們要借助額外的輔助空間，為此可以全局使用一個和原始數(shù)組等長的輔助數(shù)組，否則每一次進(jìn)入 merge 函數(shù)都要 new 新數(shù)組，開銷很大。

上述解法的缺點是修改了原始數(shù)組，排序完成以后，逆序數(shù)就計算出來了。為此：1、我們可以引入一個索引數(shù)組；2、或者直接拷貝一個原始數(shù)組，這樣就不用修改原始數(shù)組了。

例2：LeetCode 第 315 題：計算右側(cè)小于當(dāng)前元素的個數(shù)

傳送門：315. 計算右側(cè)小于當(dāng)前元素的個數(shù)。

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

示例:

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

Python 代碼：

class Solution:
    def countSmaller(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """

        size = len(nums)
        if size == 0:
            return []
        if size == 1:
            return [0]

        temp = [None for _ in range(size)]
        indexes = [i for i in range(size)]
        res = [0 for _ in range(size)]

        self.__helper(nums, 0, size - 1, temp, indexes, res)
        return res

    def __helper(self, nums, left, right, temp, indexes, res):
        if left == right:
            return
        mid = left + (right - left) // 2

        # 計算一下左邊
        self.__helper(nums, left, mid, temp, indexes, res)
        # 計算一下右邊
        self.__helper(nums, mid + 1, right, temp, indexes, res)

        if nums[indexes[mid]] <= nums[indexes[mid + 1]]:
            return
        self.__sort_and_count_smaller(nums, left, mid, right, temp, indexes, res)

    def __sort_and_count_smaller(self, nums, left, mid, right, temp, indexes, res):
        # [left,mid] 前有序數(shù)組
        # [mid+1,right] 后有序數(shù)組

        # 先拷貝，再合并

        for i in range(left, right + 1):
            temp[i] = indexes[i]

        l = left
        r = mid + 1
        for i in range(left, right + 1):
            if l > mid:
                # l 用完，就拼命使用 r
                # [1,2,3,4] [5,6,7,8]
                indexes[i] = temp[r]
                r += 1
            elif r > right:
                # r 用完，就拼命使用 l
                # [6,7,8,9] [1,2,3,4]
                indexes[i] = temp[l]
                l += 1
                # 注意：此時前面剩下的數(shù)，比后面所有的數(shù)都大
                res[indexes[i]] += (right - mid)
            elif nums[temp[l]] <= nums[temp[r]]:
                # [3,5,7,9] [4,6,8,10]
                indexes[i] = temp[l]
                l += 1
                # 注意：
                res[indexes[i]] += (r - mid - 1)
            else:
                assert nums[temp[l]] > nums[temp[r]]
                # 上面兩種情況只在其中一種統(tǒng)計就可以了
                # [3,5,7,9] [4,6,8,10]
                indexes[i] = temp[r]
                r += 1

說明：這里用到了一個索引數(shù)組 indeses，是一個常見的技巧。比如我們交換數(shù)組的元素成本很大的時候，可以使用索引數(shù)組，交換索引成本很低。這一點，在我們以后介紹索引堆的時候還會用到。

例3：LeetCode 第 53 題：最大子序和

傳送門：英文網(wǎng)址：53. Maximum Subarray ，中文網(wǎng)址：53. 最大子序和 。

給定一個整數(shù)數(shù)組 nums ，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。

示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6。

進(jìn)階:

如果你已經(jīng)實現(xiàn)復(fù)雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

分析：這道題其實最先應(yīng)該想到使用動態(tài)規(guī)劃，使用分治有點“小題大作”，我們不妨把分治解法看做一個例題。

分治的時候，要注意一點，不重不漏。

Python 代碼：

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 0:
            return 0
        return self.__max_sub_array(nums, 0, n - 1)

    def __max_sub_array(self, nums, left, right):
        if left == right:
            return nums[left]
        mid = left + (right - left) // 2
        return max(self.__max_sub_array(nums, left, mid),
                   self.__max_sub_array(nums, mid + 1, right),
                   self.__max_cross_array(nums, left, mid, right))

    def __max_cross_array(self, nums, left, mid, right):
        """
        一定包含 nums[mid] 元素的最大連續(xù)子數(shù)組的和
        思路是看看左邊擴(kuò)散到底，得到一個最大數(shù)
        右邊擴(kuò)散到底得到一個最大數(shù)
        :param nums:
        :param mid:
        :param right:
        :return:
        """
        ls = 0
        j = mid - 1
        s1 = 0
        while j >= left:
            s1 += nums[j]
            ls = max(ls, s1)
            j -= 1

        rs = 0
        j = mid + 1
        s2 = 0
        while j <= right:
            s2 += nums[j]
            rs = max(rs, s2)
            j += 1

        return ls + nums[mid] + rs


if __name__ == '__main__':
    s = Solution()
    nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    result = s.maxSubArray(nums)
    print(result)

在 LeetCode 上面搜索一下，看看還有哪些是分治思想解決的問題。

歸并排序的 3 個優(yōu)化-3

本文源代碼

Python：代碼文件夾，Java：代碼文件夾。

（本節(jié)完）