📙 插入排序习题
习题1
重写插入排序过程，使之按非升序排序。
查看代码
function insertionSort (originalArray) {
const array = [...originalArray]
let currentElement, preIndex
for (let i = 1; i < array.length; i++) {
preIndex = i - 1
currentElement = array[i]
while (preIndex >= 0 && currentElement > array[preIndex])) {
array[preIndex + 1] = array[preIndex--]
}
array[preIndex + 1] = currentElement
}
return array
}
习题2
考虑查找问题：
输入：n个数的一个序列A = [a1, a2, a3, ..., an]和一个值v
输出：下标i使得v = A[i]或者v不在A中出现时，输出null
写出线性查找的JavaScript实现。
查看代码
function linearSearch (array, search) {
for (let i = 0; i < array.length; i++) {
if (array[i] === search) {
return i
}
}
return null
}
习题3
考虑把两个n位二进制整数加起来的问题，这两个整数分别存储在两个n元数组A和B中。这两个整数的和应按二进制形式存储在一个（n + 1）元的数组C中，请给出该问题的形式化描述，并写出JavaScript实现。
查看答案
答案
形式化描述：
输入： A = [1, 1, 1, 1]、B=[0, 0, 1, 1]
输出： C = [1, 1, 0, 1, 1]
友情提示：
查看代码
function addBinary (bin1, bin2) {
const length = bin1.length > bin2.length ? bin1.length : bin2.length
const bin = new Array(length + 1)
let carry = 0
let sum
let i
for (i = 0; i < length; i++) {
bin1[i] |= 0
bin2[i] |= 0
sum = bin1[i] + bin2[i] + carry
bin[i] = sum % 2
carry = Math.floor(sum / 2)
}
bin[i] = carry
return bin
}