本文最后更新于419 天前，其中的信息可能已经过时，如有错误请发送邮件到2446865563@qq.com
1.题目基本信息
1.1.题目描述
给你一个整数数组 nums，请你将该数组升序排列。
1.2.题目地址
https://leetcode.cn/problems/sort-an-array/description/
2.解题方法
2.1.解题思路
十个经典的排序算法：直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序、归并排序、基数排序、计数排序、桶排序
2.2.解题步骤
-
3.解题代码
Python代码
class Solution:
# 10.桶排序(O(n+k),O(n^2),O(n+k),稳定)
def sortArray(self, nums: List[int]) -> List[int]:
# 获取分组个数
maxVal,minVal=max(nums),min(nums)
if minVal==maxVal:
return nums
# 获取桶的个数和分隔间隔
bucketCnt=int((maxVal-minVal)**0.5)
bucketWidth=(maxVal-minVal)/bucketCnt
# 创建桶
buckets=[[] for i in range(bucketCnt)]
# 遍历,将数据加到桶中
for num in nums:
bucketIndex=int((num-minVal)//bucketWidth)
bucketIndex=bucketIndex if bucketIndex<bucketCnt else bucketCnt-1
buckets[bucketIndex].append(num)
result=[]
# 将各个桶中的数据进行排序
for bucket in buckets:
bucket.sort()
result.extend(bucket)
return result
# 9.计数排序[神奇的过了](0(n+k),0(n+k),0(n+k),O(k),稳定)
def sortArray9(self, nums: List[int]) -> List[int]:
minVal,maxVal=min(nums),max(nums)
counters=[0]*(maxVal-minVal+1)
for num in nums:
counters[num-minVal]+=1
index=0
for i in range(len(counters)):
for _ in range(counters[i]):
nums[index]=i+minVal
index+=1
return nums
# 8.基数排序[错误,因为基数排序只适合正整数/负整数等排序](O(nk),O(nk),O(nk),O(n+k),稳定)
def sortArray8(self, nums: List[int]) -> List[int]:
length=len(nums)
maxVal=max(nums)
exp=1
while maxVal//exp>0:
# 第一步,统计该分位数字的个数
counters=[0]*10
for num1 in nums:
num=(num1//exp)%10
counters[num]+=1
# 第二步,统计该分为各个数字的最后一个的索引
for i in range(1,10):
counters[i]+=counters[i-1]
# 第三步,倒序遍历,将数字添加到output中
output=[0]*length
for j in range(length-1,-1,-1):
num=(nums[j]//exp)%10
output[counters[num]-1]=nums[j]
counters[num]-=1
# 将output赋值给nums
nums=output
exp*=10
return nums
# 7.归并排序(O(nlogn),O(nlogn),O(nlogn),O(n),稳定)
def sortArray7(self, nums: List[int]) -> List[int]:
# 归并排序,左毕右开
def mergeSort(arr,left,right):
if right-left<=1:
return
mid=(right-left)//2+left
mergeSort(arr,left,mid)
mergeSort(arr,mid,right)
copyLeftSortArr=arr[left:mid].copy()
copyRightSortArr=arr[mid:right].copy()
copyLeftSortArr.append(inf)
copyRightSortArr.append(inf)
# print(copyLeftSortArr,copyRightSortArr)
i,j,k=0,0,0
while k<right-left:
if copyLeftSortArr[i]<copyRightSortArr[j]:
arr[left+k]=copyLeftSortArr[i]
i+=1
else:
arr[left+k]=copyRightSortArr[j]
j+=1
k+=1
mergeSort(nums,0,len(nums))
# print(nums)
return nums
# 6.堆排序[附带堆的下滤、上滤、创建、push、pop算法函数](O(nlogn),O(nlogn),O(nlogn),O(1),不稳定)
def sortArray6(self, nums: List[int]) -> List[int]:
# 堆的上滤操作
def upPercolate(heap,pos):
parentPos=(pos-1)//2
while parentPos>=0 and heap[pos]<heap[parentPos]:
heap[pos],heap[parentPos]=heap[parentPos],heap[pos]
pos=parentPos
parentPos=(pos-1)//2
# 堆的下滤操作
def downPercolate(heap,pos):
length=len(heap)
minChildPos=2*pos+1 # 获取最小根节点
while minChildPos<length:
if minChildPos+1<length and heap[minChildPos+1]<heap[minChildPos]:
minChildPos=minChildPos+1
if heap[pos]>heap[minChildPos]:
heap[pos],heap[minChildPos]=heap[minChildPos],heap[pos]
pos=minChildPos
minChildPos=2*pos+1
# 构建堆
def heapify(heap):
# 将所有的父节点逆向进行上滤
length=len(heap)
for i in range(length//2,-1,-1):
downPercolate(heap,i)
# 弹出堆
def heappop(heap):
# 将堆顶最小值和最后一个值互换,然后弹出最后一个(即交换前的堆顶),然后将堆顶下滤进行调整
length=len(heap)
heap[0],heap[length-1]=heap[length-1],heap[0]
ret=heap.pop()
downPercolate(heap,0)
return ret
# 堆增加节点(这里堆排序没有用到)
def heappush(heap,val):
# 增加节点到数组末尾并进行上滤
heap.append(val)
upPercolate(heap,len(heap)-1)
heapify(nums)
# heappush(nums,-10)
result=[]
while len(nums)>0:
result.append(heappop(nums))
return result
# 5.选择排序[超时](O(n^2),O(n^2),O(n^2),O(1),不稳定)
def sortArray5(self, nums: List[int]) -> List[int]:
length=len(nums)
for i in range(length):
for j in range(i,length):
if nums[j]<nums[i]:
nums[j],nums[i]=nums[i],nums[j]
return nums
# 4.快速排序[超时](O(nlogn),O(nlogn),O(n^2),O(logn),不稳定)
def sortArray4(self, nums: List[int]) -> List[int]:
def quickSort(nums,left,right):
if left>=right:
return
# 选择基准值
baseVal=random.choice(nums)
l,r=left-1,right+1
while l<r:
# 至少一次递增,防止死循环
l+=1
r-=1
# 找到左边第一个大于baseVal的索引
while nums[l]<baseVal:
l+=1
# 找出右边第一个小于baseVal的索引
while nums[r]>baseVal:
r-=1
if l<r:
nums[l],nums[r]=nums[r],nums[l]
quickSort(nums,left,r)
quickSort(nums,r+1,right)
quickSort(nums,0,len(nums)-1)
# print(nums)
return nums
# 3.冒泡排序[超时](O(n),O(n^2),O(n^2),O(1),稳定)
def sortArray3(self, nums: List[int]) -> List[int]:
length=len(nums)
for i in range(length):
flag=False # 标记该轮冒泡是否有交换
for j in range(length-i-1):
if nums[j+1]<nums[j]:
nums[j+1],nums[j]=nums[j],nums[j+1]
flag=True
if not flag:
break
# print(nums)
return nums
# 2.希尔排序(O(n),O(n^1.3),O(n^2),O(1),不稳定)
def sortArray2(self, nums: List[int]) -> List[int]:
dist=length=len(nums)
while dist>0:
dist=int(dist//2)
for i in range(dist):
for j in range(i,length,dist):
temp=nums[j]
k=j-dist
while k>=0 and nums[k]>temp:
nums[k+dist]=nums[k]
k-=dist
nums[k+dist]=temp
# print(nums)
return nums
# 1.直接插入排序[超时](O(n),O(n^2),O(n^2),O(1),稳定)
def sortArray1(self, nums: List[int]) -> List[int]:
length=len(nums)
for i in range(length):
temp=nums[i]
j=i-1
while j>=0 and temp<nums[j]:
nums[j+1]=nums[j]
j-=1
nums[j+1]=temp
# print(nums)
return nums4.执行结果
