js测试算法的工具方法

1.生成随机数组

/**
 * 生成有n个元素的随机数组，每个元素的随机范围为[rangeL, rangeR)
 * length 数组长度
 * rangeL 最小值
 * rangeR 最大值
 */
var generateRandamArray = (length, rangeL, rangeR) => {
    console.assert(rangeL < rangeR);  // rangeR要求大于rangeL
    let arr = [];
    for (let i = 0; i < length; i++) {
        arr[i] = rangeL + Math.floor(Math.random() * (rangeR - rangeL + 1));
    }
    return arr;
}

2.生成接近排好序的数组

/**
 * 生成有length长度的元素的较为有序的数组
 * length 数组长度
 * swapTimes 打乱的次数
 */
var genNearOrderArr = (length, swapTimes) => {
    let arr = [];
    for (let i = 0; i < length; i++) {
        arr.push(i);
    }
    for (let i = 0; i < swapTimes; i++) {
        const x = Math.floor(Math.random() * length);
        const y = Math.floor(Math.random() * length);
        console.log(arr);
        arr.swop(x, y);
        console.log(arr);
    }
    return arr;
}

3.测试排序结果

/**
 * 测试方法
 * 计算算法效率
 * 检查排序结果是否正确
 * selector 可选入参，当数组内容是对象的时候，用于获取比较字段，例如function(item) { return item.id;};
 */
var testSort = (arr, sorter, selector) => {
    console.log(sorter.getName());
    console.time();
    let sortedArr = sorter(arr, selector);
    console.timeEnd();
    console.log(SortTestHelper.isSorted(arr, selector));
    return sortedArr;
}

4.判断是否已排序

/**
 * 判断是否已排序
 * selector 可选入参
 */
var isSorted = (arr, selector) => {
    selector = selector || JSON.parse;
    for (let i = 0; i < arr.length - 1; i++) {
        if (selector(arr[i]) > selector(arr[i + 1])) {
            return false;
        }
    }
    return true;
}

5.深拷贝,用于数组备份

// 深拷贝
var clone = (arr) => {
    return JSON.parse(JSON.stringify(arr));
}

6.增加原型方法

// 交换数组的两个位置的元素
Array.prototype.swap = function (i, j) {
    let item = this[i];
    this[i] = this[j];
    this[j] = item;
}
// 获取 function 名
Function.prototype.getName = function () {
    return this.name || this.toString().match(/function\s*([^(]*)\(/)[1]
}

7.将 function 统一放在 SortTestHelper 对象中

image.png

8.使用范例

// 选择排序
function SectionSort(arr, selector) {
    selector = selector||JSON.parse;
    for (let i=0; i<arr.length; i++) {
        // 寻找[i, n)区间里的最小值
        let minIndex = i;
        for (let j=i; j<arr.length; j++) {
            if (selector(arr[j]) < selector(arr[minIndex])) {
                minIndex = j;
            }
        }
        arr.swap(i, minIndex);
    }
    return arr;
}
let n = 20;
let arr11 = SortTestHelper.generateRandamArray(n, 0, n);
console.log(arr11);
// let arrB = SortTestHelper.clone(arr);
let arr12 = SortTestHelper.testSort(arr11, SectionSort)
console.log(arr12);
console.log('\n');


let arr21 = [1.1,5.2,6.5,3.2,4.3];
console.log(arr21);
let arr22 = SortTestHelper.testSort(arr21, SectionSort)
console.log(arr22);
console.log('\n');

let arr31 = ['D','F','A','E','C','B'];
console.log(arr31);
let arr32 = SortTestHelper.testSort(arr31, SectionSort, JSON.stringify)
console.log(arr32);
console.log('\n');

let arr41 = [
    {age: 15, name: 'TOM'},
    {age: 12, name: 'LILEI'},
    {age: 17, name: 'DAVIE'},
    {age: 14, name: 'ROSE'},
    {age: 15, name: 'LIO'},
    {age: 13, name: 'LEON'}
];
console.log(arr41);
let arr42 = SortTestHelper.testSort(arr41, SectionSort, function(item) { return item.age;})
console.log(arr42);
console.log('\n');

// SortTestHelper.testSort(arr, InsertionSort1)
arr11 = arr12 = arr21 = arr22 = arr31 = arr32 = arr41 = arr42 = null;

输出结果