随机化算法中的排序问题
现给定一个数组A[1...n],要构造这个数组的一个随机排列，一个常用的方法是为数组的每个元素A[i]赋一个随机的优先级P[i],然后依据优先级对数组进行排序。伪代码如下：
n=length[A]
for(i=1;i<=n;i++)
P[i]=random(1,n^3);
sort A,using p as sort keys

其中random(1,n^3)生成1到n^3之间的随机数，是为了让P中优先级尽可能是唯一的。
问： sort A,using p as sort keys 这一步该怎么实现才能使时间复杂度尽可能小？即数组A依据优先级序列P排序，怎样排序使用时间最少？

[解决办法]
楼主觉的插入排序怎么样！！！
[解决办法]
洗牌算法，参考

C/C++ code

#include <stdio.h>#include <stdlib.h>#include <time.h>int d[6];int i,n,a,b,t;int c,j;void main() {    srand(time(NULL));    printf("shuffle 0..n-1 demo\n");    for (n=1;n<=5;n++) {/* 测试1～5个元素 */        printf("_____n=%d_____\n",n);        j=1;        for (c=1;c<=n;c++) j=j*c;/* j为n! */        j*=n*2;        for (c=1;c<=j;c++) {/* 测试n*2*n!次 */            for (i=0;i<n;i++) d[i]=i;/* 填写0～n-1 */            for (i=n;i>0;i--) {/* 打乱0～n-1 */                a=i-1;b=rand()%i;                if (a!=b) {t=d[a];d[a]=d[b];d[b]=t;}            }            printf("%04d:",c);            for (i=0;i<n;i++) printf("%d",d[i]);            printf("\n");        }    }    printf("shuffle 1..n demo\n");    for (n=1;n<=5;n++) {/* 测试1～5个元素 */        printf("_____n=%d_____\n",n);        j=1;        for (c=1;c<=n;c++) j=j*c;/* j为n! */        j*=n*2;        for (c=1;c<=j;c++) {/* 测试n*2*n!次 */            for (i=1;i<=n;i++) d[i]=i;/* 填写1～n */            for (i=n;i>1;i--) {/* 打乱1～n */                a=i;b=rand()%i+1;                if (a!=b) {t=d[a];d[a]=d[b];d[b]=t;}            }            printf("%04d:",c);            for (i=1;i<=n;i++) printf("%d",d[i]);            printf("\n");        }    }}