我需要编写一个生成 N 个随机数的程序,并将它们按降序写入二进制文件。它应该在不使用任何使用主内存的排序算法的情况下完成。这是我到目前为止所做的:
#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>
using namespace std;
int main () {
srand(time(0));
rand();
int N;
do{
cout << "Unesite N: ";
cin >> N;
} while(N<=0);
ofstream br("broj.dat", ios::binary | ios::trunc);
for(int i = 0; i<N; i++){
int a = rand();
br.write((char *)&a, sizeof(a));
}
br.close();
return 0;
}
所以,我生成了随机数并将它们写入二进制文件,但我不知道如何对其进行排序。
最佳答案
您可以在线性时间内按排序顺序生成数字。描述如何执行此操作的论文是:Bentley & Saxe 生成的随机数排序列表
https://pdfs.semanticscholar.org/2dbc/4e3f10b88832fcd5fb88d34b8fb0b0102000.pdf
/**
* Generate an sorted list of random numbers sorted from 1 to 0, given the size
* of the list being requested.
*
* This is an implementation of an algorithm developed by Bentley and Sax, and
* published in in ACM Transactions on Mathematical Software (v6, iss3, 1980) on
* 'Generating Sorted Lists of Random Numbers'.
*/
public class SortedRandomDoubleGenerator {
private long valsFound;
private double curMax;
private final long numVals;
/**
* Instantiate a generator of sorted random doubles.
*
* @param numVals the size of the list of sorted random doubles to be
* generated
*/
public SortedRandomDoubleGenerator(long numVals) {
curMax = 1.0;
valsFound = 0;
this.numVals = numVals;
}
/**
* @return the next random number, in descending order.
*/
public double getNext() {
curMax = curMax
* Math.pow(Math.E, Math.log(RandomNumbers.nextDouble())
/ (numVals - valsFound));
valsFound++;
return curMax;
}
}
关于c++ - 随机数外部排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46058304/