js随机数生成与排序

时间：2023-03-09 23:55:50
js随机数生成与排序 
'use strict';

// 排序算法、

// 生成一个指定数量的不含重复数字的随机数组

function ranArr(n,callback) {

    var res = [];

    var tmp ;

    res = lack(res,n);

    ckRanArr(res,n,,function (res) {

        return callback(res);

    });

}

// 生成一个指定范围内(正整数 a到b)的随机数

function ranNum(a,b){

    var n = Math.abs(a - b );

    var base_n = a;

    if(a > b){ base_n = b; }

    var res = Math.floor(Math.random()*n) + base_n;

    return res;

}

// 返回去除重复项后的数组

function quchong(arr) {

    var arr2 = arr.slice();

    var arr2_len = arr2.length;

    var arr3 = [];

    for(var j = ;j < arr2_len;j++){

    // 重复项不进新数组 去重

    (function (item,ind) {

        var flag = false;

        for(var k = (ind + );k < arr2_len; k++){

            if(item == arr2[k]){

                flag = true;

            }

        }

        if(!flag){

            arr3.push(item);

        }

    }) (arr2[j],j);

    }

    return arr3;

}

// 补缺失的量并检查

function lack(arr,n) {

    // 去重后数量少了 补上

    var arr_len = arr.length;

    if(arr_len < n){

        var lack = n - arr_len;

        for(var j = ; j < lack;j++){

            arr.push( ranNum(,) );

        }

    }

    return arr;

}

// 递归检查函数  count:重试次数 重试次数限制与生成数量相关

function ckRanArr(arr,n,count,callback){    

    var limit;

    if(n < ){

        limit = *n;

    }

    if(n >= ){

        limit = n;

    }

    if(count <  limit){

        count++;

        var arr2 = quchong(arr);  // 去重

        if(arr2.length < n ){

            var arr3 = lack(arr2,n);  // 补量

            ckRanArr(arr3,n,count,callback);

        }

        else{

            return callback(arr2);

        }

    }

    else{

        return callback( quchong(arr) );

    }

}

ranArr(,function (res) {

    console.log(res);

});

// 上面的递归调用会发生每个函数都是一个栈，会生成一个不断堆叠的函数栈直到最后一个栈函数return后依次退出。

// 同步循环生成版

function ranArr2(n){

    var arr = [];

    arr = lack(arr,n);

    var limit;

    if(n < ){

        limit = *n;

    }

    else{

        limit = n;

    }

    cl:for(var i = ;i < limit;i++){ console.log(i);

        var arr2 = quchong(arr);  // 去重

        if(arr2.length < n){

            arr = lack(arr2,n); // 补量

        }

        else{

            break cl;

        }

    }

    return arr;

}

优化性能效率版

// 前两个版本生成指定数量不重复的随机数效率太低了,

// 举例生成1000个 每一次去重时都需要接近1000 x 1000次的比较

// 优化之后速度有了极大的提升

// 生成范围 0-30000  生成20000个不重复随机数

// ranArr2 平均需要23s(秒)左右

// ranArr3 平均需要300ms左右

//在数据范围和数据量接近 重复几率大的时候1位1位排重的方式具有很高的性能

//在数据范围和数据量差距很大 10万条 1亿    ran3平均需要5s左右 ran2需要23s左右

// 数据范围增加100倍 10万条 ran2 21s左右

function ranArr3(n) {

    var arr = [];

    var arr2 = [];

    if(n <= ){

        return arr2;

    }

    arr = lack(arr,n);

    arr2.push(arr[]);

    // console.log('第0个数:'+arr2);

    var arr_len = arr.length;

    for (var i = ; i < arr_len; i++) {

        // console.log('第'+i+'个数:'+arr[i]);

        arr2 = not_in_arr_item(arr[i],i,arr2 );

        // console.log('得到arr2为：['+arr2+']');

    }

    return arr2;

}

// 给定一个数组 和元素,返回一个不在数组中已有元素的元素

function not_in_arr_item(item,ind,arr2) {

    //console.log( '每次进入: '+ 'item:' + item + '  ind:' + ind + ' [' + arr2 + ']');

    var flag = false;

    cl:for (var j = ; j < ind; j++) {

        // console.log('j:'+j);

        if(item == arr2[j]){

            flag = true;

            break cl;

        }

    }

    // console.log(flag);

    if(flag){

        item = ranNum(,);

        //console.log('进入ran: '+item);

        return not_in_arr_item(item,ind,arr2);

    }

    if(!flag){

        arr2.push(item);

        return arr2;

    }

}

排序算法部分

//                  取5次的平均时间

// 比较  (个数)       冒泡          快速排序     插入排序

//       100          0.354ms      0.443ms       0.294ms

