数据结构与算法-3
1. 归并排序
- 递归：O(N * logN) ，求解方法见：上一篇博客
- 非递归：O(N * logN)
- 对比O(N^2)算法： O(N^2)算法浪费了比较行为，因为每次循环都只做了一次实质替换，O(N*logN)算法的每次迭代都将比较行为的结果保留了下来供下一次比较使用
2.归并排序算法练习
示例代码 MergeSort
- 求数组最小和问题（求数组中 每个数左侧所有比它小的数的和 的和）
- 求降序对问题（数组中每个数与其右侧比它小的数组成的二元组）：上题反过来即可
3.快速排序
Partition过程：
- 给定一个数组arr，和一个整数num，请把小于num的数放在数组的左边，大于num的数放在数组的右边，要求额外空间复杂度O(1),时间复杂度O(N)
- 三色问题/荷兰国旗问题—>快排V2.0（快排V1.0即partition函数只返回一个基准值位置，而V2.0返回了一组基准值的左右边界,时间复杂度都为O(N)）
- 快排 V3.0，随机快排，在V2.0基础上使用随机基准值，时间复杂度为O(N*logN)
