随机数外部排序

本文介绍了随机数外部排序的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我需要编写一个生成N个随机数并将其按降序写入二进制文件的程序.应该在不使用任何使用主内存的排序算法的情况下完成此操作.到目前为止，这是我所做的:

I need to write a program that generates N random numbers and write them to binary file in descending order. It should be done without using any of sorting algorithms that use main memory. This is what I've done so far:

#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; }

因此，我生成了随机数并将其写入二进制文件，但是我不知道如何对其进行排序.

So, I've generated random numbers and wrote them to binary file but I don't know how to sort it.

推荐答案

您可以在线性时间内按排序顺序生成数字.描述如何执行此操作的论文是:通过Bentley& amp; amp; amp; amp;生成随机数排序列表.萨克斯

You can generate your numbers in sorted order in linear time. The paper describing how to do this is: Generating Sorted Lists of Random Numbers by Bentley & Saxe

pdfs.semanticscholar/2dbc/4e3f10b88832fcd5fb88d34b8fb0b

pdfs.semanticscholar/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; } }