深入数组拓展应用二
内容大纲
- 冒泡排序
- 选择排序
- 插入排序
- 数组相关面试题
冒泡排序
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从 Z 到 A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
冒泡排序的核心思想如下：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
示意图如下：
下面是冒泡排序具体实现的代码：
// 分解，将大问题拆解成小问题
// 试数，拿一个具体的数去试一下
// 所以我们找一个具体的数组来进行分析
// [3, 8, 1, 5]
// 第一次冒泡
// 3 和 8 进行比较，不交换 [3, 8, 1, 5]
// 8 和 1 进行比较，交换 [3, 1, 8, 5]
// 8 和 5 进行比较，交换[3, 1, 5, 8]
// [3, 1, 5, 8]
// 第二次冒泡
// 3 和 1 进行比较，交换 [1, 3, 5, 8]
// 3 和 5 进行比较，不交换 [1, 3, 5, 8]
// [1, 3, 5, 8]
// 第三次冒泡
// 1 和 3 进行比较，不交换 [1, 3, 5, 8]
var arr = [3, 5, 8, 1, 7, -2, 6, 12, -7, 24, 18];
function bubbleSort(arr) {
var temp = null; // 临时变量，因为我们之后要交换两个数
// 外层 for 循环用于控制冒泡的次数
for (var i = 0; i < arr.length - 1; i++) {
// 内层 for 循环用于控制每一次冒泡比较的次数
// 因为之后每一次冒泡比较的次数会减少，所以 -i
for (var j = 0; j < arr.length - 1 - i; j++) {
// 冒泡始终是相邻的两个数进行比较
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
bubbleSort(arr);
console.log(arr);
选择排序
选择排序（Selection sort）是一种简单直观的排序算法。
它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。
示意图如下：
下面是选择排序的具体实现代码：
var arr = [3, 5, 8, 1, 7, -2, 6, 12, -7, 24, 18];
function selectionSort(arr) {
var min = 0; // 用来记录最小值的索引
var temp = null; // 用来交换两个变量，存储临时值的
// 外层 for 循环遍历整个数组
// 因为最后一个数不需要比较
for (var i = 0; i < arr.length - 1; i++) {
min = i;
// 内层 for 循环也是遍历整个数组，但是是从当前数的下一项
for (var j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
// 更新最小的数的下标
min = j;
}
}
// 等到整个 for 循环跑完之后， min 一定存储的是数组最小值的下标
// 然后这个时候我们再来进行交换
if (min !== i) {
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
}
selectionSort(arr);
console.log(arr);
作业练习
Consider the following code, What will be printed ？
var arr = [23, 18, 1, 9, 7, 6];
var i = 0;
var pos;
while (i < arr.length - 3) {
pos = i;
for (var j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[pos]) {
pos = j;
}
}
var temp = arr[pos];
arr[pos] = arr[i];
arr[i] = temp;
i++
}
console.log(arr);
A. {23, 18, 1, 9, 7, 6}
B. {1, 9, 7, 6, 23, 18}
C. {1, 6, 7, 9, 23, 18}
D. {1, 6, 7, 9, 18, 23}
E. {1, 23, 18, 9, 7, 6}
小结： 冒泡排序是每次比较相邻的两个数比较一轮最后数就最大（或最小），而选择排序是当前数比较后面的所有数选择出最小（或最大）的数
插入排序
插入排序从索引 1 开始，试图将之后的每一个元素都插入到已排好序部分（即外层循环当前位置的左侧部分）的正确位置。
算法会通过将之后元素右移一位的办法把待插入值的位置空出来。右移的操作会一直进行，直到找到了正确位置或已经到了数组开头（证明待插入值其实是已排序部分的最小值）。
一般来说，插入排序都采用就地在数组上实现具体算法描述如下：
- 从第一个元素开始，该元素可以认为已经被排序;
- 取出下一个元素，在已经排序的元素序列中从后向前扫描;
- 如果该元素（已排序）大于新元素，将该元素移到下一位置;
- 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置;
- 将新元素插入到该位置后;
- 重复步骤 2 〜 5。
示意图如下：
插入排序具体实现代码如下：
var arr = [3, 5, 8, 1, 7, -2, 6, 12, -7, 24, 18];
function insertSort(arr) {
var i, j, insertNode; // 要插入的数据
// 从数组的第二个元素开始循环将数组中的元素插入
for (i = 1; i < arr.length; i++) {
// 设置数组中的第 2 个元素为第一次循环要插入的数据
insertNode = arr[i];
j = i - 1;
// 如果要插入的元素小于第j个元素，就将第 j 个元素向后移
while ((j >= 0) && insertNode < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
// 直到要插入的元素不小于第 j 个元素，将 insertNote 插入到数组中
arr[j + 1] = insertNode;
}
}
insertSort(arr);
console.log(arr);
作业练习
Consider the following code, What will be printed ?
var arr = [13, 18, 11, 29, 1];
var pos;
for (var i = 1; i < arr.length - 2; i++) {
pos = arr[i];
var j = i - 1;
while (j >= 0 && pos < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = pos;
}
console.log(arr);
A. {13, 18, 11, 29, 1}
B. {13, 18, 29, 29, 1}
C. {1, 11, 13, 18, 29}
D. {11, 13, 18, 29, 1}
E. {1, 11, 13, 29, 18}
数组相关面试题
第一题
给定两个数组，分别求出这两个数组的交集、并集、差集和补集。
例如：给定 a = [ 1, 2, 3, 4, 5 ]，b = [ 2, 4, 6, 8, 10 ]。a 与 b 的交集为 [ 2, 4 ]，a 与 b 的补集： [ 1, 3, 5, 6, 8, 10 ]，a 与 b 的并集： [ 1, 2, 3, 4, 5, 6, 8, 10 ]，a 与 b 的差集： [ 1, 3, 5 ]
解答：
在解答这道题目之前，我们首先需要复习数学中的交集、并集、差集和补集这几个概念。
- 交集：属于 a 或者属于 b 的元素的集合，也就是 a & b（图一）
- 补集：a 和 b 非相交的部分的元素的集合，也就是 a ^ b（图二）
- 并集：属于 a 或者属于 b 的元素的集合，也就是 a | b（图三）
- 差集：所有属于 a 但是不属于 b 的元素的集合，也就是 a - b（图四）
var a = [1, 2, 3, 4, 5];
var b = [2, 4, 6, 8, 10];
// 交集
// 思路：遍历 a 数组，返回 a 数组中那些在 b 数组中有的元素
var intersect = a.filter(function (item) {
return b.indexOf(item) !== -1
})
// 补集
// 思路：遍历 a 数组，找到 a 数组中那些在 b 数组不存在的元素
// 遍历 b 数组，找到 b 数组中那些在 a 数组不存在的元素
// 最后两个数组进行拼接
var complement = a.filter(function (item) {
return b.indexOf(item) === -1
}).concat(b.filter(function (item) {
return a.indexOf(item) === -1
}))
// 并集
// 思路：找到 b 数组中那些在 a 数组中不存在的元素，之后再与 a 数组拼接
var unionSet = a.concat(b.filter(function (item) {
return a.indexOf(item) === -1
}));
// 差集
// 思路：遍历 a 数组，找到 a 数组中那些在 b 数组中没有的元素
var minus = a.filter(function (item) {
return b.indexOf(item) === -1
})
console.log("数组a:", a);
console.log("数组b:", b);
console.log("a与b的交集:", intersect);
console.log("a与b的补集:", complement);
console.log("a与b的并集:", unionSet);
console.log("a与b的差集:", minus);
第二题
两个数组合并成一个数组
请把两个数组 [ ‘A1’, ‘A2’, ‘B1’, ‘C1’, ‘C2’, ‘C3’, ‘D3’, ‘D2’ ] 和 [ ‘A’, ‘B’, ‘C’, ‘D’ ]，合并为
[ ‘A1’, ‘A2’, ‘A’, ‘B1’, ‘B’, ‘C1’, ‘C2’, ‘C3’, ‘C’, ‘D2’, ‘D3’, ‘D’ ]。
解题思路：既然是要合并成一个数组，所以我们先做合并的操作，之后按照一定的规则进行排序即可。
解答：
var arr1 = ['A1', 'A2', 'B1', 'C1', 'C2', 'C3', 'D3', 'D2'];
var arr2 = ['A', 'B', 'C', 'D'];
console.log(
arr1.concat(arr2).sort(
(v2, v1) => (
v2.codePointAt(0) - v1.codePointAt(0) ||
v1.length - v2.length ||
v2.codePointAt(1) - v1.codePointAt(1)
)
)
);
后面学习了 ES6 之后，合并数组还可以写作：
[...arr1, ...arr2]
第三题
给定一个数组 arr，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
例如输入 [ 0, 0, 1, 0, 3, 12 ]，之后输出 [ 1, 3, 12, 0, 0, 0 ]。
解答：
/**
* @param {number[]} arr
* @return {void} Do not return anything, modify arr in-place instead.
*/
var moveZeroes = function (arr) {
var count = 0;
// 遍历整个数组
for (var i = 0; i < arr.length; i++) {
if (arr[i] === 0) {
arr.splice(i, 1); // 如果当前项为 0，则需要删除
i--; // 下一位会变成上一位，所以需要重新判断
count++; // 计数器进行技术
}
}
// 删除了多少个零，最后就需要在数组末尾补多少个零
for (var i = 0; i < count; i++) {
arr.push(0);
}
};
var arr = [0, 0, 1, 0, 3, 12];
moveZeroes(arr);
console.log(arr); // [ 1, 3, 12, 0, 0 ]
-EOF-