QuickSort
QuickSort 版本一
依据
QuickSort版本一其实是依据 ‘荷兰国旗问题' 实现的。只不过这次划分时只有大于或者小于num的数。
思路
- 取数组最右的数作为
num，划分为两个区域(大于、小于) - 在两个区域里重复第一部操作
QuickSort 版本二
依据
QuickSort版本二就是实打实的依据 ‘荷兰国旗问题' 实现的。
思路
- 取数组最右的数作为
num，划分为两个区域(大于、小于，等于) - 在两个(大于、小于)区域里重复第一部操作
QuickSort 版本三
思考
版本一和版本二本质差不多，版本二较版本一的优化并没有多少。
之前一直考虑的情况都是能够分出三个部分，但如果只能分出两个部分
(大于和等于、小于和等于)呢
/******假如给一个数组[1，2，3，4，5，6，7，8，9]******/
[1，2，3，4，5，6，7，8，]9]
[1，2，3，4，5，6，7，]8，9]
[1，2，3，4，5，6，]7，8，9]
.
.
.
由于每次只能往一个区域进行递归，最后的时间复杂度也只能是0(N^2).
思路
- 随机取数组中的一个数作为
num，与最右数交换，划分区域(大于、小于、等于) - 在两个区域里重复第一部操作
总结
最后版本的时间复杂度也只能依靠概率来决定了，版本三的依据依旧是荷兰国旗问题
