Python - 深夜数据结构与算法之 Sort

目录

一.引言

二.排序简介

1.排序类型

2.时间复杂度

3.初级排序?

4.高级排序

A.快速排序

B.归并排序

C.堆排序

5.特殊排序

三.经典算法实战

1.Quick-Sort?

2.Merge-Sort

3.Heap-Sort

4.Relative-Sort-Array [1122]

5.Valid-anagram [242]

6.Merge-Intervals [56]

7.Reverse-Pairs-V1 [LCR 170]

8.Reverse-Pairs-V2 [493]

四.总结

---

一.引言

排序在日常开发中是最常见的应用之一，常用的有快速排序、冒泡排序、桶排序、归并排序、合并排序等等，下面我们介绍下常用的排序算法与原理。

二.排序简介

1.排序类型

前者可以参考 Java 的 Comparator，我们通过定义看来两个 Class 的比较方法实现元素两两之间的排序；而后者的非比较类排序主要适用于整形类数字，且往往需要额外的内存空间辅助，因此两种方法也是各有利弊。

2.时间复杂度

3.初级排序?

初级排序的平均时间复杂度都在 o(n^2)，其排序都是不断缩小范围且比较次数较多。

4.高级排序

A.快速排序

B.归并排序

C.堆排序

5.特殊排序

三.经典算法实战

1.Quick-Sort?

class Solution:

    def quickSort(self, nums, start, end):
        if end <= start:
            return
        pivot = self.partition(nums, start, end)
        self.quickSort(nums, start, pivot - 1)
        self.quickSort(nums, pivot + 1, end)

    def partition(self, nums, start, end):
        # pivot 标杆位置 counter 小于 pivot 的个数
        counter, pivot = start, end

        for i in range(start, end):
            # 移动小于标杆的元素
            if nums[i] < nums[pivot]:
                nums[counter], nums[i] = nums[i], nums[counter]
                counter += 1

        # 移动标杆
        nums[pivot], nums[counter] = nums[counter], nums[pivot]
        return counter

    def sort(self, nums):
        self.quickSort(nums, 0, len(nums) - 1)
        return nums


if __name__ == '__main__':
    nums = [3, 7, 1, 5, 9, 2, 4]
    s = Solution()
    print(s.sort(nums))

通过二分的方法，每次对数组一分为 2，再到子数组一分为二继续拆分，如果使用 Python 也有更简洁的写法，不过这里推荐大家熟悉上面的双指针写法，对于理解更有帮助。

    def sortV2(self, nums):
        if len(nums) < 2:
            return nums
        else:
            pivot = nums[0]
            less = [i for i in nums[1:] if i <= pivot]
            rather = [i for i in nums[1:] if i > pivot]

        return self.sortV2(less) + [pivot] + self.sortV2(rather)

这种写法比较容易理解，但是空间复杂度会更高。

2.Merge-Sort

class Solution:

    def merge_sort(self, arr):
        if len(arr) <= 1:
            return arr

        mid = len(arr) // 2
        # 一分为二
        left = self.merge_sort(arr[:mid])
        right = self.merge_sort(arr[mid:])

        # 合并
        return self.merge(left, right)

    def merge(self, left, right):
        result = []
        i = j = 0

        # 双指针比大小
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        
        # 追加数组
        result.extend(left[i:])
        result.extend(right[j:])

        return result


if __name__ == '__main__':
    nums = [3, 7, 1, 5, 9, 2, 4]
    s = Solution()
    print(s.merge_sort(nums))

这里也可以看出快排和归并的差距:?

3.Heap-Sort

import heapq

class Solution:

    def heap_sort(self, nums):
        heapq.heapify(nums)

        re = []
        for i in range(len(nums)):
            re.append(heapq.heappop(nums))

        return re

if __name__ == '__main__':
    nums = [3, 7, 1, 5, 9, 2, 4]
    s = Solution()
    print(s.heap_sort(nums))

直接调用 heapq 实现小顶堆，随后按顺序 pop 获取最小值即可。

4.Relative-Sort-Array [1122]

数组相对排序:?https://leetcode.cn/problems/relative-sort-array

◆ 题目分析

最常规的方法就是把 arr2 的元素重新构建 num2index，按照他们的索引对 arr1 的元素排序，最后再用索引反映射回来即可，即 zipWithIndex，用 index 排序，再 indexWithNum，把 index 转换回来。

◆ 传统实现

class Solution(object):
    def relativeSortArray(self, arr1, arr2):
        """
        :type arr1: List[int]
        :type arr2: List[int]
        :rtype: List[int]
        """
        
        # 构建 i-> num 和 num -> i 的映射
        m = {}
        change = {}
        for i in range(len(arr2)):
            m[arr2[i]] = i
            change[i] = arr2[i]

        # 补充排序
        add = []
        wait = []

        # 区分待排序与异常排序
        for i in arr1:
            if i in m:
                wait.append(m[i])
            else:
                add.append(i)
        
        wait.sort()
        add.sort()

        # 根据映射返回
        return [change[i] for i in wait] + add
        

比较好理解，但是时间、空间复杂度都比较高。?

