swap 为什么要这么写：
template < typename T >
void _swap( T &a, T &b )
{
        a = a + b;
        b = a - b;
        a = a - b;
}
为啥不用临时变量？ 如：temp = a;  a = b; b = temp;

虽然那样写比较酷，但是代码效率不如用临时变量。

for ( i=0; i<rang-1; i++ )
{
         if ( *( first+i ) <= *( first+i+1 ) )
         {
                x = i;
         }
}
可以写成这样来提速：
for ( i=rang-2; i>=0; i-- )
{
         if ( *( first+i ) <= *( first+i+1 ) )
         {
                x = i;
                break;  // 跳出多余的循环
         }
}

[ Last edited by WinHack on 2005-10-30 at 12:31 ]

for ( i=x; i<rang; i++ )
{
        if ( *( first+x ) <= *( first+i ) )
        {
               j = i;
        }
}
可以写成这样来提速：
j = x+1; //我们事先已经知道 j >= x+1
for ( i=x + 2; i<rang; i++ )
{
        if ( *( first+x ) <= *( first+i ) )
        {
               j = i;
        }
}

[ Last edited by WinHack on 2005-10-30 at 12:31 ]

这段好像就是把i元素和rang-(i-x)元素互换， 能解释一下为什么这么做么？
for ( i=x+1; i<rang; i++ )
{
          if ( i != rang + x - i )
          {
                int nSwap = rang + x - i;
               _swap( *( first+i ), *( first+ ( rang+x-i ) ) );
           }
           if ( ( i + 1 ) * 2 > rang + x )  //其实你可以把外边那个for改成 for ( i=x+1; i<= (rang+x)/2; i++ ) ，就可以省去这个if 语句块
           {
                 break;
           }
}

递归其实体现了一种divide-and-conquer （化整为零，逐个击破）的解决问题的思想， 所以在多数情况下，算法效率都是最优的之一。   

在这个问题上，最直觉的递归算法，时间复杂度为 O(N!)
你可以算算你的算法的时间复杂度， main 里面的那个while循环应该有N!次，而每次while循环调用的next_permutation的函数复杂度为 2N ，乘起来应该有  2N * N! 的时间复杂度。

引用:

Originally posted by psbeyond at 2005-10-28 22:34:
用递归效率应该是最低的了吧？

程序段可以进一步优化。算法见下：
// 1、从左至右遍历，找到最后一对升序数对的第一个数(它后面的数列为降序)
// 2、从这个数至右遍历，找到最后一个比它大的数
// 3、交换这两个数
// 4、从第一步得到的数以后的数列逆置
// 例：原数列d c h g f e b a
// 第一步：找到c ( dc ch hg gf fe eb ba中ch是最后一对左边数小于右边数的)
// 第二步：找到e ( 在chgfeba数列中，e是最后一个比c大的数)
// 第三步：交替c和e，成新数列dehgfcba
// 第四步：把c位置(交换c和e后变为e位置)以后的数列逆置成新数列deabcfgh
这种算法是比较好的，只是我的编程能力一般，实现起来可能不是很好。会有一些垃圾语句地里面。

楼上的算法倒是很新颖， 能够解释一下为什么这么做可以得到全排列么？ （就是理论上的解释，算法的原理）

我想到的递归算法是：

字符串是N， 我们假设去掉第N个字符，然后对剩下的N-1长度字符串进行全排列。 最后，再把第N个字符插入到所有可能的位置。

如：
输入字符串是 abcd ， 我们对abc 全排列， 对于每个abc全排列的结果，插入字符d。

例如，我们得到abc的一个排列组合是：b c  a ， 于是试图插入d
  b c  a
d  d d  d
得到 dbca, bdca, bcda, bcad .

递归下去，当字符串长度为1的时候，直接返回该字符串

比如给你abcdefgh八个字母，就从abcdefgh开始排，现在已经排到d c h g f e b a了，前面的就不用管了，就让你排d c h g f e b a下一个，按照人的思维，就是我写的算法，按照机器的思维，可能就是递归或其它算法了。_next_permutation就是已知d c h g f e b a，求deabcfgh的。abcdefgh一共有多少个全排列，就调用多少次_next_permutation就可以了。所以我说，时间复杂度是最优的。这八个字母排下来好像是130多秒，包括打印到屏幕的时间，如果不打印，应该能更快点。

算法的时间复杂度不是根据你运行多少时间来算的， 而是根据你的代码来理论分析的。


你的算法要调 N! 次_next_permutation ，而_next_permutation 的复杂度是2N，所以整个算法复杂度是 N! * 2N 级别的。

从这点来说，算法并不是最优的。 因为用递归可以达到 N! 级别。

[[i] Last edited by WinHack on 2005-10-31 at 00:00 [/i]]