数据结构与算法-基础排序算法及TopK问题（Python）

2023-11-12

排序

基础排序算法
经典问题：TopK
- 堆排序
- 快速排序

基础排序算法

如果在面试中遇到排序算法，先问清楚数据的特点，结合具体的业务场景，多和面试官交流，先陈述思路，得到面试官肯定以后再编码
没有一个排序算法是任何情况下都表现最好的。
学习算法的可视化网站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

常见排序算法对比
在这里插入图片描述
所有代码和思路以升序为例。

冒泡排序

思路：

每一轮依次比较相邻的两个元素，如果前一个元素>后一个，则交换位置，保证未排定部分的最大元素置于数组末尾；
重复上述步骤，直到第2个元素是前两个元素中最大的，排序结束；

优化：
通过flag标识已经有序的情况，提前停止排序。

Python实现：

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if len(nums)<2:
            return nums
        
        flag = True
        n = len(nums)
        for i in range(n,0,-1):
            for j in range(1,i):
                if nums[j-1]>nums[j]:
                    flag = False
                    nums[j-1],nums[j] = nums[j],nums[j-1]
            if flag:
                break
        return nums

复杂度分析：
时间复杂度：O(n²)，加上flag最优的情况即本身有序，O(n)；
空间复杂度：O(1)，原地操作，不需要额外的空间。

选择排序

思路：

每轮选出未排定部分中最小的元素，交换到未排定部分的开头，交换一次；

Python实现：

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if len(nums)<2:
            return nums
        
        n = len(nums)
        for i in range(n):
            min_idx = i
            for j in range(i+1,n):
                if nums[j]<nums[min_idx]:
                    min_idx = j
            nums[i],nums[min_idx] = nums[min_idx],nums[i]

        return nums

复杂度分析：
时间复杂度：O(n²)；
空间复杂度：O(1)，原地操作，不需要额外的空间。

优点： 交换次数最少
在交换成本较高的排序任务中，可以使用选择排序。

插入排序

思路：

保持当前元素左侧是排序后的数组，将当前元素插入到对应位置。

Python实现：

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if len(nums)<2:
            return nums
        
        n = len(nums)
        for i in range(1,n):
            j = i 
            while j>0 and nums[j]<nums[j-1]:
                nums[j],nums[j-1] = nums[j-1],nums[j]
                j -= 1

        return nums

复杂度分析：
时间复杂度：O(n²)，最好的情况即数组有序时，复杂度为O(n)；
空间复杂度：O(1)，原地操作，不需要额外的空间。

优化：
可以采用二分查找的方式来确定需要插入的位置

优点：
内层循环可以提前终止，因此插入排序在几乎有序的数组上表现良好，在短数组（每个元素离它最终排定的位置都不会太远）上表现也很好。

归并排序

思路：

分而治之的思想，理解递归的好材料，递归时，只剩下一个元素或没有元素时返回；
借助额外空间，合并两个有序数组，得到更长的有序数组。

Python实现：

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if len(nums)<2:
            return nums
  
        self.mergesort(nums,0,len(nums)-1)
        return nums
    
    def merge(self,nums,left,mid,right):
        temp = []
        i = left
        j = mid+1
        while i<=mid and j<=right:
            if nums[i]<=nums[j]:
                temp.append(nums[i])
                i += 1
            else:
                temp.append(nums[j])
                j += 1
        while i<=mid:
            temp.append(nums[i])
            i += 1
        while j<=right:
            temp.append(nums[j])
            j += 1
        return temp

    def mergesort(self,nums,left,right):
        if left>=right:
            return
        mid = (left+right)//2
        self.mergesort(nums,left,mid)
        self.mergesort(nums,mid+1,right)
        temp = self.merge(nums,left,mid,right)
        for j in range(len(temp)):
            nums[left+j] = temp[j]

复杂度分析：
时间复杂度：确定的O(nlogn)
空间复杂度：O(n)，借助了额外空间，可以实现稳定排序

缺点：
需要额外的空间，元素来回复制；
一般不用于内排序。

优化：
只开一个temp数组，避免频繁申请、释放内存。

快速排序

思路：

每论都排定一个元素（主元pivot），然后递归地去排它左侧和右侧的部分，直到数组有序
Tips：
随机化选择切分元素，否则在输入数组是有序或逆序时，快速排序会非常慢；
递归到规模充分小时，停止递归，直接用简单排序（如插入排序）。

Python实现：

