Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3
→ 1,3,2
3,2,1
→ 1,2,3
1,1,5
→ 1,5,1
题解：
从后往前遍历，设置一个pre，aft，指针
int comp (
const void*a,
const void
*b )
{
return
*( int
*) a -
* (int
*) b;
}
int get_next(int
*array, int len)
{
assert(array!= NULL
&&len >=
0);
int
* pre
= array
+ len
-2; //指向数组倒数第2个数
int
* aft
= pre
+
1; //指向数组最后一个数
int index
= len
-
1; //置换的第一个数的下标
当index
等于0时表示这个数是最大数，因为没有找到前一个比后一个小的数。
while((pre
-array) >=
0&& (aft -array)
> 0&& (pre
<aft) )
{
if(*pre
>=
*aft )
// 略过前一个数比后一个数大的
{
pre--;
aft--;
}
else //找到前一个比后一个小的数
{
int
* p
= pre; //找到最后还要回退比较找到pre
与aft之后的数是否有比它大的
比如1 2 3 4 6 8 7 3 2 1
当前pre指向6aft
指向8；
int
*q = aft
+1;
int flag
=0;
while(*p!=
'\0')
{
if(*p<
*q )
{
flag=
1;
break;
}
p++;
q++;
}
if(flag
==1)
{
int tmp
=*q;
*q
= *pre;
*pre
= tmp;
}
else
{
int tmp
=*aft;
*aft
= *pre;
*pre
= tmp;
}
qsort(aft,len- aft,
sizeof(int),comp);
break;
}
index--;
}
if(index
==0)
{
qsort(array,len,
sizeof(int), comp);
}
return index;
}