前端基础函数算法整理应用（sort+reduce+date+双重for循环）

基础函数算法

一、排序算法

1. 冒泡排序（Bubble Sort）
   • 原理：
     • 比较相邻的元素。如果第一个比第二个大（升序），就交换它们两个。
     • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
     • 针对所有的元素重复以上的步骤，除了最后一个。
     • 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
   • 代码示例：

function bubbleSort(arr) {var len = arr.length;for (var i = 0; i < len - 1; i++) {for (var j = 0; j < len - 1 - i; j++) {if (arr[j] > arr[j + 1]) {// 交换位置var temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}return arr;
}
var arr = [5, 4, 3, 2, 1];
console.log(bubbleSort(arr));

2. 选择排序（Selection Sort）
   • 原理：
     • 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
     • 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
     • 以此类推，直到所有元素均排序完毕。
   • 代码示例：

function selectionSort(arr) {var len = arr.length;for (var i = 0; i < len - 1; i++) {var minIndex = i;for (var j = i + 1; j < len; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}if (minIndex!== i) {var temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}return arr;
}
var arr = [5, 4, 3, 2, 1];
console.log(selectionSort(arr));

3. 插入排序（Insertion Sort）
   • 原理：
     • 从第二个元素开始（索引为1），将当前元素与前面已排序的元素进行比较。
     • 如果当前元素小于前面的元素，则将前面的元素后移一位，然后继续向前比较，直到找到合适的位置插入当前元素。
     • 重复这个过程，直到所有元素都插入到正确的位置。
   • 代码示例：

function insertionSort(arr) {for (var i = 1; i < arr.length; i++) {var current = arr[i];var j = i - 1;while (j >= 0 && arr[j] > current) {arr[j + 1] = arr[j];j--;}arr[j + 1] = current;}return arr;
}
var arr = [5, 4, 3, 2, 1];
console.log(insertionSort(arr));

二、搜索算法

1. 线性搜索（Linear Search）
   • 原理：
     • 从数组的第一个元素开始，逐个检查每个元素，直到找到目标元素或者遍历完整个数组。
   • 代码示例：

function linearSearch(arr, target) {for (var i = 0; i < arr.length; i++) {if (arr[i] === target) {return i;}}return -1;
}
var arr = [1, 3, 5, 7, 9];
console.log(linearSearch(arr, 5));

2. 二分搜索（Binary Search，要求数组是有序的）
   • 原理：
     • 首先，比较目标元素和数组中间元素的大小。
     • 如果目标元素等于中间元素，则搜索结束。
     • 如果目标元素小于中间元素，则在数组的左半部分继续搜索。
     • 如果目标元素大于中间元素，则在数组的右半部分继续搜索。
     • 重复这个过程，直到找到目标元素或者确定目标元素不存在。
   • 代码示例：

function binarySearch(arr, target) {var low = 0;var high = arr.length - 1;while (low <= high) {var mid = Math.floor((low + high)/2);if (arr[mid] === target) {return mid;} else if (arr[mid] < target) {low = mid + 1;} else {high = mid - 1;}}return -1;
}
var arr = [1, 3, 5, 7, 9];
console.log(binarySearch(arr, 5));

三、字符串操作算法

1. 字符串反转（String Reversal）
   • 原理：
     • 可以将字符串转换为数组，然后使用数组的反转方法，最后再将数组转换回字符串。或者通过逐个字符交换的方式来反转字符串。
   • 代码示例（使用数组方法）：

function reverseString(str) {return str.split("").reverse().join("");
}
console.log(reverseString("hello"));

• 代码示例（逐个交换）：

function reverseString2(str) {var newStr = "";for (var i = str.length - 1; i >= 0; i--) {newStr += str[i];}return newStr;
}
console.log(reverseString2("hello"));

2. 字符串匹配（简单的模式匹配，例如判断一个字符串是否包含另一个字符串）
   • 原理：
     • 可以使用JavaScript原生的indexOf方法来检查一个字符串是否包含另一个字符串。如果indexOf返回的值大于等于0，则表示包含。
   • 代码示例：

function containsString(str, subStr) {return str.indexOf(subStr) >= 0;
}
console.log(containsString("hello world", "world"));

reduce 函数算法

1. 默认排序（字符串Unicode码点排序）
   • 原理：
     • 当sort方法没有传入比较函数时，它会将数组元素转换为字符串，并按照Unicode码点顺序对这些字符串进行排序。对于数字数组，这种排序方式可能不符合预期。例如，[10, 2, 30]排序后可能得到[10, 2, 30]，因为在Unicode码点顺序下，"10"会排在"2"之前。
   • 代码示例：

const arr = ["apple", "banana", "cherry"];
arr.sort();
console.log(arr); 

• 这里arr数组中的字符串元素会按照字典序（即字符的Unicode码点顺序）进行排序，结果为["apple", "banana", "cherry"]。

2. 数字排序
   • 原理：
     • 为了正确地对数字数组进行排序，需要传入一个比较函数。比较函数接受两个参数a和b，如果a小于b，则返回一个小于0的值；如果a等于b，则返回0；如果a大于b，则返回一个大于0的值。对于升序排序，通常返回a - b。
   • 代码示例：

const numbers = [10, 2, 30];
numbers.sort((a, b) => a - b);
console.log(numbers); 

• 在这个例子中，比较函数(a, b) => a - b会计算a和b的差值。当a小于b时，a - b小于0，数组会将a排在b之前，最终得到升序排列的数组[2, 10, 30]。

3. 降序排序
   • 原理：
     • 与升序排序类似，只是比较函数返回b - a，这样当b大于a时，返回值大于0，b就会排在a之前。
   • 代码示例：

const numbers = [10, 2, 30];
numbers.sort((a, b) => b - a);
console.log(numbers); 

• 这里的比较函数(a, b) => b - a使得数组按照降序排列，结果为[30, 10, 2]。

4. 对象数组排序
   • 原理：
     • 对于对象数组，可以根据对象的某个属性值进行排序。比较函数会根据对象属性的值来比较两个对象。
   • 代码示例：

const people = [{ name: "Alice", age: 25 },{ name: "Bob", age: 30 },{ name: "Charlie", age: 20 }
];
// 根据年龄升序排序
people.sort((a, b) => a.age - b.age);
console.log(people);

• 在这个对象数组中，比较函数(a, b) => a.age - b.age根据对象的age属性进行比较。当a.age小于b.age时，a会排在b之前，最终得到按照年龄升序排列的对象数组[{"name": "Charlie", "age": 20}, {"name": "Alice", "age": 25}, {"name": "Bob", "age": 30}]。

5. 复杂条件排序（多个属性排序）
   • 原理：
     • 有时候需要根据多个属性对对象数组进行排序。可以在比较函数中先根据一个属性进行比较，如果该属性值相等，再根据另一个属性进行比较。
   • 代码示例：

const students = [{ name: "Alice", grade: "A", age: 20 },{ name: "Bob", grade: "B", age: 22 },{ name: "Charlie", grade: "A", age: 21 }
];
// 先根据成绩升序排序，如果成绩相同，再根据年龄升序排序
students.sort((a, b) => {if (a.grade === b.grade) {return a.age - b.age;}if (a.grade < b.grade) {return -1;}return 1;
});
console.log(students);

• 这个比较函数首先比较对象的grade属性。如果grade属性相同，就比较age属性。最终得到按照成绩升序排列，成绩相同则按照年龄升序排列的对象数组[{"name": "Bob", "grade": "B", "age": 22}, {"name": "Alice", "grade": "A", "age": 20}, {"name": "Charlie", "grade": "A", "age": 21}]。

sort 函数算法

1. 默认排序（字符串Unicode码点排序）
   • 原理：
     • 当sort方法没有传入比较函数时，它会将数组元素转换为字符串，并按照Unicode码点顺序对这些字符串进行排序。对于数字数组，这种排序方式可能不符合预期。例如，[10, 2, 30]排序后可能得到[10, 2, 30]，因为在Unicode码点顺序下，"10"会排在"2"之前。
   • 代码示例：

const arr = ["apple", "banana", "cherry"];
arr.sort();
console.log(arr); 

• 这里arr数组中的字符串元素会按照字典序（即字符的Unicode码点顺序）进行排序，结果为["apple", "banana", "cherry"]。

2. 数字排序
   • 原理：
     • 为了正确地对数字数组进行排序，需要传入一个比较函数。比较函数接受两个参数a和b，如果a小于b，则返回一个小于0的值；如果a等于b，则返回0；如果a大于b，则返回一个大于0的值。对于升序排序，通常返回a - b。
   • 代码示例：

const numbers = [10, 2, 30];
numbers.sort((a, b) => a - b);
console.log(numbers); 

• 在这个例子中，比较函数(a, b) => a - b会计算a和b的差值。当a小于b时，a - b小于0，数组会将a排在b之前，最终得到升序排列的数组[2, 10, 30]。

3. 降序排序
   • 原理：
     • 与升序排序类似，只是比较函数返回b - a，这样当b大于a时，返回值大于0，b就会排在a之前。
   • 代码示例：

const numbers = [10, 2, 30];
numbers.sort((a, b) => b - a);
console.log(numbers); 

• 这里的比较函数(a, b) => b - a使得数组按照降序排列，结果为[30, 10, 2]。

4. 对象数组排序
   • 原理：
     • 对于对象数组，可以根据对象的某个属性值进行排序。比较函数会根据对象属性的值来比较两个对象。
   • 代码示例：

const people = [{ name: "Alice", age: 25 },{ name: "Bob", age: 30 },{ name: "Charlie", age: 20 }
];
// 根据年龄升序排序
people.sort((a, b) => a.age - b.age);
console.log(people);

• 在这个对象数组中，比较函数(a, b) => a.age - b.age根据对象的age属性进行比较。当a.age小于b.age时，a会排在b之前，最终得到按照年龄升序排列的对象数组[{"name": "Charlie", "age": 20}, {"name": "Alice", "age": 25}, {"name": "Bob", "age": 30}]。

5. 复杂条件排序（多个属性排序）
   • 原理：
     • 有时候需要根据多个属性对对象数组进行排序。可以在比较函数中先根据一个属性进行比较，如果该属性值相等，再根据另一个属性进行比较。
   • 代码示例：

const students = [{ name: "Alice", grade: "A", age: 20 },{ name: "Bob", grade: "B", age: 22 },{ name: "Charlie", grade: "A", age: 21 }
];
// 先根据成绩升序排序，如果成绩相同，再根据年龄升序排序
students.sort((a, b) => {if (a.grade === b.grade) {return a.age - b.age;}if (a.grade < b.grade) {return -1;}return 1;
});
console.log(students);

• 这个比较函数首先比较对象的grade属性。如果grade属性相同，就比较age属性。最终得到按照成绩升序排列，成绩相同则按照年龄升序排列的对象数组[{"name": "Bob", "grade": "B", "age": 22}, {"name": "Alice", "grade": "A", "age": 20}, {"name": "Charlie", "grade": "A", "age": 21}]。

时间排序

在JavaScript中，如果你有一个包含时间信息（如日期）的数组，想要对其进行排序，可以使用Array.prototype.sort方法，并结合Date对象来实现。以下是几种常见的基于时间的排序场景及实现方法：

1. 对日期字符串数组进行排序

假设数组中的元素是日期字符串，格式为YYYY - MM - DD。

// 日期字符串数组
const dateStrings = ["2023-10-05", "2023-09-15", "2023-11-20"];// 排序函数
dateStrings.sort((a, b) => {return new Date(a) - new Date(b);
});console.log(dateStrings);

在上述代码中：

• sort方法接受一个比较函数，该函数接收两个参数a和b。
• new Date(a)和new Date(b)将日期字符串转换为Date对象。
• 通过new Date(a) - new Date(b)计算两个日期对象的时间差，如果a的日期早于b，则返回一个负数，sort方法会将a排在b之前；如果时间差为0，则保持原顺序；如果a的日期晚于b，则返回一个正数，sort方法会将a排在b之后。

2. 对包含日期对象的数组进行排序

假设数组中直接存储的是Date对象。

// 日期对象数组
const dates = [new Date("2023-10-05"),new Date("2023-09-15"),new Date("2023-11-20")
];// 排序函数
dates.sort((a, b) => {return a - b;
});console.log(dates.map(date => date.toISOString()));

这里，Date对象之间可以直接进行减法运算，其结果是两个日期之间相差的毫秒数。同样，比较函数根据这个差值来确定元素的顺序。

3. 对包含时间戳的数组进行排序

如果数组中的元素是时间戳（从1970年1月1日00:00:00 UTC开始到指定时间的毫秒数）。

// 时间戳数组
const timestamps = [1696502400000, 1694774400000, 1699286400000];// 排序函数
timestamps.sort((a, b) => {return a - b;
});console.log(timestamps.map(timestamp => new Date(timestamp).toISOString()));

时间戳本身就是数字，直接相减就可以得到正确的比较结果，sort方法会根据这个结果对数组进行排序。

4. 对包含日期时间信息的对象数组进行排序

假设数组中的对象包含日期时间信息，例如：

const events = [{ name: 'Event1', date: '2023-10-05' },{ name: 'Event2', date: '2023-09-15' },{ name: 'Event3', date: '2023-11-20' }
];events.sort((a, b) => {return new Date(a.date) - new Date(b.date);
});console.log(events);

在这个例子中，比较函数从对象中提取日期字符串，将其转换为Date对象后进行比较，从而实现对对象数组的排序。