计数法排序

  • 适用于数值范围比较小的情形
  • 时间复杂度为O(n + k)
  • 空间复杂度为O(k)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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/
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    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]

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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