2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
'''冒泡排序'''
"""
def BubbleSort(nums):
listLength = len(nums)
while listLength > 0:
for i in range(listLength - 1):
if nums[i] > nums[i+1]:
nums[i], nums[i+1] = nums[i+1], nums[i]
listLength -= 1
return nums
"""
def BubbleSort(nums):
for i in range(len(nums)):
for j in range(len(nums) - i - 1):
if nums[j] > nums[j+1]:
nums[j], nums[j+1] = nums[j+1], nums[j]
return nums
nums = [5, 2, 8, 4, 7, 4, 3, 9, 2, 0, 16,1]
print(BubbleSort(nums))
'''快速排序'''
def QuickSort(nums, start, end):
if start < end:
i, j = start, end
base = nums[i]
while i < j:
while i < j and nums[j] >= base:
j -= 1
nums[i] = nums[j]
while i < j and nums[i] <= base:
i += 1
nums[j] = nums[i]
nums[i] = base
QuickSort(nums, start, i - 1)
QuickSort(nums, i+1, end)
nums = [9,4,10,8,13,2,15,7]
QuickSort(nums, 0, len(nums)-1)
print(nums)
'''插入排序'''
def InsertSort(nums):
for i in range(len(nums)-1):
if nums[i] > nums[i+1]:
while i>=0 and nums[i] > nums[i+1]:
nums[i], nums[i+1] = nums[i+1], nums[i]
i -= 1
return nums
nums = [9,4,10,8,13,2,15,7]
print(InsertSort(nums))
'''希尔排序'''
#①第一层循环 gap折半 直到gap=1
#②二层三层循环直接插入排序
def ShellSort(nums):
gap = len(nums) // 2
while gap >= 1:
for i in range(gap, len(nums)):
for j in range(i-gap, -1, -gap):
if nums[j] > nums[j+gap]:
nums[j], nums[j+gap] = nums[j+gap], nums[j]
gap = gap // 2
return nums
nums = [9,4,10,8,13,2,15,7]
print(ShellSort(nums))
'''选择排序'''
def SelectSort(nums):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[j] < nums[i]:
nums[j], nums[i] = nums[i], nums[j]
return nums
nums = [5, 2, 8, 4, 7, 4, 3, 9, 2, 0, 1,16]
print(SelectSort(nums))
Le tas maximum stocke toujours la valeur maximale au nœud racine de l'arborescence.
Pour un tas min, l'élément du nœud racine est toujours la plus petite valeur de l'arborescence.
Scénarios d'application
Par exemple, pour trouver les 10 plus grands nombres parmi 1 milliard de nombres, construisez toujours un petit tas supérieur avec seulement 10 éléments. S'il est plus petit que le haut du tas, il ne sera pas traité s'il est plus grand que le haut. du tas, replacez le haut du tas, puis procédez en séquence.
Par exemple, pour trouver les 10 premiers nombres les plus petits parmi 1 milliard de nombres, construisez toujours un grand tas supérieur avec seulement 10 éléments. S'il est plus grand que le sommet du tas, il ne sera pas traité s'il est plus petit que le sommet. du tas, replacez le haut du tas, puis procédez en séquence.
Généralement, le grand tas supérieur est utilisé par ordre croissant et le petit tas supérieur est utilisé par ordre décroissant.
'''构造大顶堆'''
def HeapBuild(nums):
l = len(nums) - 1
# 构造大顶堆，从非叶子节点开始倒序遍历，因此是l//2 -1 就是最后一个非叶子节点
for i in range(len(nums)//2 - 1, -1, -1):
HeapSort(nums, i, l)
# 上面的循环完成了大顶堆的构造，那么就开始把根节点跟末尾节点交换，然后重新调整大顶堆
for j in range(l, -1, -1):
nums[0], nums[j] = nums[j], nums[0]
HeapSort(nums, 0, j-1)
return nums
def HeapSort(nums, i, l):
left, right = 2 * i + 1, 2 * i + 2 # 左右子节点的下标
index = i
# 构造大顶推
if left <= l and nums[i] < nums[left]:
index = left
if right <= l and nums[left] < nums[right] and nums[i] < nums[right]:
index = right
if index != i:
nums[i], nums[index] = nums[index], nums[i]
HeapSort(nums, index, l)
nums = [17, 13, 40 , 22, 31, 14, 33, 56, 24, 19 ,10, 41, 51, 42, 26]
print('使用大顶堆排序：', HeapBuild(nums))
'''构造小顶堆'''
def SmallHeapBuild(nums):
l = len(nums) - 1
# 从非叶子节点开始倒序遍历，因此是l//2 -1 就是最后一个非叶子节点
for i in range(len(nums)//2 - 1, -1, -1):
SmallHeapSort(nums, i, l) # 小顶堆构造函数
# 上面的循环完成了小顶堆的构造，那么就开始把根节点跟末尾节点交换，然后重新调整大顶堆
# 使用小顶堆进行降序，nums[0]是最小的，放到最后
for j in range(l, -1 ,-1):
nums[0], nums[j] = nums[j], nums[0]
SmallHeapSort(nums, 0, j-1)
return nums
def SmallHeapSort(nums, i, l):
left, right = 2 * i + 1, 2 * i + 2 # 左右子节点的下标
index = i
# 构建小顶堆
if left <= l and nums[i] > nums[left]:
index = left
if right <= l and nums[left] > nums[right] and nums[i] > nums[right]:
index = right
if index != i:
nums[i], nums[index] = nums[index], nums[i]
SmallHeapSort(nums, index, l)
nums = [17, 13, 40 , 22, 31, 14, 33, 56, 24, 19 ,10, 41, 51, 42, 26]
print('使用小顶堆倒排序', SmallHeapBuild(nums))
def MergeBuild(nums):
if len(nums) == 1:
return nums
mid = len(nums) // 2
left = nums[:mid]
right = nums[mid:]
l1 = MergeBuild(left)
l2 = MergeBuild(right)
return MergeSort(l1, l2)
def MergeSort(left, right):
res = []
while len(left) and len(right):
if left[0] < right[0]:
res.append(left.pop(0))
else:
res.append(right.pop(0))
res += left
res += right
return res
if __name__ == '__main__':
nums = [5, 2, 8, 4, 7, 4, 3, 9, 2, 0, 1,16]
res = MergeBuild(nums)
print(res)
'''二分查找'''
def BinarySearch(target, nums):
low = 0
high = len(nums)-1
while low <= high:
mid = (low + high) // 2
if nums[mid] == target:
return 'target in nums'
elif nums[mid] < target:
low = mid + 1
else:
high = mid - 1
return 'target not in nums'
nums = [2, 4, 7, 8, 9, 10, 13, 15, 19]
print(BinarySearch(13, nums))
print(BinarySearch(20, nums))
Il se consacre à la recherche technologique depuis plus de 30 ans et maîtrise divers langages tels que java, linux, javascript, php, css, etc. Il a apporté de nombreuses contributions dans le domaine de l'open source. station de documentation pour les développeurs pour partager certains problèmes de développement technologique pour référence future.
