место действия
Босс попросил Сяо Мина отсортировать более 20 000 единиц данных компании, но, поскольку операция сортировки происходит часто, если операция занимает много времени, это серьезно ухудшит работу пользователя.Услышав эту плохую новость, Сяо Мин начал код.
1. Алгоритм сортировки без всякого смысла нарушения Сяо Мин немного подумал в соответствии со своими потребностями и написал следующий алгоритм:
/**
* max排序
* @param {*} arr
* 耗时：760ms
*/
function maxSort(arr) {
let result = [...arr];
for(let i=0,len=result.length; i< len; i++) {
let minV = Math.min(...result.slice(i))
let pos = result.indexOf(minV,i)
result.splice(pos, 1)
result.unshift(minV)
}
return result.reverse()
}
Уверенный в себе Сяо Мин опьянен своим алгоритмом, готовый проверить работоспособность,
/*
* @Author: Mr Jiang.Xu
* @Date: 2019-06-11 10:25:23
* @Last Modified by: Mr Jiang.Xu
* @Last Modified time: 2019-06-13 21:03:59
* @desc 测试函数执行的时间
*/
const testArr = require('./testArr');
module.exports = async function getFnRunTime(fn) {
let len = testArr.length;
let startTime = Date.now(), endTime;
let result = await fn(testArr);
endTime = Date.now();
console.log(result);
console.log(`total time:${endTime-startTime}ms`,
'test array\'length:' + len,
result.length
);
}
После запуска тестовой функции прошло 760 мс.Сяомин посчитал, что это неплохо.После включения в проект первая операция прошла нормально.После нескольких последовательных операций страница явно зависла. . . (В это время ищите теневую область в сердце Сяо Мина)
2. Пузырьковая сортировка
Сяо Мин не смирился и после поиска соответствующей информации в Интернете написал следующий код пузырьковой сортировки:
/**
* 置换函数
* @param {源数组} arr
* @param {原数组的A项} indexA
* @param {原数组的B项} indexB
*/
function swap(arr, indexA, indexB) {
[arr[indexA], arr[indexB]] = [arr[indexB], arr[indexA]];
}
/**
* 原始冒泡排序
* @param {数组} arr
* 耗时：377ms
*/
function bubbleSort1(arr) {
for (let i = arr.length - 1; i > 0; i--) {
for (let j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
return arr;
}
После теста это заняло 377 мс, что идеально. Сяомин включил его в проект для тестирования, и частая сортировка все равно будет немного зависать. Вы можете оптимизировать это? После долгих раздумий Сяо Мин усовершенствовал сортировку пузырьком:
/**
* 利用索引优化后的冒泡排序
* @param {数组} arr
* 耗时：350ms
*/
function bubbleSort2(arr) {
let i = arr.length - 1;
while (i > 0) {
let pos = 0;
for (let j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
pos = j;
swap(arr, j, j + 1);
}
}
i = pos;
}
return arr;
}
Повышение производительности сортировки на основе кэшированной позиции индекса экономит 20 мс времени, но выигрыш невелик. Сяо Мин начал бороться с собой, продолжил поиски в Википедии и наконец нашел способ:
/**
* 在每趟排序中进行正向和反向两遍冒泡 ,
* 一次可以得到两个最终值（最大和最小）,
* 从而使外排序趟数大概减少了一半
* @param {*} arr
* 耗时：312ms
*/
function bubbleSort3(arr) {
let start = 0;
let end = arr.length - 1;
while (start < end) {
let endPos = 0;
let startPos = 0;
for (let i = start; i < end; i++) {
if (arr[i] > arr[i + 1]) {
endPos = i;
swap(arr, i, i + 1);
}
}
end = endPos;
for (let i = end; i > start; i--) {
if (arr[i - 1] > arr[i]) {
startPos = i;
swap(arr, i - 1, i);
}
}
start = startPos;
}
return arr;
}
Выполняя прямое и обратное барботирование дважды в каждой сортировке, Сяо Мин сократил время на 38 мс, неплохо~
/**
* 插入排序 -- 基础版
* @param {*} arr
* 耗时：897ms
*/
function insertionSort(arr) {
for (let i = 1, len = arr.length; i < len; i++) {
const temp = arr[i];
let preIndex = i - 1;
while (arr[preIndex] > temp) {
arr[preIndex + 1] = arr[preIndex];
preIndex -= 1;
}
arr[preIndex + 1] = temp;
}
return arr;
}
897 мс, Сяо Мин оставил неумелые слезы.
/**
* 改造二分查找,查找小于value且离value最近的值的索引
* @param {*} arr
* @param {*} maxIndex
* @param {*} value
*/
function binarySearch1(arr, maxIndex, value) {
let min = 0;
let max = maxIndex;
while (min <= max) {
const m = Math.floor((min + max) / 2);
if (arr[m] <= value) {
min = m + 1;
} else {
max = m - 1;
}
}
return min;
}
/**
* 使用二分法来优化插入排序
* @param {*} arr
* 耗时：86ms
*/
function insertionSort1(arr) {
for (let i = 1, len = arr.length; i < len; i++) {
const temp = arr[i];
const insertIndex = binarySearch1(arr, i - 1, arr[i]);
for (let preIndex = i - 1; preIndex >= insertIndex; preIndex--) {
arr[preIndex + 1] = arr[preIndex];
}
arr[insertIndex] = temp;
}
return arr;
}
Отлично, всего 86 мс! Сяо Мин взволнованно встал и похлопал по столу, полностью игнорируя пристальный взгляд аудитории.
4. Сортировка по холму
Неужели нет места для совершенствования? Исследования показали, что есть лучшее решение:
/**
* 希尔排序
* 核心：通过动态定义的 gap 来排序，先排序距离较远的元素，再逐渐递进
* @param {*} arr
* 耗时：15ms
*/
function shellSort(arr) {
const len = arr.length;
let gap = Math.floor(len / 2);
while (gap > 0) {
// gap距离
for (let i = gap; i < len; i++) {
const temp = arr[i];
let preIndex = i - gap;
while (arr[preIndex] > temp) {
arr[preIndex + gap] = arr[preIndex];
preIndex -= gap;
}
arr[preIndex + gap] = temp;
}
gap = Math.floor(gap / 2);
}
return arr;
}
Для поклонения требуется 15 мс. ####5. Сортировка слиянием
/**
* 归并排序
* @param {*} arr
* 耗时 30ms
*/
function concatSort(arr) {
const len = arr.length;
if (len < 2) { return arr; }
const mid = Math.floor(len / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);
return concat(concatSort(left), concatSort(right));
}
function concat(left, right) {
const result = [];
while (left.length > 0 && right.length > 0) {
result.push(left[0] <= right[0] ? left.shift() : right.shift());
}
return result.concat(left, right);
}
Это занимает 30 мс, и я хочу быть отличным. Есть ли более быстрый способ? Ответ - да, но это потребует математических знаний монахов. Брось это, дитя. . .
В будущем будет запущено больше отличных алгоритмов, так что следите за обновлениями~ И, наконец, добро пожаловать в группу передовых технологий и вместе обсудите прелести переднего плана.