线性搜索
顺序搜索或线性搜索是最简单的搜索算法，它从列表或数组的开头开始逐个比较元素，直到找到目标值或搜索完整个列表。
function linearSearch(array, target) {
for (let i = 0; i < array.length; i++) {
if (array[i] === target) {
return i; // 返回目标值在数组中的索引
}
}
return -1; // 目标值不存在于数组中
}
// 示例用法
const arr = [5, 2, 4, 7, 1, 9, 3];
const target = 7;
const result = linearSearch(arr, target);
if (result !== -1) {
console.log("目标值 " + target + " 的索引为 " + result);
} else {
console.log("目标值 " + target + " 不存在于数组中");
}
二分搜索
二分搜索是一种高效的搜索算法，适用于已排序的数组。它通过将目标值与数组的中间元素进行比较，然后根据比较结果在数组的前半部分或后半部分继续搜索，直到找到目标值或搜索范围缩小为空。
function binarySearch(array, target) {
let left = 0;
let right = array.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (array[mid] === target) {
return mid; // 返回目标值在数组中的索引
} else if (array[mid] < target) {
left = mid + 1; // 目标值在右半部分
} else {
right = mid - 1; // 目标值在左半部分
}
}
return -1; // 目标值不存在于数组中
}
// 示例用法
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const target = 6;
const result = binarySearch(arr, target);
if (result !== -1) {
console.log("目标值 " + target + " 的索引为 " + result);
} else {
console.log("目标值 " + target + " 不存在于数组中");
}
冒泡排序
冒泡排序是一种简单的排序算法，它通过重复地交换相邻的元素，将较大（或较小）的元素逐渐移动到数组的一端，直到整个数组排序完成。
function bubbleSort(array) {
const length = array.length;
for (let i = 0; i < length - 1; i++) {
for (let j = 0; j < length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
// 交换相邻的两个元素
const temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
return array;
}
// 示例用法
const arr = [5, 2, 4, 7, 1, 9, 3];
const sortedArr = bubbleSort(arr);
console.log("排序后的数组：", sortedArr);
选择排序
选择排序也是一种简单的排序算法，它通过每次从未排序的部分选择最小（或最大）的元素，并将其放置在已排序部分的末尾，逐渐完成整个数组的排序。
function selectionSort(array) {
const length = array.length;
for (let i = 0; i < length - 1; i++) {
let minIndex = i;
// 在未排序部分中找到最小的元素索引
for (let j = i + 1; j < length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
// 将最小的元素与当前位置交换
if (minIndex !== i) {
const temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
}
return array;
}
// 示例用法
const arr = [5, 2, 4, 7, 1, 9, 3];
const sortedArr = selectionSort(arr);
console.log("排序后的数组：", sortedArr);
插入排序
插入排序是一种简单且高效的排序算法，它通过构建有序序列，对未排序的元素逐个插入到有序序列的适当位置，从而完成整个数组的排序。
function insertionSort(array) {
const length = array.length;
for (let i = 1; i < length; i++) {
const key = array[i];
let j = i - 1;
// 将大于 key 的元素向右移动
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
// 将 key 插入到正确位置
array[j + 1] = key;
}
return array;
}
// 示例用法
const arr = [5, 2, 4, 7, 1, 9, 3];
const sortedArr = insertionSort(arr);
console.log("排序后的数组：", sortedArr);
快速排序
快速排序是一种常用且高效的排序算法，它基于分治的思想，通过选择一个基准元素将数组划分为较小和较大的两个子数组，然后对子数组进行递归排序，最终实现整个数组的排序。
function quickSort(array) {
if (array.length <= 1) {
return array;
}
const pivot = array[Math.floor(array.length / 2)];
const less = [];
const equal = [];
const greater = [];
for (let element of array) {
if (element < pivot) {
less.push(element);
} else if (element > pivot) {
greater.push(element);
} else {
equal.push(element);
}
}
return [...quickSort(less), ...equal, ...quickSort(greater)];
}
// 示例用法
const arr = [5, 2, 4, 7, 1, 9, 3];
const sortedArr = quickSort(arr);
console.log("排序后的数组：", sortedArr);
归并排序
归并排序是一种高效的排序算法，它采用分治策略，将数组递归地划分为较小的子数组，然后将子数组合并为一个有序的数组，从而完成整个数组的排序。
function mergeSort(array) {
if (array.length <= 1) {
return array;
}
const middle = Math.floor(array.length / 2);
const left = array.slice(0, middle);
const right = array.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
const merged = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] <= right[rightIndex]) {
merged.push(left[leftIndex]);
leftIndex++;
} else {
merged.push(right[rightIndex]);
rightIndex++;
}
}
// 将剩余的元素添加到 merged 数组中
while (leftIndex < left.length) {
merged.push(left[leftIndex]);
leftIndex++;
}
while (rightIndex < right.length) {
merged.push(right[rightIndex]);
rightIndex++;
}
return merged;
}
// 示例用法
const arr = [5, 2, 4, 7, 1, 9, 3];
const sortedArr = mergeSort(arr);
console.log("排序后的数组：", sortedArr);
堆排序
堆排序是一种基于二叉堆的排序算法，它利用堆的性质来实现排序。首先将待排序的元素构建成一个最大堆（或最小堆），然后反复从堆中取出最大（或最小）元素，将其放置在已排序部分的末尾，最终完成排序。
function heapSort(array) {
buildMaxHeap(array);
for (let i = array.length - 1; i > 0; i--) {
swap(array, 0, i);
heapify(array, 0, i);
}
return array;
}
function buildMaxHeap(array) {
const length = array.length;
const startIndex = Math.floor(length / 2) - 1;
for (let i = startIndex; i >= 0; i--) {
heapify(array, i, length);
}
}
function heapify(array, index, heapSize) {
const left = 2 * index + 1;
const right = 2 * index + 2;
let largest = index;
if (left < heapSize && array[left] > array[largest]) {
largest = left;
}
if (right < heapSize && array[right] > array[largest]) {
largest = right;
}
if (largest !== index) {
swap(array, index, largest);
heapify(array, largest, heapSize);
}
}
function swap(array, i, j) {
const temp = array[i];
array[i] = array[j];
array[j] = temp;
}
// 示例用法
const arr = [5, 2, 4, 7, 1, 9, 3];
const sortedArr = heapSort(arr);
console.log("排序后的数组：", sortedArr);
评论区