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

港控/mmm° 2021-11-22 14:24 347阅读 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 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个数的中间值作为分界线
 *  随机法  
    从数组中随机取一个数作为分界线

### 资料 ###

*  <>
 *  <>
 *  <>

![1634914-20190623172836409-113676237.jpg][]

转载于:https://www.cnblogs.com/zlone/p/11173732.html

[1634914-20190623172836409-113676237.jpg]: /images/20211122/6f884a00f41541a1a330d976cec89ea9.png