本文作者:文蔺
本文地址:http://www.wemlion.com/2016/algo-selection-sort/
本文由 @文蔺 创作,转载请保留此声明。
所有权利保留,请勿用于商业目的。

所谓“选择排序”,基本思路就是不断从数组中选择出最小的数。

还是以扑克牌为例。假设有 N 张扑克牌,记扑克牌集合为 cards,则我们的基本操作如下:

首先,从手中拿出左侧第 0 张牌 cardA;

第二步,将 cardA 向右依次与剩下的 (N - 1) 张牌进行对比,找出最小的那张牌所在的位置 minIndex;

第三步,对比完成后,若 minIndex 不等于 1,则说明 cardA 不是最小的,将 cards[minIndex] 与 cardA 进行位置交换。

第四步,从第二张牌开始,重复前面的步骤……

……

最后得到的数组即是排序好的。

实现如下:

// 选择排序
function selectionSort(cards) {
cards = cards.slice(0);
var len = cards.length;
var i = 0;
var j = 0;
var minIndex = 0;
var temp = 0;

for (i = 0; i < len - 1; i++) {
// 将当前的数字与后面子序列中最小数进行换位
// 这样每次拿到前面的都是最小的数字
minIndex = i;

// 寻找子序列中最小数的索引
// 每一轮得比较 n - i 次
for (j = i + 1; j < len; j++) {
if (cards[j] < cards[minIndex]) {
minIndex = j;
}
}

// 如果当前数比后面子序列最小元素大
// 则进行换位处理
if (minIndex !== i) {
temp = cards[i];
cards[i] = cards[minIndex];
cards[minIndex] = temp;
}
}
return cards;
}

来粗略看下时间复杂度的问题。

实际上,这个算法,不存在最好的情况和最坏的情况。因为每次通过比较寻找最小数时,必须将所有剩余数字对比个遍。

第一次需要与 (N - 1) 个数进行对比;第二次需要与 (N - 2 个数) 对比,直到最后。总的计算次数为 (N - 1) + (N - 2) + ... + 1 + 0 = N * (N - 1) / 2。不难看出,时间复杂度是 O(n^n)

在 JavaScript 中,与插入排序比较,感觉选择排序比较好的一点是,没有频繁的元素位置调换,每次只会进行一次交换这一点上,性能应该会好很多(尤其是数组较大的情况下)。可以参考 测试Demo

每次使用的数组都长度为 1000、元素为在 (0, 10000) 区间中的整数的随机数组,每种方法分别测试 10000次,最终取计算时间平均值。结果插入排序每次时间大约在 0.9 毫秒左右,而选择排序在 0.6 毫秒左右,但注意,这里的时间包含生成随机数组的时间。

也可以用 node 来测试(排序函数代码略):

var times = 10000;

var t = times;
console.time('selectionSort');
while (t--) {
selectionSort(getRandArray(1000));
}
console.timeEnd('selectionSort');


t = times;
console.time('insertionSort');
while (t--) {
insertionSort(getRandArray(1000));
}
console.timeEnd('insertionSort');

// 获取指定长度的元素大小在 0 到 10000 之间的随机数组
function getRandArray(len) {
return (new Array(len)).fill(0).map((i) => Math.random() * 10000 | 0);
}

本文作者:文蔺
本文地址:http://www.wemlion.com/2016/algo-selection-sort/
转载请注明来源