js 排序算法 2021-07-13

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

三个 数的最小值

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

image.png

任意长度的排序

image.png 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]

image.png

快速排序

image.png image.png image.png

归并排序

image.png image.png image.png image.png image.png