快速排序
快速排序算法有两个核心点,分别为 “哨兵划分” 和 “递归” 。
- 哨兵划分操作: 以数组某个元素(一般选取首元素)为 基准数 ,将所有小于基准数的元素移动至其左边,大于基准数的元素移动至其右边。
- 递归: 对 左子数组 和 右子数组 递归执行 哨兵划分,直至子数组长度为 1 时终止递归,即可完成对整个数组的排序。
在时间复杂度为 O(nlogn) 级的几种排序算法中,大多数情况下效率更高,所以快速排序的应用非常广泛。
快速排序代码:
def quick_sort(nums:list,l,r):
if l>= r: return
i,j = l,r
while i < j:
while i<j and nums[j] > nums[l]: j-=1
while i<j and nums[i] < nums[l]: i+=1
nums[i], nums[j] = nums[j], nums[i]
nums[l], nums[i] = nums[i], nums[l]
quick_sort(nums,l,i-1)
quick_sort(nums,i+1,r)
return nums
nums = [6,2,5,3,7,1,4,9,8]
print(quick_sort(nums,0,len(nums)-1))
归并排序
归并排序其实就是将两个有序的列表合并成一个有序的列表。
拿到一个长数组,将其不停的分为左边和右边两份,然后以此递归分下去。然后再将它们按照两个有序数组的样子合并起来。
归并排序使用了二分法,归根到底的思想还是分而治之。
归并排序是一种稳定的排序算法(不会改变相同元素的相对位置)。
- 复杂度分析:
拆分数组的过程中,会将数组拆分 logn 次,每层执行的比较次数都约等于 n 次,所以时间复杂度是 O(nlogn)。
空间复杂度是O(n),主要占用空间的就是我们在排序前创建的长度为 n 的 result 数组。
归并排序代码:
"""
利用递归实现分治,但注意递归一定要有结束条件,比如下边separate()的结束条件就是if len(nums) <= 1
执行流建议自己设置断点看一下,理解会比较深
就是遇到自己调用自己的时候就取调用,先不执行后边没执行完的,遇到就调用
直到遇到结束条件,就返回结果然后去执行前面没执行完的递归
"""
def separate(nums):
if len(nums) <= 1:
return nums
n = len(nums)//2
left = separate(nums[:n])
right = separate(nums[n:])
return merge(left,right)
"""
1、归并排序的时候,首先想到比较用循环来实现,那么循环的条件是什么?
两个长度不一定都一样,当一个遍历完了,直接把另一个补上即可
2、然后要想到怎么比较合并
要先创建一个空数组,用来存放比完的合并的数组,依次比大小,一个插入了索引就后移
3、要考虑到一个遍历完了另一个怎么办
直接把剩下的插入即可,注意这里要用extend,一次添加多个
"""
def merge(left,right):
res = []
i = 0
j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
res.append(left[i])
i += 1
else:
res.append(right[j])
j += 1
res.extend(left[i:])
res.extend(right[j:])
return res
nums = [5,7,1,3,4,2,8]
print(separate(nums))
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)