//       1000         2.94ms       2.351ms       1.89ms 1.84ms

//       10000        158.39ms     12.15ms       56.8ms 55.3ms

//       50000        5026ms       54ms          1286ms 1298ms

// 冒泡排序

function maopao(arr) {

    var arr1 = arr.slice();

    var len = arr1.length;

    for(var i = ;i < len;i++){

        for(var j = (i+);j<len;j++){

            if(arr1[i] > arr1[j]){

                var tmp = arr1[i];

                arr1[i] = arr1[j];

                arr1[j] = tmp;

            }

        }

    }

    return arr1;

}

// console.time('maopao');

// var maopao_arr = maopao(arr1);

// console.timeEnd('maopao');

// console.log(maopao_arr);

// 快排 快速排序

//1、找基准（一般是以中间项为基准）

//2、遍历数组，小于基准的放在left，大于基准的放在right

//3、递归

function kuaipai(arr) {

    if(arr.length<=){return arr;}

    var index = Math.floor(arr.length/);

    var base_num = arr.splice(base_num,)[];

    var l = [];

    var r = [];

    var len = arr.length;

    for(var i = ; i < len;i++){

        if(arr[i]<= base_num){

            l.push(arr[i]);

        }

        else{

            r.push(arr[i]);

        }

    }

    return kuaipai(l).concat( [base_num],kuaipai(r) );

}

// console.time('kuaipai');

// var kuaipai_arr = kuaipai(arr1);

// console.timeEnd('kuaipai');

// console.log(kuaipai_arr);

// 插入排序

// 类似于斗地主整理牌时窝们人类所使用的算法：不断把牌抽出来,插入到已有牌中应处的位置

// 将n个元素的数列分为已有序和无序两个部分

// 将该数列的第一元素视为有序数列，后面都视为无序数列

// 将无序数列中的元素插入到有序数列的对应位置，插入前通过比大小的方式找到其在有序数列中的对应位置。

// 找位置的时候有两种方式找,就近找可以减少比较次数

function insertSort(arr){

    var len = arr.length;

    for (var i = ; i < len; i++) {

        //不断和前一个数比

        if(arr[i] < arr[i-] ){

            var el = arr[i];

            var ind;

            //找插入位置

            look: for(var j = ;j<len;j++){

                if( el < arr[j]){

                    ind = j;

                    break look;

                }

            }

            // 从j开始到原插入元素部分全部后移一位

            for(var k = i;k>j;k--){

                arr[k] = arr[k-]

            }

            arr[ind] = el;

        }

    }

    return arr;

}

// console.log(arr1);

// console.time('insertSort');

// var insert_arr = insertSort(arr1);

// console.timeEnd('insertSort');

// console.log(insert_arr);

function insertSort2(arr) {

    var len = arr.length;

    for (var i = ; i < len; i++) {

        if(arr[i] < arr[i-] ){

            var el = arr[i];

            arr[i] = arr[i-];

            var j = i-;

            while( (j >= ) && (el < arr[j]) ){

                arr[j+] = arr[j];

                j--;

            }

            arr[j] = el;

        }

    }

    return arr;

}

// console.log(arr1);

console.time('insertSort2');

var insert_arr2 = insertSort(arr1);

console.timeEnd('insertSort2');

// console.log(insert_arr2);

paixu.js

'use strict';

// 排序算法、

var arr1 = ranArr2();

//                  取5次的平均时间

// 比较  (个数)       冒泡          快速排序     插入排序

//       100          0.354ms      0.443ms       0.294ms

//       1000         2.94ms       2.351ms       1.89ms 1.84ms

//       10000        158.39ms     12.15ms       56.8ms 55.3ms

//       50000        5026ms       54ms          1286ms 1298ms

// 冒泡排序

function maopao(arr) {

    var arr1 = arr.slice();

    var len = arr1.length;

    for(var i = ;i < len;i++){

        for(var j = (i+);j<len;j++){

            if(arr1[i] > arr1[j]){

                var tmp = arr1[i];

                arr1[i] = arr1[j];

                arr1[j] = tmp;

            }

        }

    }

    return arr1;

}

// console.time('maopao');

// var maopao_arr = maopao(arr1);

// console.timeEnd('maopao');

// console.log(maopao_arr);

// 快排 快速排序

//1、找基准（一般是以中间项为基准）

//2、遍历数组，小于基准的放在left，大于基准的放在right

//3、递归

function kuaipai(arr) {

    if(arr.length<=){return arr;}

    var index = Math.floor(arr.length/);

    var base_num = arr.splice(base_num,)[];

    var l = [];

    var r = [];

    var len = arr.length;

    for(var i = ; i < len;i++){

        if(arr[i]<= base_num){

            l.push(arr[i]);

        }

        else{

            r.push(arr[i]);

        }

    }

    return kuaipai(l).concat( [base_num],kuaipai(r) );

}

