深入数组拓展应用二

内容大纲

• 冒泡排序
• 选择排序
• 插入排序
• 数组相关面试题

冒泡排序

冒泡排序（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 开始，试图将之后的每一个元素都插入到已排好序部分（即外层循环当前位置的左侧部分）的正确位置。

算法会通过将之后元素右移一位的办法把待插入值的位置空出来。右移的操作会一直进行，直到找到了正确位置或已经到了数组开头（证明待插入值其实是已排序部分的最小值）。

一般来说，插入排序都采用就地在数组上实现具体算法描述如下：

1. 从第一个元素开始，该元素可以认为已经被排序;
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描;
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置;
4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置;
5. 将新元素插入到该位置后;
6. 重复步骤 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-