深入数组拓展应用二

深入数组拓展应用二

内容大纲

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

冒泡排序

冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从 ZA)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。

冒泡排序的核心思想如下:

比较相邻的元素。如果第一个比第二个大,就交换他们两个。

对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。

针对所有的元素重复以上的步骤,除了最后一个。

持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

示意图如下:

深入数组拓展应用二

下面是冒泡排序具体实现的代码:

// 分解,将大问题拆解成小问题
// 试数,拿一个具体的数去试一下
// 所以我们找一个具体的数组来进行分析
// [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(图一)
  • 补集:ab 非相交的部分的元素的集合,也就是 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-

上一篇:让人想骂街的 Python 炫技操作:条件语句的七种写法


下一篇:springboot系列18: CommandLineRunner解决项目启动时初始化资源