快速排序和归并排序都使用了分治思想. 分治算法一般都用递归来实现
分治: 分而治之, 将一个大问题不断的分解为小问题来解决, 小的问题解决了, 大的问题也就解决了.
归并排序
思想: 将原数组不断分解为前后两部分, 直到每个数组内只有一个元素, 然后不断进行排序合并, 最后合并为一个有序数组
- 时间复杂度:
可以理解为不断的从中间分解需要O(logn)次, 每次都需要对n个元素排序, 所以需要O(nlogn)- 最好: O(nlogn)
- 最坏: O(nlogn)
- 平均: O(nlogn)
- 空间复杂度: O(n)
虽然每次排序都需要申请内存, 但是使用完毕后都释放了, 最多的一次使用内存是O(n)
# coding:utf-8
def merge(left, right):
res = []
while left and right:
# 此处决定了排序是否稳定. 需要保证针对相等的元素排序后按照出现的先后顺序进行排列
if left[0] < right[0]:
res.append(left.pop(0))
else:
res.append(right.pop(0))
if left:
res.extend(left)
if right:
res.extend(right)
return res
def merge_sort(nums):
length = len(nums)
if length <= 1:
return nums
middle = int(length / 2)
left = merge_sort(nums[:middle])
right = merge_sort(nums[middle:])
return merge(left, right)
if __name__ == "__main__":
nums = [4, 3, 6, 9, 7, 0, 1, 9, 3]
assert merge_sort(nums) == [0, 1, 3, 3, 4, 6, 7, 9, 9]
快速排序
使用了分治思想. 以数组中的一个数key为基准, 把小于key的数放到左边, 把大于key的数放到右边, 然后使用同样的方法作用于key两边的区间
- 时间复杂度:
- 最坏:
O(n**2)
比如原始数组就是有序的, 那么当尾端元素为key时, 分区导致一个区域为空. 所以需要分区n次, 每次平均对n/2个元素排序, 所以是O(n**2) - 最好: O(nlogn)
分区非常均衡 - 平均: O(nlogn)
- 最坏:
- 空间复杂度: O(n)/O(1)
- 是否稳定: 不稳定
方案一
# coding:utf-8
"""
空间复杂度: O(n)
"""
def quick_sort(nums):
if len(nums) <= 1:
return nums
key = nums.pop()
# 不考虑空间消耗
less, over = [], []
for i in nums:
if i < key:
less.append(i)
else:
over.append(i)
return quick_sort(less) + [key] + quick_sort(over)
if __name__ == "__main__":
nums_1 = [4, 3, 6, 9, 7, 0, 1, 9, 3]
assert quick_sort(nums_1) == [0, 1, 3, 3, 4, 6, 7, 9, 9]
方案二
# coding:utf-8
"""
空间复杂度: O(1)
"""
def partition(nums, low, high):
key_index = high
key = nums[key_index]
while low < high:
while low < high and nums[low] <= key:
low += 1
while low < high and nums[high] >= key:
high -= 1
nums[low], nums[high] = nums[high], nums[low]
nums[low], nums[key_index] = nums[key_index], nums[low]
return low
def interval(nums, low, high):
if low < high:
new_index = partition(nums, low, high)
interval(nums, 0, new_index - 1)
interval(nums, new_index + 1, high)
return nums
def quick_sort(nums):
res = interval(nums, 0, len(nums) - 1)
return res
if __name__ == "__main__":
nums_2 = [4, 3, 6, 9, 7, 0, 1, 9, 3]
assert quick_sort(nums_2) == [0, 1, 3, 3, 4, 6, 7, 9, 9]
区别
- 归并排序:
排序顺序是从下到上, 先解决子问题, 再合并分区. 缺点: 不是原地排序, 合并需要占用额外空间 - 快速排序:
排序顺序是从上到下, 先分区, 再解决子问题. 可以通过合理的选择key来避免时间复杂度为最坏的O(n**2)
优化key的选择
快速排序中最坏情况是分区后一个分区是空, 另一个分区全满, 这种一般是key的选择不当导致的, 比如一个有序数组选择了第一个或最后一个元素为key, 可以采用以下方法优化
- 三位数取中
取头部, 尾部, 中间的元素, 将3个数的中间值作为分界线 - 随机法
从数组中随机取一个数作为分界线
资料
- <<大话数据结构>>
- <<漫画算法>>
- <<数据结构和算法-极客时间>>
