绑定完请刷新页面
取消
刷新
登录 | 注册

分享好友

×
取消 复制
重温前端10大排序算法（长文建议收藏）
2020-01-07 15:53:17


1、冒泡排序

思路

通过相邻元素的比较和交换，使得每一趟循环都能找到未有序数组的大值或小值。

实现

created() {
    let array = [1, 6, 7, 4, 5, 8, 9, , 2, 3];
    let res = this.bubbleSort(array);
    console.log(res);
},
methods: {
    bubbleSort(arr) {
        let length = arr.length;
        if (!length) {
            return [];
        }
        for (let i = ; i < length; i++) {
            for (let j = ; j < length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                }
            }
            console.log(`第${i+1}次循环`, arr);
        }
        return arr;
    }
}

优化：单向冒泡实现

标记在一轮比较汇总中，如果没有需要交换的数据，说明数组已经有序，可以减少排序循环的次数。

created() {
    let array = [1, 6, 7, 4, 5, 8, 9, , 2, 3];
    let res = this.bubbleSort(array);
    console.log(res);
},
methods: {
    bubbleSort(arr) {
        let length = arr.length;
        if (!length) {
            return [];
        }
        for (let i = ; i < length; i++) {
            let mark = true; // 如果在一轮比较中没有出现需要交互的数据，说明数组已经有序，
            for (let j = ; j < length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                    mark = false;
                }
            }
            console.log(mark);
            console.log(`第${i+1}次循环`, arr);
            if (mark) return;
        }
        return arr;
    }
}

优化：双向冒泡实现

普通的冒泡排序，在一轮循环中只能找到大值或者小值的其中一个，双向冒泡排序则是多一轮的筛选，即找出大值也找出小值。

