http://poj.org/problem?id=1833
按照字典的顺序（a-z) (1-9），可以得出任意两个数字串的大小。比如“123”， 最小的是“123”（从小到大），最大的是“321”(从大到小)。这样对于“123”的所有排列，可以得到按照字典序排序的有序集合 : 1 2 3 ， 1 3 2 ， 2 1 3 ， 2 3 1 ， 3 1 2 ， 3 2 1。
如果有n个数的排列，
1) 从最右边开始找，找到第一个 i ，使得arr[i] > arr[i-1];
2) 从 i 到 n 这个范围找到最小的比 arr[i-1] 大的数字，交换这个数和 arr[i-1];
3) 从 arr[i] 到 arr[n] 排序 qsort(arr, i, n);
1 #include "stdafx.h"
2 #include <stdio.h>
3 #include <string.h>
4 #define N_MAX 1025
5 int n, k;
6 int a[N_MAX];
7
8 void printf_arr()
9 {
10 for (int i = 1; i <= n; i++) {
11 printf("%d ", a[i]);
12 }
13 printf("\n");
14 }
15
16 void qsort(int *a, int begin, int end)
17 {
18 if (begin >= end) return;
19 int l = begin, r = end, k = a[l];
20 while (l != r) {
21 while (l < r && k <= a[r]) r--;
22 while (l < r && k >= a[l]) l++;
23 if (l < r) {
24 int tmp = a[l];
25 a[l] = a[r];
26 a[r] = tmp;
27 }
28 }
29 a[begin] = a[l];
30 a[l] = k;
31 qsort(a, begin, l - 1);
32 qsort(a, l + 1, end);
33 }
34
35 int main(int argc, char* argv[])
36 {
37 //setbuf(stdout, NULL);
38 //freopen("sample_input.txt", "r", stdin);
39
40 int T = 0;
41 scanf("%d", &T);
42
43 while (T--) {
44 scanf("%d %d", &n, &k);
45
46 for (int j = 1; j <= n; j++) {
47 scanf("%d", &a[j]);
48 }
49
50 while (k--) {
51 int i = n;
52 // step 1 : find a[i] > a[i - 1]
53 for (; i > 0; i--) {
54 if (a[i] > a[i - 1])
55 break;
56 }
57 // the biggest
58 if (i == 1) {
59 for (int i = 1; i <= n; i++) {
60 a[i] = i;
61 }
62 continue;
63 }
64
65 // step 2 : find the min in [i, n]
66 int min = n;
67 int l = i - 1;
68 int r = i;
69 for (int j = i; j <= n; j++) {
70 if (a[j] > a[l] && a[j] < min) {
71 min = a[j];
72 r = j;
73 }
74 }
75
76 // step 2 : swap(min, a[i - 1])
77 int tmp = a[l];
78 a[l] = a[r];
79 a[r] = tmp;
80
81 // step 3 : qsort [i, n]
82 qsort(a, i, n);
83 }
84
85 printf_arr();
86 }
87 return 0;
88 }