有序序列的随机化_给定一挚有序序列,用随机化二挘挕挗的方法挕挗某元素x。 提示:随机化二挘挕挗方法

目录

 

一、引子

（1）问题

（2）问题抽象：

二、一种随机化的方法（原理如下图演示）

（1）说明：

（2）特点：

三、使用C++生成随机序列（该序列为自然数序列，且序列内不含重复元素）

---

 

一、引子

（1）问题

1. 将一副排好的扑克进行洗牌。
2. 由序列3,8,2,5,9,4重新随机排列后得到另一个序列 

（2）问题抽象：

1. 将一个有序序列随机化
2. 将一个序列A关联到一个有序计数序列B，使用随机化后的计数序列B’去重排序列A

二、一种随机化的方法（原理如下图演示）

（1）说明：

1. 在Excel表中对选中区域排序时，同一行相当于绑定在一起

（2）特点：

1. 可以对指定序列重排
2. 可以很容易地生成没有重复元素的随机序列
3. 随机序列中的随机数只用于排序，而不参加结果的计算
4. 对应算法性能分析：时间复杂度取决于排序算法的时间复杂度。是比较高效的。

三、使用C++生成随机序列（该序列为自然数序列，且序列内不含重复元素）

#include<vector>
#include<random>
struct Pair
{
	unsigned int_num;//对应计数序列
	unsigned rand_num;//对应辅助序列
};
bool isSmall_randnum(const Pair& s1, const Pair& s2)
{
	return s1.rand_num < s2.rand_num;
}
int get_randseqlist(vector<unsigned>& randseqlist,int num)
{
	/*
	函数功能：生成由0到num-1的num个整数构成的一个随机序列。随机序列通过randseqlist传出
	*/
	
	randseqlist.clear();
	Pair pair;
	vector<Pair> pairs;
    
    //生成随机数
	static default_random_engine e;
	static uniform_int_distribution<unsigned> u(0, num);
	
	for (unsigned i = 0; i < num; i++)
	{
		pair.int_num = i;
		pair.rand_num = u(e);
		pairs.push_back(pair);
	}
	sort(pairs.begin(), pairs.end(), isSmall_randnum);//以rand_num为“关键字”排序
	for (size_t i = 0; i < num; i++)
	{
		randseqlist.push_back(pairs[i].int_num);
	}
	return 0;
}