我正在开发一种三向分区算法，用于对数据进行排序。我可以观察到，对于大型数据集中的几个不同元素，算法进行的比较次数少于传统版本的Quick-sort。
但是，进行交换的次数高于常规版本的快速排序。
为了进行算法分析，我需要了解交换次数和比较次数对整体算法性能的影响。
liuchun227728 回答：掉期数在排序算法分析中的重要性-三向分区
在通过static analysis分析算法的效率时-也就是说，无需实际运行代码并测量其花费的时间-我们通常只关注算法的asymptotic complexity，这可以使用big O notation和相关的渐近符号进行描述。
关于大O表示法的一个重要事实是O（ f + g ）是O（ f ）或O（ g ），以较大者为准。因此，如果 f 衡量您的算法进行了多少次比较，而 g 衡量了多少次交换，那么较大的一项将是重要的。两者都会影响算法的 actual 运行时间，但是只有较大的一个才会影响渐近运行时间。
大多数排序算法执行的比较操作都比交换操作多，因此通常比较次数是很重要的。但是，如果您的算法进行的交换次数多于比较次数，那么交换次数对您的算法至关重要。
当然，如果您的算法还有其他操作，例如加法，乘法，读取或分配内存分配，那么您也应该考虑这些。您的算法最常执行的哪个操作将决定其渐近运行时间。