一、知识点
十大排序，详情见第二个例题的代码和注释
二、例题
1.合并两个有序数组
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
index1,index2,index=m-1,n-1,m+n-1
while index1>=0 and index2>=0:
if nums1[index1]<nums2[index2]:
nums1[index]=nums2[index2]
index2-=1
else:
nums1[index]=nums1[index1]
index1-=1
index-=1
nums1[:index2+1]=nums2[:index2+1]
2.排序数组
class Solution:
# OT 稳定 O(n2)
def bubbleSort(self,arr):
for i in range(len(arr)):
# 把最大的移到后面，i--
# 因为下面有j+1所以range里面需要-1
for j in range(len(arr)-i-1):
if arr[j]>arr[j+1]:
arr[j],arr[j+1]=arr[j+1],arr[j]
return arr
# OT 稳定 O(n2)
def selectionSort(self,arr):
for i in range(len(arr)-1):
min_i=i
# 把最小的放前面去
for j in range(i+1,len(arr)):
if arr[j]<arr[min_i]:
min_i=j
if min_i!=i:
arr[i],arr[min_i]=arr[min_i],arr[i]
return arr
# OT 稳定 O(n2)
def insertionSort(self,arr):
# 选定一个i下标的元素作为需要执行插入的元素
for i in range(1,len(arr)):
temp=arr[i]
j=i
# 把i下标之前的已排序好的元素逐个与i下标元素进行比较，碰到大的往后移一给i下标元素腾位置
# 因为有j-1，需要加j>0防止越界
while j>0 and arr[j-1]>temp:
arr[j]=arr[j-1]
j-=1
arr[j]=temp
return arr
# AC 不稳定 O(nlogn)~O(n2)
def shellSort(self,arr):
gap=len(arr)//2
# 分隔开的序列进行希尔排序，随后缩短间隔直到等于1
while gap>0:
# 这部分是插入排序改装版，将1替换为gap
for i in range(gap,len(arr)):
temp=arr[i]
j=i
while j>gap-1 and arr[j-gap]>temp:
arr[j]=arr[j-gap]
j-=gap
arr[j]=temp
gap=gap//2
return arr
# AC 稳定 O(nlogn) 空间：O(n)
def merge(self,left_arr,right_arr):
arr=[]
# 左右数组（队列）分别比较队头元素，比较结果放入新的数组中
while left_arr and right_arr:
if left_arr[0] <= right_arr[0]:
arr.append(left_arr.pop(0))
else:
arr.append(right_arr.pop(0))
# 处理剩下的
while left_arr:
arr.append(left_arr.pop(0))
while right_arr:
arr.append(right_arr.pop(0))
return arr
def mergeSort(self,arr):
# 递归终止条件
if len(arr)<2:
return arr
mid=len(arr)//2
left_arr,right_arr=arr[:mid],arr[mid:]
# 合并需要分别通过递归排序的左右数组
return self.merge(self.mergeSort(left_arr),self.mergeSort(right_arr))
# AC 不稳定 O(nlogn)
def partition(self,arr,low,high):
# 后面要+1
i=low-1
# 选定的中心分隔左右的值
pivot=arr[high]
# 快（j）慢（i）指针：j遍历同时比较，将i下标的位置变成比pivot小的数
for j in range(low,high):
if arr[j]<=pivot:
i+=1
arr[i],arr[j]=arr[j],arr[i]
# 遍历完之后，i的后一位刚好是中心位置，和最后一个位置交换即可
arr[i+1],arr[high]=arr[high],arr[i+1]
return i+1
def randomPartition(self,arr,low,high):
# 随机选取一下pivot
i=random.randint(low,high)
arr[i],arr[high]=arr[high],arr[i]
return self.partition(arr,low,high)
def quickSort(self,arr,low,high):
# low=high的时候是递归终止条件，无操作
if low<high:
pi=self.randomPartition(arr,low,high)
self.quickSort(arr,low,pi-1)
self.quickSort(arr,pi+1,high)
return arr
# AC 不稳定 O(nlogn) 空间：O(1)
def heapify(self,arr,index,end):
left=index*2+1
right=left+1
# end是最后一个节点的下标
while left<=end:
# 找最大的值
max_index=index
if arr[left]>arr[max_index]:
max_index=left
# right防止越界，看while的条件
if right<=end and arr[right]>arr[max_index]:
max_index=right
# 此时说明全部调整完了，退出
if index==max_index:
break
arr[index],arr[max_index]=arr[max_index],arr[index]
index=max_index
left=index*2+1
right=left+1
def buildMaxHeap(self,arr):
size=len(arr)
# 0到(size-2)//2是非叶子节点的序号，应该从底到顶调整
for i in range((size-2)//2,-1,-1):
self.heapify(arr,i,size-1)
return arr
def maxHeapSort(self,arr):
self.buildMaxHeap(arr)
size=len(arr)
for i in range(size):
arr[0],arr[size-i-1]=arr[size-i-1],arr[0]
self.heapify(arr,0,(size-1)-(i+1))
return arr
# AC 稳定 O(n+k)
def countingSort(self,arr):
arr_min,arr_max=min(arr),max(arr)
size=arr_max-arr_min+1
counts=[0 for _ in range(size)]
# 计数数组：key代表偏移值，value代表计数
for num in arr:
# -arr_min是因为有负数
counts[num-arr_min]+=1
# 累计数组：key代表偏移值，value代表累计计数
# 下标越大累计值比较大，下标代表偏移值
for j in range(1,size):
counts[j]+=counts[j-1]
# 新的数组空间存结果
res=[0 for _ in range(len(arr))]
# 通过原数组的元素值作为索引获取累计值，用累计值作为新数组的索引并将value设置为原数组元素值
for i in range(len(arr)):
# -1是因为下标问题 counts[arr[i]-arr_min]-1代表下标
res[counts[arr[i]-arr_min]-1]=arr[i]
# 累计值-1防止索引重复
counts[arr[i]-arr_min]-=1
return res
# AC 稳定 O(n) 空间：O(n+m)
def bucketSort(self,arr,bucket_size=5):
# bucket_size是桶区间范围
arr_min,arr_max=min(arr),max(arr)
bucket_count=(arr_max-arr_min)//bucket_size+1
# 建桶
buckets=[[] for _ in range(bucket_count)]
for num in arr:
buckets[(num-arr_min)//bucket_size].append(num)
res=[]
# 对每个桶分别进行排序
for bucket in buckets:
self.insertionSort(bucket)
res.extend(bucket)
return res
# NAC 不能处理负数 稳定 O(k*n) 空间：O(n+k)
def radixSort(self,arr):
# 取位的个数
size=len(str(max(arr)))
# i表示第几位，从最低位开始，对每一位进行操作
for i in range(size):
# 每个bucket分别装0-9，buckets的索引代表某一位的数是索引值的集合
buckets=[[] for _ in range(10)]
for num in arr:
buckets[num//(10**i)%10].append(num)
arr.clear()
# 遍历每个bucket，按某一位值的大小逐个重新存放到arr中（即按位排序）
for bucket in buckets:
for num in bucket:
arr.append(num)
return arr
def sortArray(self, nums: List[int]) -> List[int]:
# return self.bubbleSort(nums)
# return self.selectionSort(nums)
# return self.insertionSort(nums)
# return self.shellSort(nums)
# return self.mergeSort(nums)
# return self.quickSort(nums,0,len(nums)-1)
# return self.maxHeapSort(nums)
# return self.countingSort(nums)
return self.bucketSort(nums)
# return self.radixSort(nums)
3.有序数组的平方
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
i,j,k=0,len(nums)-1,len(nums)-1
ans=[-1]*len(nums)
while i<=j:
if nums[i]**2>nums[j]**2:
ans[k]=nums[i]**2
i+=1
else:
ans[k]=nums[j]**2
j-=1
k-=1
return ans
4.数组的相对排序
class Solution:
def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
min_arr2,max_arr2=min(arr2),max(arr2)
counts=[0]*(max_arr2-min_arr2+1)
rest=[]
for num in arr1:
if num not in arr2:
rest.append(num)
else:
counts[num-min_arr2]+=1
ans=[]
for num in arr2:
for i in range(counts[num-min_arr2]):
ans.append(num)
return ans+sorted(rest)
5.对链表进行插入排序
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def insertionSortList(self, head: ListNode) -> ListNode:
dummy=ListNode(next=head)
while head and head.next:
temp=head.next
if temp.val>=head.val:
head=head.next
continue
else:
pre=dummy
while pre.next.val<=temp.val:
pre=pre.next
head.next=head.next.next
temp.next=pre.next
pre.next=temp
return dummy.next