Python教程

python | 算法大神左神（左程云）算法课程 第二节

本文主要是介绍python | 算法大神左神（左程云）算法课程 第二节，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

针对的是b站视频-算法大神左神（左程云）算法课程第二节相关算法

由于python中关于递归有些踩坑，所以不搞对数器，就贴上单个例子验证正确的代码
视频笔记戳这里

1. 归并排序

归并排序-戳这里 
#归并排序-递归

class solution():
    def mergeSort(self, array):
        """
        归并排序
        :param array: List[int]
        :return: None
        """
        self.process(array, 0, len(array)-1)

    def process(self, array, left, right):
        """
        递归过程
        :param array: List[int]
        :param left: int
        :param right: int
        :return: None
        """
        if left == right: return

        mid = left + (right-left)>>1
        self.process(array, left, mid)
        self.process(array, mid+1, right)
        self.merge(array, left, mid, right)

    def merge(self, array, left, mid, right):
        #整一个辅助空间，存放已经排好序的部分
        help = []
        #比较
        i = left
        j = mid+1
        while i <= mid and j <= right:
            #判断
            if array[i] <= array[j]:
                help.append(array[i])
                i += 1
            else:
                help.append(array[j])
                j += 1
        #谁还剩，就都copy到help中
        while i <= mid:
            help.append(array[i])
            i += 1
        while j <= right:
            help.append(array[j])
            j += 1

        #将help中的排好序的数再copy回array中
        for i in range(len(help)):
            array[left+i] = help[i]

2.归并排序扩展-小和问题

归并排序扩展-小和问题-戳这里 
# 归并排序扩展
# 小和问题

class solution():
    def lowerSum(self, array):
        """
        求数组的array的小和
        :param array: List[int]
        :return: int
        """
        if len(array) < 2:
            return 0
        return self.process(array, 0, len(array)-1)

    def process(self, array, left, right):
        """
        递归过程
        :param array: List[int]
        :param left: int
        :param right: int
        :return: int
        """
        if left == right:
            return 0
        mid = left + (right-left)>>1
        return self.process(array, left, mid)+self.process(array, mid+1, right)+self.merge(array, left, mid, right)

    def merge(self, array, left, mid, right):
        """
        将排好序且求出小和的左右两个部分整合
        :param array: List[int]
        :param left: int
        :param mid: int
        :param right: int
        :return: int
        """
        help = []
        sum = 0
        i = left
        j = mid + 1
        while i <= mid and j <= right:
            if array[i] < array[j]:
                sum += array[i]*(right-j+1)
                help.append(array[i])
                i += 1
            else:
                help.append(array[j])
                j += 1

        while i <= mid:
            help.append(array[i])
            i += 1

        while j <= right:
            help.append(array[j])
            j += 1

        for i in range(len(help)):
            array[left+i] = help[i]

        return sum

这篇关于python | 算法大神左神（左程云）算法课程 第二节的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航