常见算法搜集

Leetcode中常用算法的总结

排序算法

相关题目：912

快速排序

class Solution:
    def partition(self, nums, left, right):
        pivot = nums[left] # 在left(l)挖坑
        l, r = left, right
        while l < r:
            while l < r and nums[r] >= pivot:
                r -= 1
            if l < r:
                nums[l] = nums[r] # 在r挖坑，填l的坑
                l += 1
            while l < r and nums[l] <= pivot:
                l += 1
            if l < r:
                nums[r] = nums[l] # 在l挖坑，填r的坑
                r -= 1
        nums[l] = pivot
        return l

    def quicksort(self, nums, left, right):
        if left < right:
            pivot_loc = self.partition(nums, left, right)
            self.quicksort(nums, left, pivot_loc - 1)
            self.quicksort(nums, pivot_loc + 1, right)
            
    def sortArray(self, nums: List[int]) -> List[int]:
        self.quicksort(nums, 0, len(nums) - 1)
        return nums

堆排序

class Solution:
    def max_heapify(self, heap, root, heap_len): # 从root开始，依次与左右节点中较大的值进行交换
        p = root
        while p * 2 + 1 < heap_len:
            l, r = p * 2 + 1, p * 2 + 2
            if heap_len <= r or heap[r] < heap[l]:
                nex = l
            else:
                nex = r
            if heap[p] < heap[nex]:
                heap[p], heap[nex] = heap[nex], heap[p]
                p = nex
            else:
                break
        
    def build_heap(self, heap):
        for i in range(len(heap) - 1, -1, -1):
            self.max_heapify(heap, i, len(heap))

    def heap_sort(self, nums):
        self.build_heap(nums) # 构建初始堆，从最后一个叶结点开始向上遍历，每一个节点都保证以自己为根节点的树中自己的值最大
        for i in range(len(nums) - 1, -1, -1):
            nums[i], nums[0] = nums[0], nums[i] # 将当前最大值交换到队尾，找到一个元素的正确位置
            self.max_heapify(nums, 0, i)
            
    def sortArray(self, nums):
        self.heap_sort(nums)
        return nums