快速排序优化——荷兰国旗与随机快排

发表于 |
如何借助荷兰国旗问题，一步步将快排优化至稳定的O(N*logN)

快速排序

image-20200423062433436 image-20200423062734100 小于等于num, 当前数和<=区下一个数交换 大于num, 直接跳下一个

分三段: 荷兰国旗问题
image-20200423070643055
image-20200423063218126
[ i ] == num, i++
[ i ] < num, [ i ] 与<区右一个交换, <区右扩1位, i++
[ i ] > num, [ i ] 与>区左一个交换, >区左扩1位, i不懂, 这个数还没比较过

荷兰国旗1: 以arr[R] 作为划分值
image-20200423064734526
image-20200423064753839
image-20200423065349613

image-20200423070703395 image-20200423065546159 image-20200423065659272 image-20200423065804180 image-20200423125703988 image-20200423065826323 image-20200423065942356 ![image-20200423070051147](快速排序优化——荷兰国旗与随机快排/image-20200423070051147.png)

1.0/2.0 时间复杂度

image-20200423125738958 image-20200423070015988 image-20200423125821385 image-20200423070153215![image-20200423070221686](快速排序优化——荷兰国旗与随机快排/image-20200423070221686.png)

num在中间, 时间复杂度最低

概率累加 = O(N * logN)

差情况随机发生
image-20200423070613686