created() {
    let array = [1, 6, 7, 4, 5, 8, 9, , 2, 3];
    let res = this.bubbleSortTow(array);
    console.log(res);
},
methods: {
    bubbleSortTow(arr) {
        let low = ;
        let high = arr.length - 1;
        while (low < high) {
            let mark = true;
            // 找到大值放到右边
            for (let i = low; i < high; i++) {
                if (arr[i] > arr[i + 1]) {
                    [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
                    mark = false;
                }
            }
            high--;
            // 找到小值放到左边
            for (let j = high; j > low; j--) {
                if (arr[j] < arr[j - 1]) {
                    [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
                    mark = false;
                }
            }
            low++;
            console.log(mark);
            console.log(`第${low}次循环`, arr);
            if (mark) return arr;
        }
    }
}

性能比较

对三种排序的算法进行性能的比较：发现单向冒泡排序性能 > 双向冒泡排序性能 > 大于普通冒泡性能。（产生时间具体取决于所使用的系统）

提示

大数据量操作时，请勿模仿，页面已经卡死。

2、选择排序

思路

依次找到剩余元素的小值或者大值，放置在末尾或者开头。

实现

created() {
    let array = [];
    for (let i = ; i < 10; i++) {
        let number = Math.floor(Math.random() * 10);
        array.push(number);
    }
    let res = this.selectSort(array);
    console.log(res);
},
methods: {
    /**
     * 选择排序
     */
    selectSort(arr) {
        let length = arr.length,
            minIndex;
        for(let i = ; i < length -1; i++) {
            minIndex = i;
            for(let j = i+1; j < length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
            console.log(`第${i+1}次循环`, arr);
        }
        return arr;
    }
}


性能比较

对于等量的数据进行性能比价，发现单向冒泡排序性能 > 双向冒泡排序性能 > 选择排序 > 大于普通冒泡性能。（产生时间具体取决于所使用的系统）

提示

选择排序是时间复杂度上表现稳定的算法之一，因为快、慢时间复杂度都是O(n²)，用选择排序数据量越小越好。

3、插入排序

思路

以个元素为有序数组，其后的元素通过再这个已有序的数组中找到合适的元素并插入。

实现

created() {
    let array = [];
    for (let i = ; i < 10; i++) {
        let number = Math.floor(Math.random() * 10);
        array.push(number);
    }
    let res = this.insertSort(array);
    console.log(res);
},
methods: {
    /**
     * 插入排序
     */
    insertSort(arr) {
        let length = arr.length,
            preIndex, current;
        for (let i = 1; i < length; i++) {
            preIndex = i - 1;
            current = arr[i];
            // 和已经排序好的序列进行比较，插入到合适的位置
            while (preIndex >=  && arr[preIndex] > current) {
                arr[preIndex + 1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex + 1] = current;
            console.log(`第${i}次循环`, arr);
        }
        return arr;
    }
}


优化：拆半插入排序实现

在直接插入排序的基础上，在插入的时候运用了折半查找法查找要插入的位置，再进行插入。

created() {
    let array = [];
    for (let i = ; i < 10; i++) {
        let number = Math.floor(Math.random() * 10);
        array.push(number);
    }
    let res = this.binsertSort(array);
    console.log(res);
},
methods: {
    /**
     * 拆半插入排序
     */
    binsertSort(arr) {
        let low, high, j, temp;
        for (let i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i - 1]) {
                temp = arr[i];
                low = ;
                high = i - 1;
                while (low <= high) {
                    let mid = Math.floor((low + high) / 2);
                    if (temp > arr[mid]) {
                        low = mid + 1;
                    } else {
                        high = mid - 1;
                    }
                }
                for (j = i; j > low; --j) {
                    arr[j] = arr[j - 1];
                }
                arr[j] = temp;
            }
            console.log(`第${i}次循环`, arr);
        }
        return arr;
    }
}

性能比较

>=表示性能相差不大

在数据量相当的情况下：发现拆半插入排序 >= 单向冒泡排序性能 > 双向冒泡排序性能 > 插入排序 > 选择排序 > 大于普通冒泡性能。（产生时间具体取决于所使用的系统）

提示

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是容易理解的了。

4、希尔排序

思路

通过某个增量 gap，将整个序列分给若干组，从后往前进行组内成员的比较和交换，随后逐步缩小增量至 1。希尔排序类似于插入排序，只是一开始向前移动的步数从 1 变成了 gap。

实现

created() {
    let array = [];
    for (let i = ; i < 10; i++) {
        let number = Math.floor(Math.random() * 10);
        array.push(number);
    }
    let res = this.shellSort(array);
    console.log(res);
},
methods: {
    /**
     * 希尔排序
     */
    shellSort(arr) {
        let len = arr.length;
        // 初始步数
        let gap = parseInt(len / 2);
        // 逐渐缩小步数
        while (gap) {
            // 从第gap个元素开始遍历
            for (let i = gap; i < len; i++) {
                // 逐步其和前面其他的组成员进行比较和交换
                for (let j = i - gap; j >= ; j -= gap) {
                    if (arr[j] > arr[j + gap]) {
                        [arr[j], arr[j + gap]] = [arr[j + gap], arr[j]];
                    } else {
                        break;
                    }
                }
            }
            gap = parseInt(gap / 2);
        }
    }
}

性能比较

在数据量相当的情况下：发现拆半插入排序 >= 单向冒泡排序性能 > 双向冒泡排序性能 > 插入排序 > 希尔排序 >选择排序 > 大于普通冒泡性能。（产生时间具体取决于所使用的系统）

5、归并排序

思路

递归将数组分为两个序列，有序合并这两个序列。作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

  1. 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第2种方法）。
  2. 自下而上的迭代。

实现

created() {
    let array = [];
    for (let i = ; i < 10; i++) {
        let number = Math.floor(Math.random() * 10);
        array.push(number);
    }
    let res = this.mergeSort(array);
    console.log(res);
},
methods: {
    /**
     * 归并排序
     */
    mergeSort(arr) {
        let len = arr.length;
        if (len < 2) {
            return arr;
        }
        let middle = Math.floor(len / 2),
            left = arr.slice(, middle),
            right = arr.slice(middle);
        console.log(`处理过程：`, arr);
        return this.merge(this.mergeSort(left), this.mergeSort(right));
    },
    /**
     * 归并排序辅助方法
     */
    merge(left, right) {
        let result = [];
        while (left.length && right.length) {
            if (left[] <= right[]) {
                result.push(left.shift());
            } else {
                result.push(right.shift());
            }
        }
        while (left.length) {
            result.push(left.shift());
        }
        while (right.length){
            result.push(right.shift());
        }
        return result;
    }
}

性能比较

在数据量相当的情况下：发现拆半插入排序 >= 单向冒泡排序性能 > 双向冒泡排序性能 > 插入排序 > 希尔排序 > 归并排序 > 选择排序 > 大于普通冒泡性能。（产生时间具体取决于所使用的系统）



6、快速排序

思路

选择一个元素作为基数（通常是个元素），把比基数小的元素放到它左边，比基数大的元素放到它右边（相当于二分），再不断递归基数左右两边的序列。快速排序是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高! 它是处理大数据快的排序算法之一了。

快速排序的坏运行情况是O(n²)，比如说顺序数列的快排。但它的平摊期望时间是O(n log n) ，且O(n log n)记号中隐含的常数因子很小，比复杂度稳定等于O(n log n)的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

举例说明（详解）

例如对以下10个数进行排序： 6 1 2 7 9 3 4 5 10 8

  1. 以6为基准数（一般情况以个为基准数）
  2. 在初始状态下，数字6在序列的位，我们轮的目的是将6移动到一个位置（K），使得K左边的数都<=6，K右边的数字都>=6。
  3. 为找到K的位置，我们需要进行一个搜索过程，从右往左查找一个大于6的数字，位置为j，从左往右查找一个小于6的数字，位置为i，交互j和i上面的数字。
  4. j和i的位置继续移动，重复3步骤。
  5. 当j和i相等时，停止移动，移动到的位置就是位置K，将位置K的数组和6交换。此时6左边的数字都被6小，6右边的数字都比6大。
  6. 将6左边和右边的序列进行上诉操作。

详情更多在：blog.csdn.net/qq_40941722…

实现1

 created() {
    let array = [];
    for (let i = ; i < 10; i++) {
        let number = Math.floor(Math.random() * 10);
        array.push(number);
    }
    console.log(array);
    let res = this.quickSort(array, , array.length - 1);
    console.log(res);
},
methods: {
    /**
     * 快速排序
     */
    quickSort(arr, begin, end) {
        if (begin > end) return arr;
        let temp = arr[begin],
            i = begin,
            j = end;
        while(i != j) {
            while(arr[j] >= temp && j > i) {
                j--;
            }
            while(arr[i] <= temp && j > i) {
                i++;
            }
            if (j > i) {
                [arr[i], arr[j]] = [arr[j], arr[i]];
            }
        }
        [arr[begin], arr[i]] = [arr[i], temp];
        console.log(`${arr[i]}作为基准点：`, arr);
        this.quickSort(arr, begin, i - 1);
        this.quickSort(arr, i + 1, end);
        return arr;
    },
}

实现2

 created() {
    let array = [];
    for (let i = ; i < 10; i++) {
        let number = Math.floor(Math.random() * 10);
        array.push(number);
    }
    console.log(array);
    let res = this.quickSortOne(array, , array.length - 1);
    console.log(res);
},
methods: {
    /**
     * 快速排序
     */
    quickSortOne(arr, left, right) {
        var len = arr.length,
            partitionIndex,
            left = typeof left != 'number' ?  : left,
            right = typeof right != 'number' ? len - 1 : right;

        if (left < right) {
            partitionIndex = this.partition(arr, left, right);
            console.log(`${arr[partitionIndex]}作为基准点：`, arr);
            this.quickSortOne(arr, left, partitionIndex - 1);
            this.quickSortOne(arr, partitionIndex + 1, right);
        }
        return arr;
    },
    /**
     * 快速排序辅助方法-寻找基准值
     */
    partition(arr, left, right) {
        let pivot = left,
            index = pivot + 1;
        for (let i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                [arr[i], arr[index]] = [arr[index], arr[i]];
                index++;
            }
        }
        [arr[pivot], arr[index - 1]] = [arr[index - 1], arr[pivot]];
        return index - 1;
    }
}

性能比较

在数据量相当的情况下：发现拆半插入排序 >= 单向冒泡排序性能 > 双向冒泡排序性能 > 插入排序 > 希尔排序 > 归并排序 > 选择排序 >= 快速排序1 > 快速排序2 > 大于普通冒泡性能。（产生时间具体取决于所使用的系统）

注意

快排实现方法1，虽然代码相对看起来简单，但是在数据量较大时，会出现溢出问题。

7、堆排序

思路

说到堆排序，首先需要了解一种数据结构——堆。堆是一种完全二叉树，这种结构通常可以用数组表示。在实际应用中，堆又可以分为小堆和大堆，两者的区别如下：

  • -max-heap property ：对于所有除了根节点（root）的节点 i，A[Parent(i)]≥A[i]

  • -min-heap property ：对于所有除了根节点（root）的节点 i，A[Parent(i)]≤A[i]

堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

  • 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列
  • 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列

实现

 created() {
    let array = [];
    for (let i = ; i < 10; i++) {
        let number = Math.floor(Math.random() * 10);
        array.push(number);
    }
    console.log(array);
    let res = this.quickSortOne(array, , array.length - 1);
    console.log(res);
},
methods: {
    /**
     * 堆排序
     */
    heapSort(nums) {
        this.buildHeap(nums);
        // 循环n-1次，每次循环后交换堆顶元素和堆底元素并重新调整堆结构
        for (let i = nums.length - 1; i > ; i--) {
            [nums[i], nums[]] = [nums[], nums[i]];
            this.adjustHeap(nums, , i);
            console.log(`${nums[i]}作为堆顶元素：`, nums);
        }
        return nums;
    },
    /**
     * 堆排序辅助方法
     */
    adjustHeap(nums, index, size) {
        // 交换后可能会破坏堆结构，需要循环使得每一个父节点都大于左右结点
        while (true) {
            let max = index;
            let left = index * 2 + 1; // 左节点
            let right = index * 2 + 2; // 右节点
            if (left < size && nums[max] < nums[left]) max = left;
            if (right < size && nums[max] < nums[right]) max = right;
            // 如果左右结点大于当前的结点则交换，并再循环一遍判断交换后的左右结点位置是否破坏了堆结构（比左右结点小了）
            if (index !== max) {
                [nums[index], nums[max]] = [nums[max], nums[index]];
                index = max;
            } else {
                break;
            }
        }
    },
    /**
     * 堆排序辅助方法
     */
    buildHeap(nums) {
        // 注意这里的头节点是从0开始的，所以后一个非叶子结点是 parseInt(nums.length/2)-1
        let start = parseInt(nums.length / 2) - 1;
        let size = nums.length;
        // 从后一个非叶子结点开始调整，直至堆顶。
        for (let i = start; i >= ; i--) {
            this.adjustHeap(nums, i, size);
        }
    }
}

性能比较

在大数量量和小数据量不用的情况下，堆排序的相对性能排序表动比较大。和他本身的特点有关，虽然堆排序在实践中不常用，经常被快速排序的效率打败，但堆排序的优点是与输入的数据无关，时间复杂度稳定在O(N*lgN),不像快排，坏的情况下时间复杂度为O(N2)。

8、计数排序

思路

以数组元素值为键，出现次数为值存进一个临时数组，后再遍历这个临时数组还原回原数组。因为 JavaScript 的数组下标是以字符串形式存储的，所以计数排序可以用来排列负数，但不可以排列小数。

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

实现

 created() {
    let array = [];
    for (let i = ; i < 10; i++) {
        let number = Math.floor(Math.random() * 10);
        array.push(number);
    }
    console.log(array);
    let res = this.countingSort(array);
    console.log(res);
},
methods: {
    /**
     * 计数排序
     */
    countingSort(nums) {
        let arr = [];
        let max = Math.max(...nums);
        let min = Math.min(...nums);
        // 装桶
        for (let i = , len = nums.length; i < len; i++) {
            let temp = nums[i];
            arr[temp] = arr[temp] + 1 || 1;
            console.log(`装桶键为${temp}-值为${arr[temp]}`, arr);
        }
        let index = ;
        // 还原原数组
        for (let i = min; i <= max; i++) {
            while (arr[i] > ) {
                nums[index++] = i;
                arr[i]--;
            }
        }
        return nums;
    }
}


性能比较

在数据量相当的情况下：发现拆半插入排序 >= 单向冒泡排序性能 > 双向冒泡排序性能 > 插入排序 > 计数排序 > 希尔排序 > 归并排序 > 选择排序 >= 快速排序1 > 快速排序2 > 大于普通冒泡性能。（产生时间具体取决于所使用的系统）

9、桶排序

思路

取 n 个桶，根据数组的大值和小值确认每个桶存放的数的区间，将数组元素插入到相应的桶里，后再合并各个桶。

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。 为了使桶排序更加高效，我们需要做到这两点：

  • 在额外空间充足的情况下，尽量增大桶的数量。
  • 使用的映射函数能够将输入的N个数据均匀的分配到K个桶中。

什么时候快（Best Cases）： 当输入的数据可以均匀的分配到每一个桶中

什么时候慢（Worst Cases）： 当输入的数据被分配到了同一个桶中

实现

 created() {
    let array = [];
    for (let i = ; i < 10; i++) {
        let number = Math.floor(Math.random() * 10);
        array.push(number);
    }
    console.log(array);
    let res = this.bucketSort(array);
    console.log(res);
},
methods: {
    /**
     * 桶排序
     */
    bucketSort(nums) {
        // 桶的个数，只要是正数即可
        let num = 5;
        let max = Math.max(...nums);
        let min = Math.min(...nums);
        // 计算每个桶存放的数值范围，至少为1，
        let range = Math.ceil((max - min) / num) || 1;
        // 创建二维数组，维表示第几个桶，第二维表示该桶里存放的数
        let arr = Array.from(Array(num)).map(() => Array().fill());
        nums.forEach(val => {
            // 计算元素应该分布在哪个桶
            let index = parseInt((val - min) / range);
            // 防止index越界，例如当[5,1,1,2,0,0]时index会出现5
            index = index >= num ? num - 1 : index;
            let temp = arr[index];
            // 插入排序，将元素有序插入到桶中
            let j = temp.length - 1;
            while (j >=  && val < temp[j]) {
                temp[j + 1] = temp[j];
                j--;
            }
            temp[j + 1] = val;
            console.log(temp);
        });
        // 修改回原数组
        let res = [].concat.apply([], arr);
        nums.forEach((val, i) => {
            nums[i] = res[i];
        });
        return nums;
    }
}


性能比较

在数据量相当的情况下：发现拆半插入排序 >= 单向冒泡排序性能 > 双向冒泡排序性能 > 插入排序 > 计数排序 > 桶排序 > 希尔排序 > 归并排序 > 选择排序 >= 快速排序1 > 快速排序2 > 大于普通冒泡性能。（产生时间具体取决于所使用的系统）

10 、基数排序

思路

使用十个桶 0-9，把每个数从低位到高位根据位数放到相应的桶里，以此循环大值的位数次。但只能排列正整数，因为遇到负号和小数点无法进行比较。

基数排序有两种方法：

  • MSD 从高位开始进行排序
  • LSD 从低位开始进行排序

基数排序 vs 计数排序 vs 桶排序：

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

  • 基数排序：根据键值的每位数字来分配桶
  • 计数排序：每个桶只存储单一键值
  • 桶排序：每个桶存储一定范围的数值

实现

 created() {
    let array = [];
    for (let i = ; i < 10; i++) {
        let number = Math.floor(Math.random() * 10);
        array.push(number);
    }
    console.log(array);
    let res = this.radixSort(array);
    console.log(res);
},
methods: {
    /**
     * 基数排序
     */
    radixSort(nums) {
        // 计算位数
        function getDigits(n) {
            let sum = ;
            while (n) {
                sum++;
                n = parseInt(n / 10);
            }
            return sum;
        }
        // 维表示位数即0-9，第二维表示里面存放的值
        let arr = Array.from(Array(10)).map(() => Array());
        let max = Math.max(...nums);
        let maxDigits = getDigits(max);
        for (let i = , len = nums.length; i < len; i++) {
            // 用0把每一个数都填充成相同的位数
            nums[i] = (nums[i] + '').padStart(maxDigits, );
            // 先根据个位数把每一个数放到相应的桶里
            let temp = nums[i][nums[i].length - 1];
            arr[temp].push(nums[i]);
        }
        console.table(arr);
        // 循环判断每个位数
        for (let i = maxDigits - 2; i >= ; i--) {
            // 循环每一个桶
            for (let j = ; j <= 9; j++) {
                let temp = arr[j]
                let len = temp.length;
                // 根据当前的位数i把桶里的数放到相应的桶里
                while (len--) {
                    let str = temp[];
                    temp.shift();
                    arr[str[i]].push(str);
                }
            }
        }
        // 修改回原数组
        let res = [].concat.apply([], arr);
        nums.forEach((val, index) => {
            nums[index] = +res[index];
        });
        return nums;
    }
}

性能比较

在数据量相当的情况下：发现拆半插入排序 >= 单向冒泡排序性能 > 双向冒泡排序性能 > 插入排序 > 计数排序 > 桶排序 > 希尔排序 > 基数排序 >归并排序 > 选择排序 >= 快速排序1 > 快速排序2 > 大于普通冒泡性能。（产生时间具体取决于所使用的系统）


作者：蜗牛的北极星之旅

链接：https://juejin.im/post/5e1182def265da5d691039ab
来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。  

上一篇：微服务SpringBoot－整合kafka和storm
下一篇：管理员指南-备份与恢复
分享好友

分享这个小栈给你的朋友们，一起进步吧。

测试转移内容
创建时间：2020-03-20 17:37:37
测试转移内容
展开
订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅：虚拟交易，一经交易不退款；若特殊情况，可3日内客服咨询

• 专区发布评论属默认订阅所评论专区（除付费小栈外）

栈主、嘉宾

查看更多
  • 没心情吃饭
    栈主
戳我，来吐槽～

北京盛拓优讯信息技术有限公司. 版权所有  京ICP备16024965号-8  北京市公安局海淀分局网监中心备案编号：11010802021510  未成年人举报专区

违法不良信息举报电话:18101376593   广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员