本文将给读者介绍JS中常见的算法,包括排序、查找等。算法是程序设计的基础,对于程序员来说,学好算法是非常重要的。相信通过学习本文,读者可以对算法有更加深入的理解。
冒泡排序算法采用交换方式,将待排序数组中相邻的两个数进行比较,较大的数后移一位,较小的数前移一位。经过一次遍历,最大的数就被交换到了最后。不断重复这个过程,直到所有数都排好序。
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;
}
快速排序算法采用分治法,将待排序数组分成两个子数组,将小于某个值的元素放到左边,将大于某个值的元素放到右边。然后对左右两个子数组递归执行同样的操作,最终形成有序数组。
function quickSort(arr) {
if(arr.length <= 1) { // 元素个数小于等于1,返回整个数组
return arr;
}
var pivotIndex = Math.floor(arr.length / 2); // 取中间元素作为基准值
var pivot = arr.splice(pivotIndex, 1)[0]; // 将该元素从数组中移除,并取出该元素
var left = [];
var right = [];
for(var i = 0; i < arr.length; i++) {
if(arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right)); // 递归左右两个子数组,最终合并成有序数组
}
二分查找算法是针对有序列表的一种查找方式。原理是将待查找元素与列表中中间位置的元素进行比较,若相等,则返回该位置;若小于中间元素,就继续在左边查找;若大于中间元素,则继续在右边查找。重复此过程,直到查找到该元素,或者列表已遍历完毕。
function binarySearch(arr, value) {
var low = 0;
var high = arr.length - 1;
while(low <= high) {
var mid = Math.floor((low + high) / 2);
if(arr[mid] == value) {
return mid; // 找到该元素,返回位置
} else if(arr[mid] < value) {
low = mid + 1; // 在右边查找
} else {
high = mid - 1; // 在左边查找
}
}
return -1; // 没有找到该元素
}
哈希查找算法是通过哈希表来实现查找的方式,原理是将待查找元素作为关键字,通过哈希函数计算出该元素在哈希表中的位置,然后进行查找。若该位置的元素与待查找元素相等,则返回该元素的值;若不相等,则根据哈希函数的定义找到下一个元素的位置,继续查找。如果遇到哈希表的某个位置的元素为null,则说明该元素不存在于哈希表中。
function hashSearch(arr, value) {
var table = {}; // 哈希表
for(var i = 0; i < arr.length; i++) { // 将数组元素存入哈希表
table[arr[i]] = arr[i];
}
var key = value % arr.length; // 计算待查找元素的哈希值
while(table[key]) { // 若该位置不为空
if(table[key] == value) { // 找到该元素
return key;
} else {
key = (key + 1) % arr.length; // 继续查找下一个元素
}
}
return -1; // 没有找到该元素
}
本文讲述了两种排序算法和两种查找算法。排序算法是程序设计中常见的技术,通过本文的介绍,读者可以更加深入地理解这些算法的原理和实现。查找算法同样广泛应用于程序设计的各个领域,读者可以根据不同的需求选择不同的算法来实现相应的功能。
本文链接:http://task.lmcjl.com/news/10033.html