SJT算法是一种全排列生成算法。在该算法中，不断的寻找一种相邻元素相互交换的顺序，根据这种交换的顺序，依次计算下一个排列。该算法的算数复杂度是O(n*n!)。

SJT 算法，即 Steinhaus–Johnson–Trotter algorithm，是一种全排列生成算法。在该算法中，不断的寻找一种相邻元素相互交换的顺序，根据这种交换的顺序，依次计算下一个排列。该算法的算数复杂度是 O(n*n!)。

算法原理

SJT 算法，即 Steinhaus–Johnson–Trotter algorithm，是一种全排列生成算法。在该算法中，不断的寻找一种相邻元素相互交换的顺序，根据这种交换的顺序，依次计算下一个排列。在 SJT 算法中，每次循环都进行一次满足条件的相邻元素的交换，直到不存在满足条件的可交换的元素，此时说明所有排列的情况均已输出，算法结束。

算法步骤

设[a1,a2 ... aN] 每一项都有向左或向右两个移动方向。

1) 初始化所有移动方向向左；

2) 如果移动方向的值比自己小，就可移动，比如 <1 >2 <3, 每个数字前箭头的方向表示该数字的移动方向，3 可以移动，2 和 1 不可移动；

3) 移动最大的可以动项，在上面例子中就是数字 3；

4) 将所有比移动项大的项方向反转，重复第三步，直到不能移动为止。

算法性能分析

记要全排列的元素总数为 n，全排列一共 n!种排列，在每次枚举下一个排列时，我们都在上一个排列中寻找最大的可移动项，然后对其进行移动，因此总体复杂度是 O(n*n!)。