// console.time('kuaipai');

// var kuaipai_arr = kuaipai(arr1);

// console.timeEnd('kuaipai');

// console.log(kuaipai_arr);

// 插入排序

// 类似于斗地主整理牌时窝们人类所使用的算法：不断把牌抽出来,插入到已有牌中应处的位置

// 将n个元素的数列分为已有序和无序两个部分

// 将该数列的第一元素视为有序数列，后面都视为无序数列

// 将无序数列中的元素插入到有序数列的对应位置，插入前通过比大小的方式找到其在有序数列中的对应位置。

// 找位置的时候有两种方式找,就近找可以减少比较次数

function insertSort(arr){

    var len = arr.length;

    for (var i = ; i < len; i++) {

        //不断和前一个数比

        if(arr[i] < arr[i-] ){

            var el = arr[i];

            var ind;

            //找插入位置

            look: for(var j = ;j<len;j++){

                if( el < arr[j]){

                    ind = j;

                    break look;

                }

            }

            // 从j开始到原插入元素部分全部后移一位

            for(var k = i;k>j;k--){

                arr[k] = arr[k-]

            }

            arr[ind] = el;

        }

    }

    return arr;

}

// console.log(arr1);

// console.time('insertSort');

// var insert_arr = insertSort(arr1);

// console.timeEnd('insertSort');

// console.log(insert_arr);

function insertSort2(arr) {

    var len = arr.length;

    for (var i = ; i < len; i++) {

        if(arr[i] < arr[i-] ){

            var el = arr[i];

            arr[i] = arr[i-];

            var j = i-;

            while( (j >= ) && (el < arr[j]) ){

                arr[j+] = arr[j];

                j--;

            }

            arr[j] = el;

        }

    }

    return arr;

}

// console.log(arr1);

console.time('insertSort2');

var insert_arr2 = insertSort(arr1);

console.timeEnd('insertSort2');

// console.log(insert_arr2);

// 生成一个指定数量的不含重复数字的随机数组

// 同步递归回调版

function ranArr(n,callback) {

    var res = [];

    res = lack(res,n);

    ckRanArr(res,n,,function (res) {

        return callback(res);

    });

}

// 同步循环生成版

function ranArr2(n){

    var arr = [];

    arr = lack(arr,n);

    var limit;

    if(n < ){

        limit = *n;

    }

    else{

        limit = n;

    }

    cl:for(var i = ;i < limit;i++){ //console.log(i);

        var arr2 = quchong(arr);  // 去重

        if(arr2.length < n){

            arr = lack(arr2,n); // 补量

        }

        else{

            break cl;

        }

    }

    return arr;

} 

// 生成一个指定范围内(正整数 a到b)的随机数

function ranNum(a,b){

    var n = Math.abs(a - b );

    var base_n = a;

    if(a > b){ base_n = b; }

    var res = Math.floor(Math.random()*n) + base_n;

    return res;

}

// 返回去除重复项后的数组

function quchong(arr) {

    var arr2 = arr.slice();

    var arr2_len = arr2.length;

    var arr3 = [];

    for(var j = ;j < arr2_len;j++){

    // 重复项不进新数组 去重

    (function (item,ind) {

        var flag = false;

        for(var k = (ind + );k < arr2_len; k++){

            if(item == arr2[k]){

                flag = true;

            }

        }

        if(!flag){

            arr3.push(item);

        }

    }) (arr2[j],j);

    }

    return arr3;

}

// 补缺失的量并检查

function lack(arr,n) {

    // 去重后数量少了 补上

    var arr_len = arr.length;

    if(arr_len < n){

        var lack = n - arr_len;

        for(var j = ; j < lack;j++){

            arr.push( ranNum(,) );

        }

    }

    return arr;

}

// 递归检查函数  count:重试次数 重试次数限制与生成数量相关

function ckRanArr(arr,n,count,callback){    

    var limit;

    if(n < ){

        limit = *n;

    }

    if(n >= ){

        limit = n;

    }

    if(count <  limit){

        count++;

        var arr2 = quchong(arr);  // 去重

        if(arr2.length < n ){

            var arr3 = lack(arr2,n);  // 补量

            ckRanArr(arr3,n,count,callback);

        }

        else{

            return callback(arr2);

        }

    }

    else{

        return callback( quchong(arr) );

    }

}

// console.time('a');

// var tmp = ranArr2(1000);

// console.timeEnd('a');

// console.log( tmp );

// ranArr(10,function (res) {

//     console.log(res);

// });

相关文章