Leetcode_python/排序总结.md at main · DSXiangLi/Leetcode_python

排序算法总结

低级

低级-冒泡：两两互换大的在后，小的在前，每一趟都把最大值换到最后面

O(n^2)的复杂度

def bubble_sort(nums):
    n = len(nums)
    for i in range(n, 0, -1):
        for j in range(i-1):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1],nums[j]
    return nums

低级-插入排序:

从1开始，每个iter遍历第i个元素在前i-1个已经排好序的元素中的插入位置
i是待插入的元素位置，从i-1开始从后向前搜索

def insert_sort(nums):
    l = len(nums)
    if l==1:
        return nums
    for i in range(1, l):
        j = i
        target = nums[i]
        while j>0 and target< nums[j-1]:
            nums[j] = nums[j-1]
            j-=1
        nums[j] = target
    return nums

低级-选择排序：和冒泡相比也是每个iter选出最大或者最小的元素，但是只记录index并不每一步都进行交换，用一个额外的空间，节省中间交换的成本

def select_sort(nums):
    l = len(nums)
    if l==1:
        return nums
    for i in range(l-1):
        minIndex = i
        for j in range(i+1,l):
            if nums[j]<nums[minIndex]:
                minIndex = j
        if minIndex!=i:
            nums[i], nums[minIndex] = nums[minIndex],nums[i]
    return nums

高级

高级-快速排序：

找benchmark，一般是left，然后从两端向内收缩，保证bench mark左边比它小，右边比它大，这样benchmark的位置就固定了，再递归去排序左边的和右边的部分
和冒泡排序的差异，是冒泡每一个iter确认的是最大值，会快速排序确认的是一个中间值，所以能起到类似二分的效果

def quick_sort(nums):
    def partition(nums, left, right):
        key = left
        while left < right:
            while left<right and nums[right]>=nums[key]:
                right-=1
            while left<right and nums[left]<=nums[key]:
                left+=1
            nums[left],nums[right] = nums[right],nums[left]
        nums[left], nums[key] = nums[key],nums[left] # 保证返回left左侧的都比右侧的小，这样可以分别排序
        return left

    def sort(nums,left,right):
        if left>=right:
            return
        mid = partition(nums, left, right)

        sort(nums, left, mid - 1)
        sort(nums, mid + 1, right)
    return sort(nums, 0, len(nums)-1)

归并排序：自下而上的归并排序，复杂度是O(nlogn)，缺点是需要额外的空间来存储merge时有序的数组

def merge_sort(nums):
    def merge(nums, left, mid, right):
        i = left #左边起始
        j = mid+1 #右边起始
        temp = [] #存储排序数组
        while i <=mid and j<=right:
            if nums[i] <=nums[j]:
                temp.append(nums[i])
                i+=1
            else:
                temp.append(nums[j])
                j+=1
        if i<=mid:
            for k in range(i, mid+1):
                temp.append(nums[k])
        if j<=right:
            for k in range(j, right+1):
                temp.append(nums[k])
        for i in range(left, right+1):
            nums[i] = temp[i-left]

    def sort(nums, left, right):
        if left>=right:
            return
        mid = (left+right)//2
        sort(nums, left, mid)
        sort(nums, mid+1,right)
        merge(nums, left, mid, right)

    n = len(nums)
    if n<=1:
        return nums
    sort(nums, 0, len(nums) - 1)
    return nums

题目

220存在重复元素III
215 数组中的第K个最大元素
703 数据流中的第K大元素
40剑指offer. 最小的k个数

215. 数组中的第K个最大元素.md

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2 输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4

提示：

1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104

堆排序

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = [x for x in nums[:k]]
        heapq.heapify(heap)
        n=len(nums)
        for i in range(k, n):
            if nums[i]> heap[0]:
                heapq.heappop(heap)
                heapq.heappush(heap,nums[i])
        return heap[0]

python heapq是完全二叉树的实现，parent<=child
Heappop->下降：当root节点被heappop，会把叶子节点放到root，依次和child中更小的节点进行交换，直到再次成为叶节点

def _siftup(heap, pos):
    endpos = len(heap)
    startpos = pos
    newitem = heap[pos]
    # Bubble up the smaller child until hitting a leaf.
    childpos = 2*pos + 1    # 左节点，默认替换左节点
    while childpos < endpos:
        # Set childpos to index of smaller child.
        rightpos = childpos + 1  # 右节点
        if rightpos < endpos and not heap[childpos] < heap[rightpos]:
            childpos = rightpos  # 当右节点比较小时，应交换的是右节点
        # Move the smaller child up.
        heap[pos] = heap[childpos]
        pos = childpos
        childpos = 2*pos + 1
    # The leaf at pos is empty now.  Put newitem there, and bubble it up
    # to its final resting place (by sifting its parents down).
    heap[pos] = newitem
    _siftdown(heap, startpos, pos)

Heappush上浮：把push的元素放在叶节点，如果比parent小就和parent进行替换，

def _siftdown(heap, startpos, pos):
    newitem = heap[pos]
    # Follow the path to the root, moving parents down until finding a place
    # newitem fits.
    while pos > startpos:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if newitem < parent:
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = newitem

heapify

