问题描述：设R={r1,r2,…,rn}是要进行排列的个元素。其中元素r1,r2,…,rn 可能相同。试设计一个算法，列出R的所有不同排列。 ★算法设计：给定n及待排列的n个元素。计算出这n个元素的所有不同排列。 ★数据输入：由文件input.txt提供输入数据。文件的第1行是元素个数n,1≤n≤500。接下来的1行是待排列的n个元素。 ★结果输出：将计算出的n个元素的所有不同排列输出到文件output.txt。文件最后1行中的数是排列总数。

大学学习

线性时间选择 给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素 template Type RandomizedSelect(Type a[],int p,int r,int k) { if (p==r) return a[p]; int i=RandomizedPartition(a,p,r), j=i-p+1; if (k<=j) return RandomizedSelect(a,p,i,k); else return RandomizedSelect(a,i+1,r,k-j); } 在最坏情况下，算法randomizedSelect需要O(n2)计算时间但可以证明，算法randomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素。