python算法与数据结构—排序和归并排序

本文介绍: 专栏是基于python的基础知识，是很好的入门学习资料。帮助大家快速理解这些数据结构和常见算法的概念，同时结合力扣题目，也能更好的掌握这些知识，达到在面试中游刃有余的效果。本专栏主要针对python基础语法，帮助学习者快速接触并掌握python大部分最重要的语法特征。而且在面试过程中这些是必考，必问的内容。temp数组用于存储合并结果，合并后拷贝回原数组；通过本专栏可以快速掌握python的基础语法。平均时间复杂度：O(N。最坏时间复杂度：O(N。1、基本数据类型和变量。2、分支结构与循环结构。

平均时间复杂度：O(NlogN)
最坏时间复杂度：O(NlogN)

在这里插入图片描述

def merge(nums, start, mid, end):
    # 使用双指针法将两个有序区间归并成一个临时有序区间
    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)  # 递归左区间
    mergesort(nums, mid + 1, end)  # 递归右区间
    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))

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):
            # 使用双指针法将两个有序区间归并成一个临时有序区间
            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 #更新逆序对的个数
                    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)  # 递归左区间
            mergesort(nums, mid + 1, end)  # 递归右区间
            merge(nums, start, mid, end)
        
        mergesort(record, 0, len(record) - 1)
        return self.cnt

https://leetcode.cn/problems/count-of-smaller-numbers-after-self/description/
在这里插入图片描述

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        if not nums:
            return []
        # 按照从小到大的顺序存储当前已经遍历过的所有元素
        sorted_num = []
        #存储最终结果
        ans = []
        # 倒序遍历
        for n in nums[::-1]:
            # 通过二分法找到n在sorted_nums数组中的插入位置index
            index = bisect.bisect_left(sorted_num, n)
            #把n插入到sorted_nums这一有序数组中
            bisect.insort(sorted_num, n)
            ans.append(index)
        #输出时顺序调整
        return ans[::-1]