def heapify(x):
    """Transform list into a heap, in-place, in O(len(x)) time."""
    n = len(x)
    for i in reversed(range(n//2)):
        _siftup(x, i)

快速排序通用解法
- 不需要对整体数组进行排序，只需要找到第k个数即可

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def partition(nums, left, right):
            key = left
            while left<right:
                while left<right and nums[right]>=nums[key]:
                    right-=1
                while left<right and nums[left]<=nums[key]:
                    left+=1
                nums[left], nums[right] = nums[right],nums[left]
            nums[left],nums[key] =nums[key],nums[left]
            return left

        def topk(nums, k, left, right):
            if left>=right:
                return
            mid = partition(nums,left,right)
            if mid ==k:
                return
            elif mid<k:
                topk(nums,k, mid + 1, right)
            else:
                topk(nums,k,left, mid - 1)
        l = len(nums)
        topk(nums, l-k, 0, l-1)
        print(nums)
        return nums[l-k]

220. 存在重复元素 III.md

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。

如果存在则返回 true，不存在返回 false。

示例 1：

输入：nums = [1,2,3,1], k = 3, t = 0 输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1, t = 2 输出：true

示例 3：

输入：nums = [1,5,9,1,5,9], k = 2, t = 3 输出：false

提示：

0 <= nums.length <= 2 * 104
-231 <= nums[i] <= 231 - 1
0 <= k <= 104
0 <= t <= 231 - 1

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        bucket = dict()
        if t < 0: return False
        for i in range(len(nums)):
            nth = nums[i] // (t + 1)
            if nth in bucket:
                return True
            if nth - 1 in bucket and abs(nums[i] - bucket[nth - 1]) <= t:
                return True
            if nth + 1 in bucket and abs(nums[i] - bucket[nth + 1]) <= t:
                return True
            bucket[nth] = nums[i]
            if i >= k: bucket.pop(nums[i - k] // (t + 1))
        return False

40剑指offer. 最小的k个数.md

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

输入：arr = [3,2,1], k = 2 输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1 输出：[0]

限制：

0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000

堆排序

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if k==0:
            return list()
        nums = [-i for i in arr[:k]]
        heapq.heapify(nums)
        for i in arr[k:]:
            if -i > nums[0]:
                heapq.heappop(nums)
                heapq.heappush(nums, -i)
        return [-x for x in nums]

快速排序

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        def partition(nums, left, right):
            key = left
            while left<right:
                while left<right and nums[right]>=nums[key]:
                    right-=1
                while left<right and nums[left]<=nums[key]:
                    left+=1
                nums[left], nums[right] = nums[right],nums[left]
            nums[left],nums[key] =nums[key],nums[left]
            return left

        def quick_sort(nums, left, right):
            if left>=right:
                return
            
            mid = partition(nums, left, right)
            if k<mid:
                quick_sort(nums, left, mid - 1)
            else:
                quick_sort(arr, mid + 1, right)

        l = len(arr)
        if k>l:
            return arr
        quick_sort(arr, 0, l-1)
        return arr[:k]

快速排序解法

注意partition过程中，保证右边是>=key，左边是<=key，且左右是不对称的需要先遍历右边
在sort过程中，可以通过和k判断位置只对一半的位置进行排序
注意sort过程的停止条件，默认是left>=right，如果找k大的停止条件还有mid==k

703. 数据流中的第 K 大元素.md

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。

请实现 KthLargest 类：

KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

示例：

输入： ["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]] 输出： [null, 4, 5, 5, 8, 8]

解释： KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // return 4 kthLargest.add(5); // return 5 kthLargest.add(10); // return 5 kthLargest.add(9); // return 8 kthLargest.add(4); // return 8

提示：

1 <= k <= 104
0 <= nums.length <= 104
-104 <= nums[i] <= 104
-104 <= val <= 104
最多调用 add 方法 104 次
题目数据保证，在查找第 k 大元素时，数组中至少有 k 个元素

class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.k = k 
        self.que = nums
        heapq.heapify(self.que)# heapify是原地把list变成小根堆

    def add(self, val: int) -> int:
        heapq.heappush(self.que, val)
        while len(self.que)> self.k:
            heapq.heappop(self.que)
        return self.que[0]

Tips

优先队列算法（最小堆）

heapq是二叉树结构，特点是root<=children。所以有heap[k]<=heap[2K+1] & heap[k] <=heap[2K+2]的特点，且最小元素是root
heapq单次插入时间复杂度是log(k)，相比使用list每次add之后sort的时间复杂度是O(klog(k))
永远只维护K个最大的元素，这样最小堆的root就是第K大元素
pop弹出最小元素，heap[0]最小元素

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

排序算法总结

低级

高级

题目

215. 数组中的第K个最大元素.md

220. 存在重复元素 III.md

40剑指offer. 最小的k个数.md

703. 数据流中的第 K 大元素.md

FilesExpand file tree

排序总结.md

Latest commit

History

排序总结.md

File metadata and controls

排序算法总结

低级

高级

题目

215. 数组中的第K个最大元素.md

220. 存在重复元素 III.md

40剑指offer. 最小的k个数.md

703. 数据流中的第 K 大元素.md