冒泡排序合成置换分解 [bubble-compose][edit]

任意置换 都可被写成若干个对换之积. 这里, 集合 上的置换是指 到 的双射. 而对换 则是交换元素 位置的映射.

Proof. [edit]

    冒泡排序使用若干次对换将 , 打到有序列表 , 把这些对换之积复合出的两个映射记为 . 现在观察下图, 写出 , 这当然就是 .