网站建设课程设计内容,匠王红木在那个网站做众筹,网站改完域名打开速度慢,保定附近的做网站价格数据结构 —— 手写排序算法 一、堆排序二、快速排序 能手撸堆排序和快速排序#xff0c;相信你在面试中已经能应付大部分排序问题了。
一、堆排序
建堆算法在面试中非常常见#xff0c;我曾经就遇到过。因此为避免踩坑#xff0c;特此开记录帖。堆必须是一棵完全二叉树相信你在面试中已经能应付大部分排序问题了。
一、堆排序
建堆算法在面试中非常常见我曾经就遇到过。因此为避免踩坑特此开记录帖。堆必须是一棵完全二叉树分为
大根堆。每个父节点元素 子节点小根堆。每个父节点元素 子节点
一、参考文章或视频链接[1] 【【从堆的定义到优先队列、堆排序】 10分钟看懂必考的数据结构——堆】- bilibili[2] 《算法》(第4版) - chapter 2.4 堆排序 - bilibili
# coding:utf-8
# Time: 2024/1/5 下午9:10
# Author: 键盘国治理专家
# File: quick_sort.py
# Description:# 大根堆建堆然后交换到数组最末尾就是升序排序了
def heapify(arr, n, i):largest i # 初始化最大值为当前位置ileft 2*i 1 # 左子节点right 2*i 2 # 右子节点#if left n and arr[i] arr[left]: # 左子节点存在且比当前位置大largest left # 更新最大值为左子节点的位置if right n and arr[largest] arr[right] # 右子节点存在且比当前位置大largest rightif largest ! i: # 最大值的位置已经被改动了不再等于开始时的i了则需要将最大值上浮arr[i], arr[largest] arr[largest], arr[i]heapify(arr, n, largest) # 再递归重复此过程堆交换后的子树继续堆化def heap_sort(arr):n len(arr)# (1)构建最大堆从最后一个非叶子节点开始依次进行堆化也就是自底向上建堆可以看参考视频[2]。最后一个非叶子节点这样理解如果将叶子节点视作一棵树那么孤零零的一个节点本身就是一个堆。所以不需要建堆但这不意味着这些叶子节点在随后的建堆过程中不参与交换只是不以这些叶子节点为中心进行建堆。for i in range(n//2 - 1, -1, -1):heapify(arr, n, i) # arr为建堆数组n表示建堆范围为[0,n-1]共n个i表示堆arr[i]元素进行调整建堆for i in range(n-1, -1, -1):arr[i], arr[0] arr[0], arr[i]heapify(arr, i, 0) # 对[0,i-1]的元素继续建堆if __name__ __main__:# 示例用法nums [10, 80, 30, 90, 40, 50, 70, -123]print(排序前的数组为, nums)heap_sort(nums)print(排序后的数组:, nums)
二、快速排序
二、参考文章或视频链接[1] 《快速排序——hoare版本挖坑法双指针法》- CSDN[2] 【快速排序双指针法动画演示】- bilibili
快速排序重在轴点pivot的选择与交换过程上。
# coding:utf-8
# Time: 2024/1/5 下午9:10
# Author: 键盘国治理专家
# File: quick_sort.py
# Description:def quick_sort(nums, low, high):if low high:# 找到轴的位置。这句话是说轴一旦确定了就意味着这个元素已经被放置在数组的正确位置了后面不会再变动partition函数本身就带有排序性质的交换操作pivot partition(nums, low, high)# print(arr)quick_sort(nums, low, pivot - 1)quick_sort(nums, pivot 1, high)def partition(nums, low, high):# (1)最左边的元素被选为轴点pivot_index lowwhile low high:# (2)high从右往左遍历直到找到一个比轴点小的数字并交换while nums[high] nums[pivot_index]:high - 1if nums[pivot_index] nums[high]:nums[pivot_index], nums[high] nums[high], nums[pivot_index]pivot_index high# (3)low从左往右遍历直到找到一个比轴点大的数字并交换while nums[low] nums[pivot_index]:low 1if nums[low] nums[pivot_index]:nums[pivot_index], nums[low] nums[low], nums[pivot_index]pivot_index low# (4)返回轴点的最终位置return pivot_indexif __name__ __main__:nums [10, 80, 30, 90, 40, 50, 70, -123]print(排序前的数组为, nums)quick_sort(nums, 0, len(nums) - 1)print(排序后的数组为, nums)
