月度归档:2018年10月

QuickSort Dijkstra 3-Way Partitioning

思想

原始的基于 2-Way Partition 的快排在遇到大量重复数据时会退化为 O(n^2),为了解决这个问题,3-Way 快排被提出了。通过将区间分割为“小于”、“等于”和“大于”(基准数)三个部分,获得了趋近 O(nlogn) 的复杂度。不同于 2-Way 快排的是,我们在此选取一个基准数[……]

Read more