算法题
斐波拉契数列
function f(n) {
if (n == 0 || n == 1) {
return n;
}
else {
return f(n-1) + f(n - 2);
}
}
1.冒泡排序
好、中、坏：O(n)、O(n2)、O(n2)
function bubbleSort(arr) {
var len = arr.length;
var temp;
for (var i = 0; i < len; i++) {
for (var j = 0; j < len - 1 - i; j++) { // 对第一个元素冒泡，这样一趟下来，最大的会排到最后面
if (arr[j] > arr[j+1]) { //相邻元素两两对比
temp = arr[j+1]; //元素交换
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
2.选择排序 （每一趟都选择最小元素与当前比较元素交换位置）
好 中 坏 ： O(n2)、O(n2)、O(n^2)
function selectionSort(arr) {
var temp;
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;
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
3.插入排序（）（ ）（ ）
好、平、坏：O(n2)、O(n)、O(n2)
function insertSort(arr) {
var temp, i;
var len = arr.length;
for (var j = 1; j < len; ++j) {
temp = arr[j];
i = j;
while (i > 0 && (arr[i - 1] >= temp)) {
arr[i] = arr[i - 1];
--i;
}
arr[i] = temp;
}
return arr;
}
4.希尔排序
好 中 坏 ： O(n1.3)、O(nlogn)-O(n2)、O(n^2)
function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
while(gap < len/3) { //动态定义间隔序列
gap = gap*3+1;
}
for (gap; gap > 0; gap = Math.floor(gap/3)) {
for (var i = gap; i < len; i++) {
temp = arr[i];
for (var j = i-gap; j >= 0 && arr[j] > temp; j -= gap) {
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
return arr;
}
5.归并排序
好、平、坏：O(nlogn)、O(nlogn)、O(nlogn)
function mergeSort(arr) { //采用自上而下的递归方法
var len = arr.length;
if(len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
var result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}
6.快速排序
好、平、坏：O(nlogn)、O(nlogn)、O(n^2)
function qSort(arr) {
var len = arr.length;
if (len == 0) {
return [];
}
var left = [];
var right = [];
var flag = arr[0];
for (var i = 1; i < len; i++) {
if (arr[i] < flag) {
left.push(arr[i]);
}
else {
right.push(arr[i]);
}
}
return qSort(left).concat(flag, qSort(right));
}
///////////////////////////////////////////////////////
var arr = [2,1,3,4,3];
var m = qSort(arr);
console.log(m); //[1, 2, 3, 3, 4]
7.堆排序
1.它是选择排序的一种。
2.可以利用数组的特点快速定位指定索引的元素。
3.堆分为大根堆和小根堆，是完全二叉树。
4.大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
function buildMaxHeap(arr) { //建立大顶堆
len = arr.length;
for (var i = Math.floor(len/2) - 1; i >= 0; i--) {
heapify(arr, i);
}
}
function heapify(arr, i) { //堆调整
var left = 2 * i + 1,
right = 2 * i + 2,
largest = i;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, largest);
}
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function heapSort(arr) {
buildMaxHeap(arr);
for (var i = arr.length-1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0);
}
return arr;
}
var arr=[91,60,96,13,35,65,46,65,10,30,20,31,77,81,22];
console.log(heapSort(arr));//[10, 13, 20, 22, 30, 31, 35, 46, 60, 65, 65, 77, 81, 91, 96]
BST遍历
// 中序：
function inOrder(node) {
if (!(node == null)) {
inOrder(node.left);
putstr(node.show() + " ");
inOrder(node.right);
}
}
// 先序：
function preOrder(node) {
if (!(node == null)) {
putstr(node.show() + " ");
preOrder(node.left);
preOrder(node.right);
}
}
// 后序：
function postOrder(node) {
if (!(node == null)) {
postOrder(node.left);
postOrder(node.right);
putstr(node.show() + " ");
}
}
DFS&BFS
// 深度优先遍历
function dfs(v) {
this.marked[v] = true;
for each(var w in this.adj[v]) {
if (!this.marked[w]) {
this.dfs(w);
}
}
}
// 广度优先遍历
function bfs(s) {
var queue = [];
this.marked[s] = true;
queue.push(s); // 添加到队尾
while (queue.length > 0) {
var v = queue.shift(); // 从队首移除
if (v == undefined) {
print("Visisted vertex: " + v);
}
for each(var w in this.adj[v]) {
if (!this.marked[w]) {
this.edgeTo[w] = v;
this.marked[w] = true;
queue.push(w);
}
}
}
}
二分搜索算法
function binSearch(arr, data) {
var low = 0;
var high = arr.length-1;
while (low <= high) {
var mid = Math.floor((high + low) / 2);
if (data < arr[mid]) {
high = mid - 1; }
else if (data > arr[mid]) {
low = mid + 1;
}
else {
return mid;
}
}
return -1;
}
不借助临时变量，进行两个整数的交换
输入 a = 2, b = 4 输出 a = 4, b =2
这种问题非常巧妙，需要大家跳出惯有的思维，利用 a , b进行置换。
主要是利用 + – 去进行运算，类似 a = a + ( b – a) 实际上等同于最后 的 a = b;
function swap(a , b) {
b = b - a;
a = a + b;
b = a - b;
return [a,b];
}
随机生成指定长度的字符串
实现一个算法，随机生成指制定长度的字符窜。
比如给定 长度 8 输出 4ldkfg9j
function randomString(n) {
let str = 'abcdefghijklmnopqrstuvwxyz9876543210';
let tmp = '',
i = 0,
l = str.length;
for (i = 0; i < n; i++) {
tmp += str.charAt(Math.floor(Math.random() * l));
}
return tmp;
}
实现类似getElementsByClassName 的功能
自己实现一个函数，查找某个DOM节点下面的包含某个class的所有DOM节点？不允许使用原生提供的 getElementsByClassName querySelectorAll 等原生提供DOM查找函数。
function queryClassName(node, name) {
var starts = '(^|[
f])',
ends = '([
f]|$)';
var array = [],
regex = new RegExp(starts + name + ends),
elements = node.getElementsByTagName("*"),
length = elements.length,
i = 0,
element;
while (i < length) {
element = elements[i];
if (regex.test(element.className)) {
array.push(element);
}
i += 1;
}
return array;
}