学步园

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


class Solution {
public:
	void NextPermutation(int num[], int n);
};


void Solution::NextPermutation(int num[], int n)
{
<span style="white-space:pre">	</span>int change = -1;
<span style="white-space:pre">	</span>int tmp;
<span style="white-space:pre">	</span>int i;

<span style="white-space:pre">	</span>i = n-1;
<span style="white-space:pre">	</span>//找到第一个不是升序的点，从后边往前遍历
<span style="white-space:pre">	</span>while(i!=0 && num[i-1]>=num[i])
<span style="white-space:pre">		</span>i--;
<span style="white-space:pre">	</span>if( i == 0 )
<span style="white-space:pre">	</span>{
<span style="white-space:pre">		</span>//直接反转顺序
<span style="white-space:pre">		</span>for(i=0; i<(n-1)/2; i++)
<span style="white-space:pre">		</span>{
<span style="white-space:pre">			</span>tmp = num[i];
<span style="white-space:pre">			</span>num[i] = num[n-1-i];
<span style="white-space:pre">			</span>num[n-1-i] = tmp;
<span style="white-space:pre">		</span>}
<span style="white-space:pre">		</span>return;
<span style="white-space:pre">	</span>}

<span style="white-space:pre">	</span>change = i-1;
<span style="white-space:pre">	</span>for(i=n-1; i>change; i--)
<span style="white-space:pre">	</span>{
<span style="white-space:pre">		</span>if(num[i]>num[change])
<span style="white-space:pre">		</span>{
<span style="white-space:pre">			</span>tmp = num[i];
<span style="white-space:pre">			</span>num[i] = num[change];
<span style="white-space:pre">			</span>num[change] = tmp;
<span style="white-space:pre">			</span>break;
<span style="white-space:pre">		</span>}
<span style="white-space:pre">	</span>}
<span style="white-space:pre">	</span>//反转顺序
<span style="white-space:pre">	</span>for(i=0; i<(n-1-change)/2; i++)
<span style="white-space:pre">	</span>{
<span style="white-space:pre">		</span>tmp = num[change+1+i];
<span style="white-space:pre">		</span>num[change+1+i] = num[n-1-i];
<span style="white-space:pre">		</span>num[n-1-i] = tmp;
<span style="white-space:pre">	</span>}
}

int main()
{
	Solution s;
	int array[4] = {1,2,2,4};
	vector<int> array2;
	array2.push_back(1);
	array2.push_back(2);
	array2.push_back(2);
	array2.push_back(4);
	
	for(int j=0; j<24-1; j++)
	{
		s.NextPermutation(array, 4);
		for(int i=0; i<4; i++)
			cout<<array[i]<<" ";
		cout<<"\t";
		//标准stl输出
		next_permutation(array2.begin(), array2.end());
		for(vector<int>::iterator it = array2.begin(); it!=array2.end(); it++)
			cout<<*it<<" ";
		cout<<endl;
	}
}

算法复杂度是O(n)，空间复杂度是O(1)。