使用random_shuffle()算法随机化序列元素

假设你需要指定范围内的随机数,传统的方法是使用ANSI C的函数random(),然后格式化结果以便结果是落在指定的范围内。但是,使用这个方法至少有两个缺点。首先,做格式化时,结果常常是扭曲的,所以得不到正确的随机数(如某些数的出现频率要高于其它数) 。其次,random()只支持整型数;不能用它来产生随机字符,浮点数,字符串或数据库中的记录。

对于以上的两个问题,C++中提供了更好的解决方法,那就是random_shuffle()算法。不要着急,下面我就会告诉你如何用这种算法来产生不同类型的随机数。

产生指定范围内的随机元素集的最佳方法是创建一个顺序序列(也就是向量或者内置数组),在这个顺序序列中含有指定范围的所有值。例如,如何你需要产生100个0-99之间的数,那么就创建一个向量并用100个按升序排列的数填充向量:

#include <vector>
using std::vector;
int main()
{
 vector<int> vi;
 for (int i = 0; i < 10; i++)
  vi.push_back(i);
/*现在向量包含了 100 个 0-99 之间的整数并且按升序排列*/
}

填充完向量之后,用random_shuffle()算法打乱元素排列顺序。random_shuffle()定义在标准的头文件<algorithm.h>中。因为所有的STL算法都是在名字空间std::中声明的,所以你要注意正确地声明数据类型。random_shuffle()有两个参数,第一个参数是指向序列首元素的迭代器,第二个参数则指向序列最后一个元素的下一个位置。下列代码段用random_shuffle()算法打乱了先前填充到向量中的元素:

#include <algorithm>
using std::random_shuffle;
random_shuffle(vi.begin(), vi.end()); /* 打乱元素 */

如果你想检查被打乱的元素,可以用如下方法看一下他们被打乱后存储的次序:

for (int i = 0; i < 100; i++)
 cout<<vi[i]; /* 显示被打乱顺序的元素 */

random_shuffle()是个完全通用的算法-适用于内建的数据类型和用户自定义类型。下面的例子创建了一个有7个字符串对象的向量,它包含一周的天数并使用random_shuffle()打乱他们的排列顺序:

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
 vector<string> vs;
 vs.push_back(string ("Sunday"));
 vs.push_back (string ("Monday"));
 ...
 vs.push_back (string ("Saturday"));
 random_shuffle(vs.begin(), vs.end()); /* 打乱顺序 */
 for (int i = 0; i << 7; i++)
  cout<<vs[i]; /* 显示打乱顺序后的元素 */
}

如何使用random_shuffle()处理内置数组

在使用容器代替内置数组时,你不要有什么负担。所有STL算法不仅适用于容器,也适用于序列。因此,你也能将random_shuffle()算法应用于内置数组。只是要注意random_shuffle()的第二个参数要指向数组上界的下一个元素位置:

char carr[4] = {''a'', ''b'', ''c'', ''d''};
/*carr+4 指向数组上界的下一个元素位置*/
random_shuffle(carr, carr+4); 
for (int i = 0; i < 4; i++)
 cout<<carr[i]; /* 显示被打乱顺序的元素 */

时间: 2024-07-30 14:59:38

使用random_shuffle()算法随机化序列元素的相关文章

C++数据结构与算法专题

快速排序算法的C++实现 详解qsort函数的用法 C++求二个数的最大公约数与最小公倍数实例 小览CallStack(调用栈)(三)-用调试器脚本查看调用栈信息 小览call stack(调用栈) (二)--调用约定 小览call stack(调用栈) (一) C++/CLI中栈对象的设计问题 POJ 1694 C++ (排序) 高效实现Josephus算法 利用堆排序实现学生成绩管理 C++双向循环链表的操作与实现 基于Crtpto++的RSA签名算法 自定义函数使用map排序 C++数据结

(算法导论习题解problem2.4)寻找一个序列中逆序对的数量

一个序列的逆序对是这样的两个元素, 对于序列A而言, i>j且A[i]<A[j], 于是A[i]和A[j]就形成一个逆序对. 研究一个序列中逆序对的数量是有实际意义的, 对于插入排序而言, 它排序的时间与待排序序列的逆序对数量成正比. 下面给出求出一个序列中逆序对数量的算法,类似于归并排序中使用的分治算法:一个序列的逆序对数量为它的左半部分逆序对的数量,加上右半部分逆序对的数量, 最后在合并的时候左半部分元素大于右半部分元素的数量.这几乎和归并算法的过程一模一样,只是在归并的时候加入了计数的操

