【每日一题】- 2019-08-23 - 如何对 1 千万个整数进行快速排序

[azl397985856]

输入：一个最多包含n个正整数的文件，每个数都小于n，其中n=10^7。如果在输入文件中有任何正数重复出现就是致命错误。没有其他数据与该正数相关联。

输出：按升序排列的输入整数的列表。

约束：最多有（大约）1MB的内存空间可用，有充足的磁盘存储空间可用。运行时间最多几分钟，运行时间为10秒就不需要进一步优化。

[xiongcaihu]

/**
 * Array存储一个数字耗费一个字节，一个字节又对应8个bit，每个bit可以表示一个数，0表示没有此数，1表示有此数
 * 比如：1，2，3，10，在Array中的存储为
 * [7,2]
 * 7的二进制为 00000111  后面三个1分别表示1，2，3
 * 2的二进制位 00000010  
 * 
 * 这样array的每位可以用来表示8个数，那么一千万个数的话，就只需要1250000byte表示，
 * 1250000/1024/1024 约等于 1M
 *
 * @param {*} inputFile
 */
function sortBigArrays(inputFile) {
    var array = new Array(1).fill(0);
    var number = '';

    var readerStream = fs.createReadStream(inputFile, {
        highWaterMark: 1
    });

    readerStream.on('data', function (chunk) {
        if (chunk == ',') {
            putNumberIntoMap(array, +number);
            number = '';
        } else {
            number += chunk;
        }
    });

    readerStream.on('end', function () {
        putNumberIntoMap(array, +number);
        var wtStream = fs.createWriteStream('output.txt');
        for (var i = 0, len = array.length; i < len; i++) {
            // console.log('output ', i, ' into file');
            if (array[i] && array[i] != 0) {
                // 输出到文件
                var base = 8 * i;
                var t = array[i].toString(2).split('').reverse();
                for (var j = 0; j < t.length; j++) {
                    if (t[j] == '1') {
                        wtStream.write((base + j + 1) + (i == len - 1 ? '' : ','));
                    }
                }
            }
        }
        wtStream.end();
    });

    function putNumberIntoMap(array, number) {
        var posIndex = number % 8;
        var arrayIndex = parseInt(number / 8);
        posIndex = posIndex == 0 ? (arrayIndex--, 7) : posIndex - 1;

        var sum = array[arrayIndex] == null ? array[arrayIndex] = 0 : array[arrayIndex];
        sum = sum.toString(2).split('');

        while (sum.length != 8) {
            sum.unshift('0');
        }
        sum[7 - posIndex] = '1';
        array[arrayIndex] = parseInt(sum.join(''), 2);
    }
}

[azl397985856]

/**
 * Array存储一个数字耗费一个字节，一个字节又对应8个bit，每个bit可以表示一个数，0表示没有此数，1表示有此数
 * 比如：1，2，3，10，在Array中的存储为
 * [7,2]
 * 7的二进制为 00000111  后面三个1分别表示1，2，3
 * 2的二进制位 00000010  
 * 
 * 这样array的每位可以用来表示8个数，那么一千万个数的话，就只需要1250000byte表示，
 * 1250000/1024/1024 约等于 1M
 *
 * @param {*} inputFile
 */
function sortBigArrays(inputFile) {
    var array = new Array(1).fill(0);
    var number = '';

    var readerStream = fs.createReadStream(inputFile, {
        highWaterMark: 1
    });

    readerStream.on('data', function (chunk) {
        if (chunk == ',') {
            putNumberIntoMap(array, +number);
            number = '';
        } else {
            number += chunk;
        }
    });

    readerStream.on('end', function () {
        putNumberIntoMap(array, +number);
        var wtStream = fs.createWriteStream('output.txt');
        for (var i = 0, len = array.length; i < len; i++) {
            // console.log('output ', i, ' into file');
            if (array[i] && array[i] != 0) {
                // 输出到文件
                var base = 8 * i;
                var t = array[i].toString(2).split('').reverse();
                for (var j = 0; j < t.length; j++) {
                    if (t[j] == '1') {
                        wtStream.write((base + j + 1) + (i == len - 1 ? '' : ','));
                    }
                }
            }
        }
        wtStream.end();
    });

    function putNumberIntoMap(array, number) {
        var posIndex = number % 8;
        var arrayIndex = parseInt(number / 8);
        posIndex = posIndex == 0 ? (arrayIndex--, 7) : posIndex - 1;

        var sum = array[arrayIndex] == null ? array[arrayIndex] = 0 : array[arrayIndex];
        sum = sum.toString(2).split('');

        while (sum.length != 8) {
            sum.unshift('0');
        }
        sum[7 - posIndex] = '1';
        array[arrayIndex] = parseInt(sum.join(''), 2);
    }
}

小骑士， 有没有兴趣领这道题？

[EdgeAsh]

我來，之前看過這道題。但是不會做

[azl397985856]

我來，之前看過這道題。但是不會做

done

[raymondmars]

这是编程珠玑里面的题，思路就是将输入的数据映射到数组的index，最后输出数组中有值的index，就是排好序的数据。分配一个10^7大小的bit位数组，大约为1M，将输入数据作为index，在对应数组值上填写一个bit 1，遍历数组，输出bit为1的数组的 index。排序完成。

[azl397985856]

这是编程珠玑里面的题，思路就是将输入的数据映射到数组的index，最后输出数组中有值的index，就是排好序的数据。分配一个10^7大小的bit位数组，大约为1M，将输入数据作为index，在对应数组值上填写一个bit 1，遍历数组，输出bit为1的数组的 index。排序完成。

我的label 有著明是来自 编程珠玑 ，只不过是英文

[Edwardgudanyang]

这是华为最喜欢考的题。。。。计数排序

[azl397985856]

我來，之前看過這道題。但是不會做

时间很长了，没有忘记吧？

[EdgeAsh]

没忘，我补了点基础知识。争取这个月完成