◆ 计数排序

class Solution(object):
    def relativeSortArray(self, arr1, arr2):
        """
        :type arr1: List[int]
        :type arr2: List[int]
        :rtype: List[int]
        """
        # 统计 arr1 中元素的频次
        count = [0] * 1001
        for num in arr1:
            count[num] += 1
        
        result = []
        
        # 遍历arr2，将arr2中的元素按照在arr1中的频次添加到结果中
        for num in arr2:
            result.extend([num] * count[num])
            count[num] = 0
        
        # 遍历count数组，将未在arr2中出现过的元素按照升序添加到结果中
        for i in range(len(count)):
            result.extend([i] * count[i])
        
        return result

通过计数排序的思想，我们对 arr1 的所有元素进行词频统计，随后根据 arr2 的顺序获取元素的 count 添加至 results，这样就保证了按照 arr2 的顺序，而剩下的数组则默认有序，把 count 拿出来 extend 即可。?

5.Valid-anagram [242]

有效异位词:?https://leetcode.cn/problems/valid-anagram/

◆ 题目分析

统计每个字符的数量，如果完全一致则为异位词。也可以字符串排序再比较。

◆ 字符统计

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if len(s) != len(t):
            return False

        # 统计字符数量是否相等
        word_count = [0] * 26

        for char in s:
            word_count[ord(char) - ord('a')] += 1

        for char in t:
            word_count[ord(char) - ord('a')] -= 1

        # 判断 0
        for count in word_count:
            if count != 0:
                return False

        return True
            

◆ 字符排序

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if len(s) != len(t):
            return False

        s = list(s)
        s.sort()

        t = list(t)
        t.sort()

        for i in range(len(s)):
            if s[i] != t[i]:
                return False
        
        return True
            

直接字符串排序即可。?

6.Merge-Intervals [56]

合并区间:?https://leetcode.cn/problems/merge-intervals/description/?

◆ 题目分析

按照 interval 的 start 进行排序，随后顺序比较并插入。

◆ 数字排序

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        intervals.sort()

        re = []
        for i in intervals:
            # 数组为空或者
            if not re or re[-1][1] < i[0]:
                re.append(i)
            else:
                re[-1][1] = max(re[-1][1], i[1])

        return re

7.Reverse-Pairs-V1 [LCR 170]

交易逆序对:?https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/

◆ 题目分析

套用归并排序的模版，在归并的过程中记录逆序的情况总数。

◆ 归并排序

class Solution:
    def mergeSort(self, record, tmp, l, r):
        if l >= r:
            return 0

        mid = (l + r) // 2
        # 拆分数组
        inv_count = self.mergeSort(record, tmp, l, mid) + self.mergeSort(record, tmp, mid + 1, r)
        # 左端 l-mid 右端 mid+1 起始位置 l
        i, j, pos = l, mid + 1, l
        while i <= mid and j <= r:
            if record[i] <= record[j]:
                tmp[pos] = record[i]
                i += 1
                # 右边有多少的元素比当前的 nums[i] 小，逆序对就加几
                inv_count += (j - (mid + 1))
            else:
                tmp[pos] = record[j]
                j += 1
            # 赋值位置 +1
            pos += 1

        for k in range(i, mid + 1):
            tmp[pos] = record[k]
            inv_count += (j - (mid + 1))
            pos += 1

        for k in range(j, r + 1):
            tmp[pos] = record[k]
            pos += 1

        record[l:r + 1] = tmp[l:r + 1]
        return inv_count

    def reversePairs(self, record):
        n = len(record)
        tmp = [0] * n
        return self.mergeSort(record, tmp, 0, n - 1)

8.Reverse-Pairs-V2 [493]

翻转对:?https://leetcode.cn/problems/reverse-pairs/description/

◆ 题目分析

和上面的题目类似，但是需要注意条件增强，需要满足 2 倍的关系。

◆ 归并排序

class Solution:

    def reversePairs(self, arr):
        self.count = 0
        self.merge_sort(arr)
        return self.count

    def merge_sort(self, arr):
        if len(arr) <= 1:
            return arr

        mid = len(arr) // 2
        # 一分为二
        left = self.merge_sort(arr[:mid])
        right = self.merge_sort(arr[mid:])

        # 合并
        return self.merge(left, right)

    def merge(self, left, right):
        result = []

        # 计数
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] <= 2 * right[j]:
                self.count += j
                i += 1
            else:
                j += 1

        self.count += (len(left) - i) * j

        # 双指针比大小
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1

        # 追加数组
        result.extend(left[i:])
        result.extend(right[j:])

        return result

类似的逆序题目我们都可以套用 Merge Sort 的模版，注意不要忘了在 i/j 遍历完后，补充后面的尾巴，因为 i 或者 j 会率先到达自己的边界即 mid 或 right，所以还有一小撮修要我们收尾。

四.总结

上面整理了日常几种常用的排序算法，我们主要需要重复的是快速排序的指针版本以及归并排序的临时内存版本，这两个方法更考验基本功同时可以作为很多题目的扩展，所以一定要多多回溯练习。