## 方法一：
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if len(nums)<=1:
            return nums
        
        def partition(left,right):
            pivot = nums[left]
            index = left
            for i in range(left+1,right+1):
                if nums[i]<pivot:
                    index += 1
                    if i!=index:
                        nums[i],nums[index] = nums[index],nums[i]
            nums[left],nums[index] = nums[index],nums[left]
            return index
        
        def quicksort(low,high):
            if low<high:
                idx = partition(low,high)
                quicksort(low,idx-1)
                quicksort(idx+1,high)
            return

        quicksort(0,len(nums)-1)
        return nums
## 方法二：
def quickSort(self,nums,left,right):
        print(left,right,nums)
        if left>=right:
            return
        mid = (left+right)//2
        if nums[mid]<nums[left]:
            nums[mid],nums[left] = nums[left],nums[mid]
        if nums[right]<nums[left]:
            nums[right],nums[left] = nums[left],nums[right]
        if nums[mid]>nums[right]:
            nums[mid],nums[right] = nums[right],nums[mid]
        
        nums[mid],nums[right-1] = nums[right-1],nums[mid]
        #if right-left<=2:
        #    return
      
        pivot = nums[right-1]
        i = left
        j = right-1
        while i<j:
            i += 1
            j -= 1
            while nums[i]<pivot:
                i += 1
            while nums[j]>pivot:
                j -= 1
            if i<j:
                nums[i],nums[j] = nums[j],nums[i]
            else:
                break

        nums[i],nums[right-1] = nums[right-1],nums[i]
        print(nums)
        self.quickSort(nums,left,i-1)
        self.quickSort(nums,i+1,right)

复杂度分析：
时间复杂度：O(nlogn)，最坏情况下O(n²)
空间复杂度：O(logn)

经典问题：TopK

TopK 是面试常考的问题
「力扣」第 215 题：数组中的第 K 个最大元素

堆排序

思路：
堆是对选择排序的优化，通过把未排定部分构建成堆，可以实现O(logn)选择最大的元素。

两个特性：

结构性：用数组表示的完全二叉树；
有序性：任一结点的关键字是其子树所有结点的最大值（或最小值）
maxheap：最大堆，又叫大顶堆

python：heapq模块

Python实现：
维护一个k大小的小顶堆，顶部就是第k个大的元素，如果是取最大的k个元素一般直接用大顶堆；
heap数组大小设置为k+1，从下标为1开始存储元素，则下标为p的结点其左右子结点分别为2p/2p+1，其父节点为p//2。

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        if not nums or len(nums)<k:
            return -1
        
        heap = [0 for _ in range(k+1)]
        for i in range(k):
            heap[i+1] = nums[i]
        
        ## build the heap
        for i in range(k//2,0,-1):
            self.percdown(i,k,heap)
        ## insert
        for i in range(k,len(nums)):
            if nums[i]>heap[1]:
                heap[1] = nums[i]
                self.percdown(1,k,heap)
        return heap[1]

    def percdown(self,i,k,heap):
        while i*2<=k:
            if i*2+1<=k and heap[i*2+1]<heap[i*2]:
                Min = i*2+1
            else:
               Min = i*2
            if heap[i]>heap[Min]:
                heap[i],heap[Min] = heap[Min],heap[i]
            i = Min

复杂度分析：
时间复杂度：O(nlogk)
空间复杂度：O(k)

空间复杂度与k相关，适用于海量的数据，不需要一次性完全读取。

快速排序

# TopK
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        if len(nums)<k:
            return -1
        
        small = len(nums)-k

        def partition(left,right):
            pivot = nums[left]
            index = left
            for i in range(left+1,right+1):
                if nums[i]<pivot:
                    index += 1
                    if i!=index:
                        nums[i],nums[index]=nums[index],nums[i]
            nums[left],nums[index] = nums[index],nums[left]
            if index==small:
                return 
            elif index<small:
                partition(index+1,right)
            else:
                partition(left,index-1)
        
        partition(0,len(nums)-1)
        return nums[small]

复杂度分析：
时间复杂度：O(n)，根据主定理计算可得；
空间复杂度：O(logn)，递归栈空间

参考资料
https://leetcode-cn.com/problems/sort-an-array/solution/dang-wo-tan-pai-xu-shi-wo-zai-tan-xie-shi-yao-by-s/
https://leetcode-cn.com/problems/sort-an-array/solution/fu-xi-ji-chu-pai-xu-suan-fa-java-by-liweiwei1419/

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)