《大数据算法》一3.5 寻找频繁元素的随机算法

3.5 寻找频繁元素的随机算法 本节重新研究3.3节中讨论的问题,提出寻找频繁元素的随机算法.Misra-Gries算法通过扫描数据一次提供足够的信息,然后通过第二次扫描数据解决频繁元素发现问题,即扫描数据第一次过程中Misra-Gries算法计算一个数据结构,对于j∈[n]该数据结构可以获得其频率fj的足够准确估计fj.本小节提出另外两个频率估计的随机算法. 3.5.1 略图法 1.略图和线性略图 在处理数据流σ的过程中,令表示Misra-Gries算法中所需的数据结构.这种数据结构的一个缺点

排序算法

排序|算法 算法是程序设计的精髓,程序设计的实质就是构造解决问题的算法,将其解释为计算机语言. 在这里您可以了解到: 算法定义 伪代码的使用 算法的复杂性 算法设计策略 常用算法 这里所有的算法都以一种类似Pascal语言的伪代码描述,请参阅伪代码的使用. 新增内容 关于数论的算法--数论基本知识(May 6, 2001)动态规划重新整理 (January 15, 2001)图的深度优先遍历 (January 21, 2001) 图的广度优先遍历 (January 21, 2001)图的拓扑排序

JS实现随机化快速排序的实例代码

这篇文章介绍了JS实现随机化快速排序的实例代码,有需要的朋友可以参考一下   算法的平均时间复杂度为O(nlogn).但是当输入是已经排序的数组或几乎排好序的输入,时间复杂度却为O(n^2).为解决这一问题并保证平均时间复 杂度为O(nlogn)的方法是引入预处理步骤,它惟一的目的是改变元素的顺序使之随机排序.这种预处理步骤可在O(n)时间内运行.能够起到同样作用的 另一种简单方法是在算法中引入一个随机元素,这可以通过随机地选择拆分元素的主元来实现.随机选择主元的结果放宽了关于输入元素的所有排列

JS实现随机化快速排序

算法的平均时间复杂度为O(nlogn).但是当输入是已经排序的数组或几乎排好序的输入,时间复杂度却为O(n^2).为解决这一问题并保证平均时间复杂度为O(nlogn)的方法是引入预处理步骤,它惟一的目的是改变元素的顺序使之随机排序.这种预处理步骤可在O(n)时间内运行.能够起到同样作用的另一种简单方法是在算法中引入一个随机元素,这可以通过随机地选择拆分元素的主元来实现.随机选择主元的结果放宽了关于输入元素的所有排列的可能性相同的步骤.引入这一步来修正原先的快速排序,可得到下面所示的随机化快速排序

常用的算法思想总结

对于计算机科学而言,算法是一个非常重要的概念.它是程序设计的灵魂,是将实际问题同解决该问题的计算机程序建立起联系的桥梁.接下来,我们来看看一些常用的算法思想. (一)穷举法思想 穷举法,又称为强力法.它是一种最为直接,实现最为简单,同时又最为耗时的一种解决实际问题的算法思想. 基本思想:在可能的解空间中穷举出每一种可能的解,并对每一个可能解进行判断,从中得到问题的答案. 使用穷举法思想解决实际问题,最关键的步骤是划定问题的解空间,并在该解空间中一一枚举每一个可能的解.这里有两点需要注意,一是解空

【排序算法】插入排序

本篇博客的主要内容是插入排序.常用的插入排序方法有直接插入排序.折半插入排序.表插入排序和希尔排序.这里介绍两个,直接插入排序和希尔排序. 在介绍排序算法时,我将从基本思想.实例讲解.代码理解三个方面整理. [直接插入排序] 1.基本思想 直接插入排序(Straight Insertion Sorting)的基本思想是一次将每个记录插入到一个已排好序的有序表中去,从而得到一个新的.记录数增加1的有序表. 2.具体做法 我们把第一个序列元素看成是已经排好序的一个记录,后面的元素依次与已排好序的序列

我的Java开发学习之旅------&amp;gt;Java经典排序算法之希尔排序

一.希尔排序(Shell Sort) 希尔排序(Shell Sort)是一种插入排序算法,因D.L.Shell于1959年提出而得名. Shell排序又称作缩小增量排序. 二.希尔排序的基本思想 希尔排序的中心思想就是:将数据进行分组,然后对每一组数据进行排序,在每一组数据都有序之后 ,就可以对所有的分组利用插入排序进行最后一次排序.这样可以显著减少交换的次数,以达到加快排序速度的目的.       希尔排序的中心思想:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组.所有距