爱折腾的前端

知识总结和回顾

0%

前端算法

发表于 更新于

排序算法

1. 冒泡排序

冒泡排序

普通版冒泡排序

1
2
3
4
5
6
7
8
9
10
11
function BubbleSort(array){
    let len = array.length;
    for(let i = 0; i < len; i++){
        for(let j = 0; j < len-i-1; j++){
            if(array[j] > array[j+1]){
                [array[j], [array[j+1]] = [array[j+1], array[j]];
            }
        }
    }
    return array;
}

优化版冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function BubbleSort(originalArray){
    const array = [...originalArray];
    let swapped;
    for(let i = 0; i < array.length; i++){
        swapped = true;
        for(let j = 0; j < array.length - i - 1; j++){
            if(array[j] > array[j+1]){
                [array[j], array[j+1]] = [array[j+1], array[j]];
                swapped = false;
            }
        }
        if(swapped){
            break;
        }
    }
    return array;
}

2. 选择排序

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function SelectionSort(originalArray){
    const array = [...originalArray];
    let len = array.length;
    for(let i = 0; i < len - 1; i++){
        let minIndex = i;
        for(let j = i + 1; j < len; j++){
            if(array[j] < array[minIndex]){
                minIndex = j;
            }
        }
        if(minIndex !== i){
            [array[minIndex], array[i]] = [array[i], array[minIndex]];
        }
    }
    return array;
}

3. 插入排序

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function InsertionSort(originalArray){
    const array = [...originalArray];
    let len = array.length;
    for(let i = 0; i < len; i++){
        let temp = array[i]
        let j = i - 1;
        while(j >= 0 && array[j] > temp){
            array[j+1] = array[j];
            j--;
        }
        array[j+1] = temp;
    }
    return array;
}

4. 归并排序

并归排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function MergeSort(array){
    let len = array.length;
    if(len <= 1){
        return array;
    }
    let num = Math.floor(len / 2);
    let left = MergeSort(array.slice(0, num));
    let right = MergeSort(array.slice(num, len));
    return merge(left, right);

    function merge(left, right){
        let [l, r] = [0, 0];
        let result = [];
        while(l < left.length && r < right.length){
            if(left[l] < right[r]){
                result.push(left[l]);
                l++;
            }else{
                result.push(right[r]);
                r++;
            }
        }
        result = result.concat(left.slice(l, left.length));
        result = result.concat(right.slice(r, right.length));
        return result;
    }
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function QuickSort(array){
    const len = array.length
    if(len <= 1){
        return array; // 如果只有一个数，就直接返回
    }

    let num = Math.floor(len / 2); // 找到中间数的索引值，如果是浮点数，则向下取整
    let numValue = array.splice(num, 1); // 找到中间数的值
    let left = []
    let right = []
    for(let i = 0; i < len; i++){
        if(array[i] < numValue){
            left.push(array[i]) // 基准点的左边数传到左边数组
        }else{
            right.push(array[i]) // 基准点的右边数传到右边数组
        }
    }
    return QuickSort(left).concat([numValue, QuickSort(right)]);
}