Loading...
墨滴

Shinkai005

2021/12/09  阅读:24  主题:红绯

js常见排序算法

  • 冒泡排序bubbleSort
  • 选择排序selectionSort
  • 插入排序insertionSort
  • 归并排序mergeSort
  • 快速排序quickSort

冒泡排序bubbleSort

gif图解

img
img

算法思路

  • 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
  • 针对所有的元素重复以上的步骤,除了最后一个;
  • 重复步骤1~3,直到排序完成。

算法实现

Array.prototype.bubbleSort = function ({
    for (let i = 0; i < this.length - 1; i++) {
        for (let j = 0; j < this.length - 1 - i; j++) {
            if (this[j] > this[j + 1]) {
                [this[j], this[j + 1]] = [this[j + 1], this[j]];
            }
            console.log(this[j], this[j + 1])
        }
    }

    console.log(this);
}
const arr = [54321];
arr.bubbleSort();

总结

属于入门级别的算法,但是很有趣.特定场合会常用

时间复杂度

O(n^2)

选择排序selectionSort

gif图解

img
img

算法思路

  • 遍历
  • 把当前没有排序过的元素设置成最小值
  • 如果元素<现在的最小值
  • 将当前元素设置为最小值
  • 将最小值和第一个没有排序过的元素位置交换
  • 遍历一次找到一个最小值

算法实现

Array.prototype.selectionSort = function ({
    for (let i = 0; i < this.length; i++) {
        let indexMin = i;
        for (let j = i; j < this.length; j++) {
            if (this[j] < this[indexMin]) {
                indexMin = j;
            }
        }
        if(indexMin !== i) [this[i], this[indexMin]] = [this[indexMin], this[i]];//swap
    }

}

const arr = [5,4,3,2,1];
arr.selectionSort();


总结

双重for循环时间复杂度还是很高的.

时间复杂度

O(n^2)

插入排序insertionSort

从这个开始比较难了,前两个 冒泡和选择排序相当于热身.

gif图解

img
img

算法思路

  • 从当前位置,下一个数开始往前比
  • 比前面的数大就不动, 比前面数小,就往前插入(在大于小于中间插入).
  • 依次类推,一遍就可以结束所有排序.

算法实现

这块写一下我的算法和老师的算法吧.

我写的

Array.prototype.myinsertionSort = function ({
    for (let i = 1; i < this.length; i++) {
        let temp = i;
        for (let j = i - 1this[j] > this[temp]; j--) {
            [this[j], this[temp]] = [this[temp], this[j]];
            temp--;
            console.log(this);
        }
    }
}

老师写的

Array.prototype.insertionSort = function ({
    for (let i = 1; i < this.length; i++) {
        const temp = this[i];
        let j = i;
        while(j>0){
            if(this[j-1]>temp) {
                this[j] = this[j-1];
            }else{
                break;
            }
            j--;
            console.log(this);
        }
        this[j] = temp;
    }
}

总结

解释下我的算法和老师的算法吧

从我的开始说

  • 刚开始是没有写外层for循环的, 第一步我先解决 第一次排序问题. ---也就是第二个数的位置
  • 我采用的是交换元素.
  • 交换后,因为发现用i--的话回到外层循环i会改变,这个时候(也只能这样)就需要一个临时变量temp来保存i值.
  • 然后就是因为我采用的是交换,因此,我需要temp--

老师的代码

  • 首先 扫第一眼,else break 真的丑!!!!!! 当然老师也是为了符合普通人最开始的思路.
  • 其次.老师不是采用的交换元素,而是,把前面元素后移,
    • 比如, 3421比较的时候, 中间调试会生成 3441数组, 3341数组, 最后2341.

复杂度没区别,只是单纯的我是js入手,解构赋值交换变量实在太方便了.老师的写法像是java入手的.

优化一下,

Array.prototype.myinsertionSort = function ({
    for (let i = 1; i < this.length; i++) {
        let temp = this[i];
        let j = i
        for ( j ; this[j-1] > temp; j--) {
            this[j] = this[j-1];
        }
        this[j]=temp;
    }
    console.log(this);
}

还是感觉老师的好, 因为没有找到最终位置的时候交换位置,不是浪费资源了么?

时间复杂度

O(n^2)

归并排序mergeSort

gif图解

img
img

算法思路

分: 把数组劈成两半, 再递归地对子数组进行'分'操作,直到分成一个个单独的数

合: 把两个数合并为有序数组,再对有序数组进行合并,直到全部子数组合并为一个完整数组.

蛮抽象的,继续往下看

合并两个有序数组

  • 新建一个空数组res,用于存放最终排序后的数组
  • 比较两个有序数组的头部,较小者出队并退出res中
  • 如果两个数组还有值重复第二步.

...还真是分两半... 取数组长度然后/2, 不断的递归直到长度为1.

算法实现

Array.prototype.mergeSort = function ({
    const rec = (arr) => {
        if (arr.length === 1) {
            return arr;
        }
        const mid = Math.floor(arr.length / 2);
        const left = arr.slice(0, mid);
        const right = arr.slice(mid, arr.length);
        const orderLeft = rec(left);
        const orderRight = rec(right);
        const res = [];
        while (orderLeft.length || orderRight.length) {
            if (orderLeft.length && orderRight.length) {
                res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift());
            } else if (orderLeft.length) {
                res.push(orderLeft.shift());
            } else if (orderRight.length) {
                res.push(orderRight.shift());
            }
        }
        console.log(res);
        return res;
    };
    rec(this);
}
const arr = [54321];
arr.mergeSort();

时间复杂度

时间复杂度是O(n*logN);

分: 每次都需要把数组劈成两半,2^k = n k= logN 有个二的但是数量级是logN.

合: O(n);极端情况, 每个都分成长度1,也就是n个数组合并

时间复杂度n*logn

快速排序quickSort

chrome 是用快排实现的数组sort方法.

gif图解

img
img

算法思路

分区:从数组中任意选择一个"基准",所有比基准小的元素放在基准前面, 比基准大的元素放在基准的后面

递归: 递归地对基准前后数组进行分区.

算法实现

Array.prototype.quickSort = function ({
    const rec = (arr) => {
        // 不能写this,this是调用的数组,arr是当前迭代数组
        if (arr.length === 1) {
            return arr;
        }
        const left = [];
        const right = [];
        const mid = arr[0];
        // 分区
        for (let i = 1; i < arr.length; i++) {
            if (arr[i] < mid) {
                left.push(arr[i]);
            } else {
                right.push(arr[i]);
            }
        }
        return [...rec(left), mid, ...rec(right)];
    };
    const res = rec(this);
    // console.log(res);
    // return res;
    res.forEach((n, i) => {
        this[i] = n
    });
};
const arr = [24531];
console.log(arr.quickSort());

时间复杂度

递归的时间复杂度O(logN);

分区 O(n) 寻找所有比基准小的

时间复杂度O(nlogN)

Shinkai005

2021/12/09  阅读:24  主题:红绯

作者介绍

Shinkai005