python数据结构与算法
0.时间复杂度和空间复杂度
快速判断算法时间复杂度：算法运行时间
1.确定问题规模n
2.循环减半 logn
3.k层关于n的循环 n^k
空间复杂度：评估算法内存占用大小
使用几个变量 O（1）
使用长度为n的一维列表 O（n）
使用m行n列的二维列表 O（mn）
1.递归
递归三步曲：
1.递归参数和返回值
2.终止条件
3.递归
2.二分查找
内置函数 .index() #输入待查找元素 ，输出元素下标，没找到返回None或-1
二分查找的代码
nums 是有序数组
def binary_search(nums, val):left = 0right = len(nums)-1while left <= right: #值在闭区间【left，right】找mid = (left+right)//2if nums[mid]< val: #待查找的值在mid右left = mid +1elif nums[mid] > val: #待查找的值在mid左right = mid -1else:return midreturn -1 #在nums里面找不到val
3.排序介绍
列表排序 内置函数 sort()
常见的排序算法
| 差生三人组O(n^2) | 好生三人组O（nlogn） 【运行时间：快排<归并<堆排序】 | 其他排序 |
|---|---|---|
| 冒泡排序 | 快速排序:极端情况，排序效率低 | 希尔排序 |
| 选择排序 | 堆排序：在快的排序算法中相对较慢 | 计数排序 |
| 插入排序 | 归并排序：需要额外的内存开销 | 基数排序 |
稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同
3.1 冒泡排序
基本思想
1.列表每两个相邻的数，如果前面比后面大，则交换位置
2.一趟排序完成，则无序区减少一个数， 有序区增加一个数
【每一趟，都把当前无序区最大的数，放到有序区】
def bubble_sort(nums):for i in range(len(nums)-1): # 第 i趟exchange = Falsefor j in range(len(nums)-i-1):if nums[j] > nums[j+1]:nums[j], nums[j+1] = nums[j+1], nums[j] #如果前> 后，则交换exchange = Trueif not exchange: #一趟下来，没有发生交换，代表剩下的无序区，已经是有序的return
3.2 选择排序
基本思路：
一趟排序，记录最小的数，放到第一个位置
再一趟排序，记录无序区最小数，放到第二个位置 …
def select_sort(nums):for i in range(len(nums)-1):min_index = ifor j in range(i+1, len(nums)):if nums[j] < nums[min_index]:min_index = jif min_index != i:nums[i],nums[min_index] = nums[min_index], nums[i]
3.3 插入排序
基本思路：从无序区来一个数，就插到有序区数组中排好
def insert_sort(nums):for i in range(1, len(nums)):temp = nums[i] #要排的元素j = i-1 #有序区的最后一位while j >=0 and nums[j]>temp:nums[j+1] = nums[j]j = j-1nums[j+1] = temp
3.4 快速排序
基本思路
def quick_sort(nums, left, right):if left< right: #保证至少两个元素mid = partition(data, left, right) #返回哨兵的位置，在排好的数组里面，哨兵的正确位置quick_sort(data, left, mid-1)quick_sort(data, mid+1, right)def partition(nums, left, right): #复杂度O(n）temp = nums[left]while left < right:while left < right and nums[right] >= temp: #从右边找比temp小的值right -= 1nums[left] = nums[right] #把右边的值写在左边的空位上while left < right and nums[left] <= temp:left += 1 nums[right] = nums[left] #把左边的值写到右边空位上nums[left] = temp #把temp归位return left3.6 归并排序
基本思路
def mergeSort(arr):if(len(arr)<2):return arrmiddle = int(len(arr)/2)left, right = arr[0:middle], arr[middle:]return merge(mergeSort(left), mergeSort(right))def merge(left,right):result = []while left and right:if left[0] <= right[0]:result.append(left.pop(0))else:result.append(right.pop(0))while left:result.append(left.pop(0))while right:result.append(right.pop(0))return result3.5堆排序
大根堆：一颗完全二叉树，满足任一节点都比其孩子节点大
小根堆: …，…小
堆排序内置模块
import heapqheap.heapify(nums) #建堆
heap.heappush(heap, item)
heap.heappop(heap)
topK问题：n个数，找前k大的数
思路：
1.快排 O（nlogn）
2.冒泡排序 O（nk）
3.堆排序：维护一个k大的小根堆，不断吐出小数 O(nlogk）
力扣：215.数组中第K个最大的元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:pivot = nums[0]small,equal,big = [],[],[]for i in nums:if i> pivot:big.append(i)elif i < pivot:small.append(i)else:equal.append(i)if len(big) >= k:return self.findKthLargest(big, k)elif len(big)< k and len(big) + len(equal)>=k:return pivotelse:return self.findKthLargest(small,k-len(big)-len(equal))
力扣：347.前K个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。
import heapq
class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:rec = {}for i in nums:rec[i] = rec.get(i,0) + 1stack = []for key, value in rec.items():heapq.heappush(stack, (value, key))if len(stack) > k:heapq.heappop(stack)ans = [0] * k for i in range(k-1, -1, -1):ans[i] = heapq.heappop(stack)[-1]return ans
3.7希尔排序
3.8 计数排序
def count_sort(nums, max_count = 100):count = [0 for _ in range(max_count+1)]for val in nums:count[val]+=1nums.clear()for index, val in enumerate(count):for i in range(val):nums.append(index)3.8桶排序
桶排序：表现取决于数据分布
3.9基数排序
