用JavaScript实现排序算法（冒泡排序、选择排序、插入排序、快速排序、归并排序）

2022/8/26 1:22:59

编程Tag： 排序 let 元素冒泡排序插入排序 item length 数列

本文主要是介绍用JavaScript实现排序算法（冒泡排序、选择排序、插入排序、快速排序、归并排序），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

冒泡排序

思路：

对未排序的各元素从头到尾依次比较相邻的两个元素大小关系
如果左边的队员高, 则两队员交换位置
向右移动一个位置, 比较下面两个队员
当走到最右端时, 最高的队员一定被放在了最右边
按照这个思路, 从最左端重新开始, 这次走到倒数第二个位置的队员即可.
依次类推, 就可以将数据排序完成

选择排序

思路：

选定第一个索引位置，然后和后面元素依次比较
如果后面的队员, 小于第一个索引位置的队员, 则交换位置
经过一轮的比较后, 可以确定第一个位置是最小的
然后使用同样的方法把剩下的元素逐个比较即可
可以看出选择排序，第一轮会选出最小值，第二轮会选出第二小的值，直到最后

图解：

插入排序

思路：

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复上一个步骤，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后, 重复上面的步骤.

图解：

快速排序

思路：

从数列中挑出一个基准值。
将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，该基准就处于数列的中间位置。
递归地把"基准值前面的子数列"和"基准值后面的子数列"进行排序。

归并排序

思路：

先递归的分解数列，再合并数列

将一个数组拆成A、B两个小组，两个小组继续拆，直到每个小组只有一个元素为止。
按照拆分过程逐步合并小组，由于各小组初始只有一个元素，可以看做小组内部是有序的，合并小组可以被看做是合并两个有序数组的过程。
对左右两个小数列重复第二步，直至各区间只有1个数。

代码实现：

class Sort {

            constructor() {
                this.item = [];
            }

            push(ele) {
                this.item.push(ele)
            }

            toString() {
                return this.item.join("-")
            }

            swap(m, n) {
                // 交换两个位置的值
                let temp = this.item[n];
                this.item[n] = this.item[m]
                this.item[m] = temp
            }



            bubbleSort() {

                // 控制趟数   控制次数
                for (let i = 0; i < this.item.length - 1; i++) {

                    for (let j = 0; j < this.item.length - 1 - i; j++) {

                        // 比较
                        if (this.item[j + 1] < this.item[j]) {
                            this.swap(j, j + 1)
                        }

                    }

                }

            }

            // 选择排序
            selectionSort() {

                for (let i = 0; i < this.item.length - 1; i++) {

                    let min = i;

                    for (let j = i + 1; j < this.item.length; j++) {

                        if (this.item[j] < this.item[min]) {
                            min = j
                        }

                    }

                    this.swap(i, min)
                }

            }


            // 插入排序
            insertionSort() {

                for (let i = 1; i < this.item.length; i++) {

                    let j = i;
                    let mark = this.item[i];

                    while (this.item[j - 1] > mark && j > 0) {

                        this.item[j] = this.item[j - 1];
                        j--;

                    }

                    this.item[j] = mark

                }

            }


            // 快速排序
            quicksort() {
                this.item = this.quick(this.item)
            }

            quick(arr) {
                if (arr.length <= 1) {
                    return arr
                } else {
                    // 分
                    let index = Math.floor(arr.length / 2);
                    let middle = arr.splice(index, 1)[0];

                    let leftArr = [],
                        rightarr = [];
                    for (let i = 0; i < arr.length; i++) {
                        if (arr[i] < middle) {
                            leftArr.push(arr[i])
                        } else {
                            rightarr.push(arr[i])
                        }
                    }

                    return this.quick(leftArr).concat(middle, this.quick(rightarr))

                }
            }

            // 归并排序
            mergerSort() {
               this.item =  this.divide(this.item)
            }

            // 分
            divide(arr) {
                if (arr.length <= 1) {
                    return arr
                } else {
                    let index = Math.floor(arr.length / 2);
                    let leftArr = arr.slice(0, index);
                    let rightArr = arr.slice(index);

                   return this.merge(this.divide(leftArr), this.divide(rightArr))
                }
            }

            // 和
            merge(left, right) {

                let newarr = [];

                while (left.length && right.length) {
                    if (left[0] < right[0]) {
                        newarr.push(left.shift())
                    } else {
                        newarr.push(right.shift())
                    }
                }

                return newarr.concat(left,right)
            }
        }


        let sort = new Sort();
        sort.push(1)
        sort.push(10)
        sort.push(16)
        sort.push(6)
        sort.push(8)
        sort.push(10)
        sort.push(7)


        sort.mergerSort();
        console.log(sort.toString());

这篇关于用JavaScript实现排序算法（冒泡排序、选择排序、插入排序、快速排序、归并排序）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！