1.冒泡排序

# 1.冒泡排序

冒泡排序算法的原理如下：
一、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
二、对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
三、针对所有的元素重复以上的步骤，除了最后一个。
四、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
冒泡排序最好的时间复杂度为 O(n)
冒泡排序最坏的时间复杂度 O(n^2)
冒泡排序总的平均时间复杂度为 O(n^2)

var myarr = [1, 32, 34, 5, 7, 34, 89, -5];

// 一、创建一个临时变量
function bubbleSort(arr) {
  for (i = 0; i < arr.length - 1; i++) {
    for (j = 0; j < arr.length - i - 1; j++) {
      // ">" 从小到大排序
      // "<" 从大到小排序
      // 核心算法
      if (arr[j] > arr[j + 1]) {
        var temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

console.log(bubbleSort(myarr));

// 二、异或^
function method2(arr) {
  for (var i = 0; i < arr.length - 1; i++) {
    for (var j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        arr[j] = arr[j] ^ arr[j + 1];
        arr[j + 1] = arr[j] ^ arr[j + 1];
        arr[j] = arr[j] ^ arr[j + 1];
      }
    }
  }
  return arr;
}

console.log(method2(myarr));

// 三、Es6 解构赋值 [a, b] = [b, a]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

# 2.选择排序

function selectSort(arr) {
  for (var i = 0; i < arr.length - 1; i++) {
    var max = i;
    for (var j = i + 1; j < arr.length; j++) {
      if (arr[max] < arr[j]) {
        max = j;
      }
    }
    arr[max] = arr[max] ^ arr[i];
    arr[i] = arr[max] ^ arr[i];
    arr[max] = arr[max] ^ arr[i];
  }
  return arr;
}

var arrs = [1, -32, 6, 3, 55, 41, 13, 45, 54, 41];
console.log(xxselectSort(arrs));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 3.插入排序

function insertionSort(array) {
  for (var i = 1; i < array.length; i++) {
    var key = array[i];
    var j = i - 1;
    while (array[j] > key) {
      array[j + 1] = array[j];
      j--;
      console.log(j);
    }
    array[j + 1] = key;
  }
  return array;
}

var arr = [43, 534, 5];
console.log(insertionSort(arr));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 4.二分查找

适用条件：
必须是顺序存储结构
必须按照关键字大小排列
O(h) = O(log2 n)

function binarySerach(tar, arr, start, end) {
  let left = start || 0;
  let right = end || arr.lenght;
  let mid = 0;
  while (right >= left) {
    mid = parseInt((right + left) / 2);
    if (tar === mid) {
      return mid;
    } else if (tar > mid) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 应用题-1. 判断字符串是否是回文

// 回文（回文），是指数或者字符串具有首尾回环性质，从后向前按位颠倒后与原文一样。

// 首尾回环的数字就是回文数，如：121,12321;首尾回环的字符串就是回文串，如：'madam'。

var isPalindrome = function(x) {
  return (
    x
      .split("")
      .reverse()
      .join("") === x
  );
};
console.log(isPalindrome("121"));

1
2
3
4
5
6
7
8
9
10
11
12
13

# 应用题-2. 统计一个字符串出现最多的字母

function countmost(str) {
  let charObj = {};
  for (let i = 0; i < str.length; i++) {
    if (!charObj[str.charAt(i)]) {
      charObj[str.charAt(i)] = 1;
    } else {
      charObj[str.charAt(i)] += 1;
    }
  }

  let maxChar = "",
    maxValue = 1;
  for (var k in charObj) {
    if (charObj[k] >= maxValue) {
      maxChar = k;
      maxValue = charObj[k];
    }
  }
  return charObj;
}
console.log(countmost("nbkcdmmmabac"));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 应用题-3. 找到字符串的最长无重复字符子串

var lengthOfLongestSubstring = function(s) {
  var res = 0; // 用于存放当前最长无重复子串的长度
  var str = ""; // 用于存放无重复子串
  var len = s.length;
  for (var i = 0; i < len; i++) {
    var char = s.charAt(i);
    var index = str.indexOf(char);
    if (index === -1) {
      str += char;
      res = res < str.length ? str.length : res;
    } else {
      str = str.substr(index + 1) + char;
    }
  }
  return [res, str];
};
console.log(lengthOfLongestSubstring("abcmafdc"));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 应用题-4. 找到字符串的最长无重复字符子串(未实现)

// 例如：将A转成B
A = [
  { id: 1, type: null },
  { id: 2, type: null },
  { id: 3, type: null }
];

B = {
  id: 1,
  type: null,
  child: {
    id: 2,
    type: null,
    child: {
      id: 3,
      type: null
    }
  }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 应用题-5. JS 递归实现杨辉三角

1
1 1
1 2 1
...
输入 n ,输出数组
假设输入 3，输出数组 [[1],[1,1],[1,2,1]]

1
2
3
4
5
6

function triangle(num) {
  let arr = [];
  arr.push([1]);
  loop([1]);

  function loop(lastarr) {
    // 代码循环的部分
    if (lastarr.length < num) {
      let newarr = [];
      newarr[0] = 1; // 头部是1
      newarr[lastarr.length] = 1; // 尾部也是1
      for (let i = 0; i < lastarr.length - 1; i++) {
        newarr[i + 1] = lastarr[i] + lastarr[i + 1];
      }
      arr.push(newarr);
      loop(newarr);
    }
  }
  return arr;
}
console.log(triangle(5));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

如果是需要输入下面的结果

1
1 1
1 2 1
...
输入 n ,输出数组
假设输入 3，输出数组 [1, 1, 1, 1, 2, 1]

1
2
3
4
5
6

只需要添加 arr.push 的时候添加扩展运算符(...)即可，这里只需要更改两个地方

1. arr.push([1])  改成 arr.push(...[1])
2. arr.push(newarr)  改成 arr.push(...newarr)

1
2

# 应用题-6. 找出数组中第 k 大的数字出现多少次

# 题目：给定一个一维数组，如[1,2,4,4,3,5]，找出数组中第 k 大的数字出现多少次

例如：第 2 大的数是 4，出现 2 次，最后输出 4,2

function getNum(arr, k) {
  // 数组排序->从大到小
  arr.sort((a, b) => b - a);
  let uniqarr = Array.from(new Set(arr)); // 数组去重
  let tar = uniqarr[k - 1]; // 找到目标元素
  let index = arr.indexOf(tar); // 寻找索引
  let num; // 利用元素之间的索引来得出该数字的数量

  if (k == uniqarr.length) {
    // 需要判断是否为数组的最后一个元素(即最小值)
    num = arr.length - index;
  } else {
    let indexnext = arr.indexOf(uniqarr[k]);
    num = indexnext - index;
  }
  return [tar, num];
}

let arr = [1, 2, 4, 4, 3, 5];
console.log(...getNum(arr, 2));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 应用题-7. 二维数组中（每个一维数组的长度相同），左右和上下分别递增，求是否含有指定整数

# 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

我们先假设一个二维数组列出来，形成一个矩阵，便于我们的理解

[10, 20, 40, 60],
[20, 30, 70, 90],
[40, 50, 80, 110]

# 根据题意我们可以得到如下理论：

① 最小数（min）是第一行第一个，最大数（max）是最后一行的最后一个
② 每一行最大的一个数是每一行的最后一个，每一行最小一个数是每一行的第一个

根据第一个结论我们就可以先判断这个数是否在这个矩阵内

let min = array[0][0];
let max = array[array.length - 1][array[0].length - 1];
if (target < min || target > max) return false;

1
2
3

接下来，我们就根据第二个条件来查找：思路如下

先从第一行的最后一个数（称为 J），开始比较，如果目标大于 J，则与下一行的最后一个数比较，如此循环，直到目标比 J 小

当目标比 J 小时，我们就能确定是哪一行，之后你懂得，代码如下

function Find(target, array) {
  let i = 0;
  let j = array[i].length - 1;
  let min = array[0][0];
  let max = array[array.length - 1][array[0].length - 1];

  if (target < min || target > max) return false;

  while (i < array.length && j >= 0) {
    if (array[i][j] < target) {
      i++;
    } else if (array[i][j] > target) {
      j--;
    } else {
      return true;
    }
  }
  return false;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 应用题-8. 给定两个维度不确定的数组，求它们之间不重复的数据合集,返回一个新数组

如给定：

arr1 = [11, 25, 44, [52, 44, 23], '52']
arr2 = [16, 25, 17, [11, 25, [23, 18]]]
返回：[52, "52", 16, 17, 18]

本次需要考虑的问题：

# 1、数组降维

因为数组的维度是不确定的，我们需要做的是把两个数组都转换成一维数组
在 ES6 中，提供了这么一个方法

Array.prototype.flat();

在数组的层次不确定时，可以使用 Infinity 关键字作为参数，即：

Array.prototype.flat(Infinity);

# 2、使用对象来判断数据出现的次数

本次需要的数据是：两个数组合并后只出现一次的数据，这里我想到的是采用对象的键值对方法，但是由于普通对象的键是字符串类型，对于数组中同时出现字符串和数值类型则无法判断，所以我采用 Map 集合来存储数据，Map 集合是 ES6 提供的一个完整的 hash 结构，键可以是任意类型

代码如下

function fn(arr1, arr2) {
  let map = new Map();
  let res = [];
  let arr = arr1.flat(Infinity).concat(arr2.flat(Infinity));
  arr.forEach(ele => {
    map.has(ele) ? map.set(ele, false) : map.set(ele, true);
  });
  for (let [key, val] of map.entries()) {
    if (val) {
      res.push(key);
    }
  }
  return res;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

测试代码：

let arr1 = [11, 25, 44, [52, 44, 23], "52"];
let arr2 = [16, 25, 17, [11, 25, [23, 18]]];
console.log(fn(arr1, arr2));

1
2
3

结果：

[52, "52", 16, 17, 18];

← JS代码练习工具库 →