minof2 两个值中的最小值
求两个数最小值
let minof2 = ([a,b]) => a < b ? a : b;
minof2([8,4]);
求三个数最小值
let minof3 = ([a,b,c]) => {
return minof2([a,minof2([b,c])])
};
minof3([3,4,6]);
推理 求四个数
let minof4 = ([a,b,c,d]) => {
return minof2([a,minof3([b,c,d])])
};
minof4([5,2,3,4]);
求任意长度的最小值
let min = (numbers) => {
if (numbers.length > 2){
return min([numbers[0],min(numbers.slice(1))])
}else{
return Math.min.apply(null,numbers)
}
}
min([9,4,3,1]);
步骤:
min(9,min([4,3,1])) = min(9,min(4,min(3,1)))
= min(9,min(4,Math.min.apply(null,[3,1])))
= min(9,min(4,1))
= min(9,1)
=Math.min.apply(null,[9,1])=1
析构赋值
image.png
image.png
三个 数的最小值

求任意长度的最小值

实现sort排序
let sort2 = ([a,b]) => a < b ? [a,b] : [b,a];
let min = (numbers) => {
if (numbers.length > 2){
return min([numbers[0],min(numbers.slice(1))])
}else{
return Math.min.apply(null,numbers)
}}
}
let minIndex = (numbers) => numbers.indexOf(min(numbers));
let sort3 = (numbers) => {
let index = minIndex(numbers)
let min = numbers[index]
numbers.splice(index, 1)
return [min].concat(sort2(numbers))
}
sort3([44,3,5]);
let sort = (numbers) => {
if (numbers.length > 2){
let index = minIndex(numbers)
let min = numbers[index]
numbers.splice(index,1)
return [min].concat(sort(numbers))
}else {
return numbers[0] < numbers[1] ? numbers : numbers.reverse()
}
}
sort([55,6,2,8,3]);
步骤
[2].concat(sort([55,6,8,3]))
[2].concat([3].concat(sort([55,6,8])))
[2].concat([3].concat([6].concat(sort([55,8]))))
[2].concat([3].concat([6].concat(sort([55,8]))))
[2].concat([3].concat([6].concat([8,55])]))
优化一下 minIndex
let minIndex = (numbers) => {
let index = 0;
for (let i = 1; i < numbers.length; i++) {
if (numbers[i] < numbers[index]) {
index = i
}
}
return index
}
image.png
bug 如果有两个相同的最小值 就会有bug
image.png

任意长度的排序


选择排序的循环写法
let minIndex = (numbers) => {
let index = 0;
for (let i = 1; i < numbers.length; i++) {
if (numbers[i] < numbers[index]) {
index = i
}
}
return index
}
//交换数组中两个元素的位置
let swap = (array, i, j) => {
let tmp = array[i]
array[i] = array[j]
array[j] = tmp
return array
}
swap([1,2,3,4],1,2);
let sort = (numbers) => {
for (let i = 0; i < numbers.length - 1; i++) {
//取最小值下标之后 数组要slice i 个位置
let index = minIndex(numbers.slice(i)) + i;
console.log(`index: ${index}`)
if (index !== i){
swap(numbers, index, i)
}
}
}
过程
[5, 1, 2, 56, 9]
i= 0 index= 1 最小值为 1
[1, 5, 2, 56, 9]
i = 1 index=2 [5, 2, 56, 9] 最小值为2
[1, 2, 5, 56, 9]
i = 2 index= 2 [5,56,9]
[1, 2, 5, 56, 9]
i = 3 index = 4
[1, 2, 5, 9, 56]

快速排序



归并排序





网友评论