前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >面试复习-算法-排序

面试复习-算法-排序

作者头像
宅蓝三木
发布2024-10-09 21:14:09
发布2024-10-09 21:14:09
5500
代码可运行
举报
文章被收录于专栏:三木的博客三木的博客
运行总次数:0
代码可运行

计数法排序

  • 适用于数值范围比较小的情形
  • 时间复杂度为O(n + k)
  • 空间复杂度为O(k)
代码语言:javascript
代码运行次数:0
运行
复制
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        minNum = nums[0]
        maxNum = nums[0]
        for n in nums:
            minNum = min(minNum, n)
            maxNum = max(maxNum, n)
        count = [0 for _ in range(maxNum - minNum + 1)]
        for n in nums:
            count[n - minNum] += 1
        res = []
        for i, c in enumerate(count):
            while c > 0:
                res.append(minNum + i)
                c -= 1
        return res

快速排序

  • 快排的时间复杂度为O(nlogn),但如果中间值都位于数组的头部或者尾部,时间复杂度会退化为O(n**2)
代码语言:javascript
代码运行次数:0
运行
复制
import random

def swap(nums, a, b):
    if a == b or nums[a] == nums[b]:
        return
    tmp = nums[a]
    nums[a] = nums[b]
    nums[b] = tmp

def partition(nums, start, end):
    p = start - 1
    q = start
    r = random.randint(start, end)  # 优化有序数组
    swap(nums, r, end)
    while q < end:
        if nums[q] < nums[end]:
            p += 1
            swap(nums, p, q)
        q += 1
    p += 1
    swap(nums, p, q)
    return p


def quickSort(nums, start, end):
    if (start < end):
        i = partition(nums, start, end)
        idx = i - 1
        while start <= idx <= end and nums[idx] == nums[i]:  # 优化多个相同数值相邻的情形
            idx -= 1
        quickSort(nums, start, idx)
        idx = i + 1
        while start <= idx <= end and nums[idx] == nums[i]:
            idx += 1
        quickSort(nums, idx, end)

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        quickSort(nums, 0, len(nums) - 1)
        return nums

寻找第K大的数: https://leetcode.cn/problems/xx4gT2/

代码语言:javascript
代码运行次数:0
运行
复制
import random

def partition(nums, k, start, end):
    r = random.randint(start, end)
    nums[r], nums[end] = nums[end], nums[r]
    p = start - 1
    q = start
    while q < end:
        if nums[q] < nums[end]:
            p += 1
            nums[p], nums[q] = nums[q], nums[p]
        q += 1
    p += 1
    nums[p], nums[q] = nums[q], nums[p]
    return p

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        n = len(nums)
        start = 0
        end = n - 1
        i = partition(nums, k, 0, end)
        while i != n - k:
            i = partition(nums, k, start, end)
            if i < n - k:
                start = i + 1
            else:
                end = i - 1
        return nums[i]

归并排序

代码语言:javascript
代码运行次数:0
运行
复制
def merge(arrA, arrB):
    lenA = len(arrA)
    lenB = len(arrB)
    res = []
    idxA = 0
    idxB = 0
    while idxB < lenB and idxA < lenA:
        if arrA[idxA] < arrB[idxB]:
            res.append(arrA[idxA])
            idxA += 1
        else:
            res.append(arrB[idxB])
            idxB += 1
    if idxA < lenA:
        res.extend(arrA[idxA:])
    else:
        res.extend(arrB[idxB:])
    return res

def mergeSort(arr, start, end):
    if start == end:
        return [arr[start]]
    middle = (start + end) // 2
    top = mergeSort(arr, start, middle)
    bottom = mergeSort(arr, middle + 1, end)
    return merge(top, bottom)

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        res = mergeSort(nums, 0, len(nums) - 1)
        return res
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-09-12,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 计数法排序
  • 快速排序
  • 归并排序
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档