JavaScript选择排序

[lfb]

选择排序

原理：首先从原始数组中找到最小的值，并把该值放在数组的最前面，然后再从剩下的值中寻找最小的值，放在之前最小值的后面，直到排序完毕。

function selectionSort(arr) {

    // 检测传入的 arr 是否为数组，如果不是数组，直接返回该本身
    if (Object.prototype.toString.call(arr) !== '[object Array]') {
        return arr;
    }

    var len = arr.length;
    
    // 如果长度为1或者为0，直接返回该数组
    if (len <= 1) {
        return arr;
    }

    for (var i = 0; i < len - 1; i++) {

        // 寻找[i, len-1)区间的最小值
        // minIndex始终保存着最小值的位置的索引，随着i的自增，遍历的数组长度越来越短，直到完成排序。
        var minIndex = i;
        for (var j = i + 1; j < len; j++) {

            if (arr[j] < arr[i]) {
                minIndex = j;
            }
        }

        var swap = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = swap;
    }

    return arr;
}

性能测试

/**
 * 生成随机数
 * @param lower 开始的数值
 * @param upper 结尾的数值
 * @returns 生成[lower, upper] 之间的随机数
 */
function getRandom(lower, upper) {
    return Math.floor(Math.random() * (upper - lower)) + lower;

}

/**
 * 获取随机数组
 * @param len 生成数组长度
 * @returns 随机生成长度为len的数组
 */
function getArr(len) {
    var arr = [];
    for (var i = 0; i < len; i++) {
        arr.push(getRandom(1, len));
    }

    return arr;
}

/**
 *  测试最好情况生成的有序数组
 * @param len 生成数组长度
 * @returns 生成有序长度为len的数组
 */
function getBestArr(len) {
    var bestArr = []
    for (var i = 1; i <= len; i++) {
        bestArr.push(i);
    }

    return bestArr;
}

/**
 * 测试最坏情况所有的数字随机（极少情况下重复）
 * @param len 生成数组长度
 * @returns 随机无序不重复长度为len的数组
 */
function getBadArr(len) {
    var badArr = []
    for (var i = len; i > 0; i--) {
        badArr.push(i + getRandom(1, 100));
    }

    return badArr;
}

/**
 * 测试算法sortName运行opCount个排序操作所需要的时间
 * @param sortName 算法名字
 * @param opCount 操作的个数
 * @returns 耗时间
 */
function testSortCountTime(sortName, opCount) {
    // 记录排序前当前时间
    var nowTime = new Date().getTime();
    sortName(opCount);
    // 记录排序完时间
    var doneTime = new Date().getTime();

    return "耗时：" + ((doneTime - nowTime) / 1000.0) + "s";
}

const TEXT_NUM = 20000;
console.log("测试的个数为：" + TEXT_NUM);

// 平均时间复杂度测试（随机）
console.log("平均时间复杂度" + testSortCountTime(selectionSort, getArr(TEXT_NUM)));

// 测试最好的时间复杂度测试情况
console.log("最好的时间复杂度" + testSortCountTime(selectionSort, getBestArr(TEXT_NUM)));


// 测试最坏的时间复杂度测试情况
console.log("最坏的时间复杂度" + testSortCountTime(selectionSort, getBadArr(TEXT_NUM)));

/**
 ➜  JSFunction git:(master) ✗ node selectionSort.js
 测试的个数为：10000
 平均时间复杂度耗时：0.143s
 最好的时间复杂度耗时：0.049s
 最坏的时间复杂度耗时：0.049s
 ➜  JSFunction git:(master) ✗ node selectionSort.js
 测试的个数为：20000
 平均时间复杂度耗时：0.571s
 最好的时间复杂度耗时：0.174s
 最坏的时间复杂度耗时：0.175s
 ➜  JSFunction git:(master) ✗ node selectionSort.js
 测试的个数为：30000
 平均时间复杂度耗时：1.25s
 最好的时间复杂度耗时：0.395s
 最坏的时间复杂度耗时：0.396s
 ➜  JSFunction git:(master) ✗ node selectionSort.js
 测试的个数为：40000
 平均时间复杂度耗时：2.229s
 最好的时间复杂度耗时：0.693s
 最坏的时间复杂度耗时：0.689s
 ➜  JSFunction git:(master) ✗ node selectionSort.js
 测试的个数为：50000
 平均时间复杂度耗时：3.54s
 最好的时间复杂度耗时：1.197s
 最坏的时间复杂度耗时：1.192s
 */

选择排序总结

• 时间复杂度： 平均时间复杂度O(nn) 、最好情况O(nn)、最差情况O(n*n)
• 空间复杂度： O(1)
• 稳定性：不稳定