Open MiaoRain opened 4 years ago
MiaoRain
commented
4 years ago 算法 https://labuladong.gitbook.io/algo/ 剑指offer https://leetcode-cn.com/problemset/lcof/ 精选 TOP 面试题 https://leetcode-cn.com/problemset/top/ 极客大学 https://time.geekbang.org/ 华为机考 https://www.nowcoder.com/ta/huawei 牛客算法笔面试真题精讲 https://www.nowcoder.com/study/live/350 背包九讲 https://www.kancloud.cn/kancloud/pack/70124
MiaoRain
commented
4 years ago MiaoRain
commented
4 years ago **十大排序** 参考 leetcode 912. Sort an Array #n = len(nums)
#if n <= 1:
# return List
#for i in range(n):
# for j in range(0, n-i-1):
# if nums[j] > nums[j + 1]:
# nums[j], nums[j + 1] = nums[j + 1], nums[j]
#return nums
#快排
"""
def helper(head, tail):
if head >= tail: return
l, r = head, tail
m = (r - l) // 2 + l
pivot = nums[m]
while r >= l:
while r >= l and nums[l] < pivot: l += 1
while r >= l and nums[r] > pivot: r -= 1
if r >= l:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1
helper(head, r)
helper(l, tail)
helper(0, len(nums)-1)
return nums
#插入排序
n=len(nums)
if n<=1:
return nums
for i in range(1,n):
j=i
target=nums[i] #每次循环的一个待插入的数
while j>0 and target<nums[j-1]: #比较、后移，给target腾位置
nums[j]=nums[j-1]
j=j-1
nums[j]=target #把target插到空位
return nums
#希尔排序
def shellinsert(arr,d):
n=len(arr)
for i in range(d,n):
j=i-d
temp=arr[i] #记录要出入的数
while(j>=0 and arr[j]>temp): #从后向前，找打比其小的数的位置
arr[j+d]=arr[j] #向后挪动
j-=d
if j!=i-d:
arr[j+d]=temp
n=len(nums)
if n<=1:
return nums
d=n//2
while d>=1:
shellinsert(nums,d)
d=d//2
return nums
#选择排序
n=len(nums)
if n<=1:
return nums
for i in range(0,n-1):
minIndex=i
for j in range(i+1,n): #比较一遍，记录索引不交换
if nums[j] < nums[minIndex]:
minIndex = j
if minIndex != i: #按索引交换
nums[minIndex],nums[i] = nums[i],nums[minIndex]
return nums
#堆排序
def heapify(nums, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and nums[i] < nums[l]:
largest = l
if r < n and nums[largest] < nums[r]:
largest = r
if largest != i:
nums[i], nums[largest] = nums[largest], nums[i]
heapify(nums, n, largest)
n = len(nums)
for i in range(n, -1, -1):
heapify(nums, n, i)
for i in range(n-1, 0, -1):
nums[i], nums[0] = nums[0], nums[i]
heapify(nums, i, 0)
return nums
#归并排序
#https://www.jianshu.com/p/3ad5373465fd
def mergesort(nums):
if len(nums) <= 1:
return nums
mid = len(nums) // 2 # 将列表分成更小的两个列表
#print(mid)
# 分别对左右两个列表进行处理，分别返回两个排序好的列表
left = mergesort(nums[:mid])
right = mergesort(nums[mid:])
# 对排序好的两个列表合并，产生一个新的排序好的列表
return merge(left, right)
def merge(left, right):
#合并两个已排序好的列表，产生一个新的已排序好的列表
result = [] # 新的已排序好的列表
i = 0 # 下标
j = 0
# 对两个列表中的元素 两两对比。
# 将最小的元素，放到result中，并对当前列表下标加1
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 += left[i:]
result += right[j:]
return result
#seq = [5,3,0,6,1,4]
#result = mergesort(seq)
#print ('排序后：',result)
return mergesort(nums)
#计数排序
def CountSort(lst):
n=len(lst)
num=max(lst)
count=[0]*(num+1)
for i in range(0,n):
count[lst[i]]+=1
arr=[]
for i in range(0,num+1):
for j in range(0,count[i]):
arr.append(i)
return arr
return CountSort(nums)
"""
#桶排序https://blog.csdn.net/ggdhs/article/details/90549127?depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2&utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2
def bucktetSort(numList,bucketNum):
if len(numList) == 0 or len(numList) == 1:
return numList
maxNum = numList[0]
minNum = numList[0]
for i in range(1,len(numList)): # 找到最大最小值
if numList[i] < minNum:
minNum = numList[i]
elif numList[i] > maxNum:
maxNum = numList[i]
else:
continue
bucketSize = (maxNum - minNum + 1) // bucketNum # 根据桶的数量找到每个桶的范围
buckets = [[] for i in range(bucketNum)]
for i in range(len(numList)): # 将各个数分配到各个桶
buckets[(numList[i] - minNum) // bucketSize].append(numList[i])
for i in range(bucketNum): # 桶内排序，可以使用各种排序方法
buckets[i].sort()
res = []
for i in range(len(buckets)): # 分别将各个桶内的数提出来，压入结果
for j in range(len(buckets[i])):
res.append(buckets[i][j])
return res
numlist = [11,34,23,56,8,20,66,45,54,87,78]
return bucktetSort(nums,5) # 利用5个桶
python刷这个 https://github.com/taizilongxu/interview_python python还可以看牛客网中的python教程 https://www.nowcoder.com/tutorial/10005/2ab560bdd36f46f09bcdefcd51ad5333