数据结构和算法: 归并排序/快速排序-蒲公英云

数据结构和算法: 归并排序/快速排序

港控/mmm° 2021-11-22 14:24 408阅读 0赞

快速排序和归并排序都使用了分治思想. 分治算法一般都用递归来实现

分治: 分而治之, 将一个大问题不断的分解为小问题来解决, 小的问题解决了, 大的问题也就解决了.

归并排序

思想: 将原数组不断分解为前后两部分, 直到每个数组内只有一个元素, 然后不断进行排序合并, 最后合并为一个有序数组

时间复杂度:
可以理解为不断的从中间分解需要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 mergesort(nums): length = len(nums) if length <= 1: return nums middle = int(length / 2) left = mergesort(nums[:middle]) right = mergesort(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]