相信大家应该都会证，但是还是写一下吧（
ouuan 的博客里面说了，对于一个最优排列问题，如果一个比较函数 \(\text{cmp}(x,y)\) 满足严格弱序，那么经过 \(\text{cmp}\) 函数排序后的排列是最优的。
证明基于两个结论：
- 经过 \(\text{cmp}(x,y)\) 排序后的函数是唯一的（假设我们将两两不可比的元素视为等价）。
- 最后得到的排列经过任意置换操作都会变劣。
下文中，我们不妨将两两不可比的元素视为等价，容易发现这并不影响答案。
第一个结论是容易得到的，我们只需要找到严格弱序的极小元素，并把它放在第一个。
第二个结论也容易证明，我们先通过临项交换将 \(a_{p_1}\) 放在 \(a_1\) 的位置，操作完毕后，可以忽略第一个元素的影响，\(2\sim n\) 的所有元素依然满足严格弱序，采用类似的方法构造即可。所有元素归位后，我们就构造出了操作后的局面，且我们做的每一步操作都会使得结果变劣。
至此我们完成了证明。
标签：临项,text,元素,证明,正确性,交换法,弱序,cmp From： https://www.cnblogs.com/yllcm/p/16798052.html