sort:insertion vs selection
HTML
<button>开始测试</button>
<div id="log"></div>
JavaScript
//noprotection
$('button').on('click', () => {
$(this).attr('disabled', true).text('测试进行中……');
var times = 10000;
$('#log').empty().append('<p>' + (Date.now()) + ': 开始进行插入排序测试,测试次数 ' + times + ' 次</p>');
var t = times;
var start = Date.now();
while (t--) {
selectionSort(getRandArray(times));
}
t = +new Date - start;
$('#log').append('<p>' + (Date.now()) + ': 插入排序测试完成,花费总时间为 ' + t + ' ms,平均每次时间为 ' + (t / times) + 'ms</p>');
$('#log').append('<p>' + (Date.now()) + ': 开始进行选择排序测试,测试次数 ' + times + ' 次</p>');
t = times;
start = Date.now();
while (t--) {
insertionSort(getRandArray(times));
}
t = +new Date - start;
$('#log').append('<p>' + (Date.now()) + ': 选择排序测试完成,花费总时间为 ' + t + ' ms,平均每次时间为 ' + (t / times) + 'ms</p>');
$(this).attr('disabled', false).text('重新测试');
});
// 获取指定长度的元素大小在 0 到 10000 之间的随机数组
function getRandArray(len) {
return (new Array(len)).fill(0).map((i) => Math.random() * 10000 | 0);
}
// 插入排序
// 类似扑克牌
function insertionSort(arr) {
arr = arr.slice(0);
var i = 0;
var j = 0;
var temp = 0;
var len = arr.length;
for (i = 1; i < len; i++) {
// 倒着往前数
j = i - 1;
// 当前要移动的数字
temp = arr[i];
// 前面是已经排序的
// 所以要找到比当前数大的最小值
// 在这个过程中,所有比当前数大的都得往后挪动一位
// j 最后的值就是 j 应该存放的位置
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
// 最后将当前数入位
arr[j + 1] = temp;
}
return arr;
};
// 选择排序
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];
...