美文网首页
排序算法

排序算法

作者: _旁观者_ | 来源:发表于2018-11-16 17:57 被阅读0次

冒泡

从前向后遍历,如果前面的元素大于后面的,两者互换位置

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Document</title>
</head>
<body>
    <script>
        var arr = [2,43,4545,22,4,567,56,76]
        function bubble (arr) { 
            for (let i = 0; i < arr.length - 1; i++) {
                for (let j = i+1; j < arr.length; j++) {
                    if(arr[j]< arr[i]) {
                        let tem = arr[i]
                        arr[i] = arr[j]
                        arr[j] = tem
                    }
                }
            }
            return arr
        }
        console.log(bubble(arr)) 
    </script>
</body>
</html>

选择排序

从未排序的数组中遍历出最小的元素,和开始位置的元素互换位置
继续从剩下的元素中遍历出做小的,放在已排序的元素后面

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Document</title>
</head>
<body>
    <script>
        var arr = [2,43,4545,22,4,567,56,76]
        function selectSort (arr) {
            let min = 0
            for (let i = 0; i < arr.length; i++) {
                min = i
                for (let j =i + 1; j < arr.length; j++) {
                    if (arr[j] < arr[min]) {
                        min = j
                    }
                }
                let tem = arr[i]
                arr[i] = arr[min]
                arr[min] = tem
            }
            return arr
        }
        console.log(selectSort(arr)) 
    </script>
</body>
</html>

归并排序

mergeSort用于分割数组,直到分割成单个元素,然后会调用merge
merge作用 排序已经分割的元素

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Document</title>
</head>
<body>
    <script>
        // 递归调用mergeSort函数,
        // 递归至数组长度为1时,合并leftArr rightArr数组
        var arr = [2,43,4545,22,4,567,56,76]
        function mergeSort (arr) {
            let length = arr.length
            if (length < 2) {
                return arr
            }
            let middle = Math.floor(length/2)
            let leftArr = arr.slice(0, middle)
            let rightArr = arr.slice(middle)
            return merge(mergeSort(leftArr), mergeSort(rightArr))
        }

        function merge (leftArr, rightArr) {
            let result = []
            while (leftArr.length && rightArr.length) {
                if (leftArr[0] <= rightArr[0]) {
                    result.push(leftArr.shift())
                }else {
                    result.push(rightArr.shift())
                }
            }
            while (leftArr.length) {
                result.push(leftArr.shift())
            }
            while (rightArr.length) {
                result.push(rightArr.shift())
            }
            return result
        }
        console.log(mergeSort(arr))
    </script>
</body>
</html>

插入排序

当前元素current如果小于前一位元素,前一位元素 的索引加1
直到 当前元素current大于正在比较的元素时,跳出while循环
当前元素current位置更改为正在比较的元素

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Document</title>
</head>
<body>
    <script>
        var arr = [2,43,4545,22,4,567,56,76]
        function insert (arr) {
            let current, preIndex
            for (let  i = 1; i < arr.length; i++) {
                current = arr[i]
                preIndex = i - 1
                // 首先缓存当前的current 和 index,在while循环中会发生变化
                // 循环直到当前的数组元素大于current时候停止,再赋值与index+1位的元素
                while (preIndex >= 0 && arr[preIndex] > current) {
                    arr[preIndex + 1] = arr[preIndex]
                    preIndex--
                }
                arr[preIndex + 1] = current
            }
            return arr
        }
        console.log(insert(arr)) 
    </script>
</body>
</html>

希尔排序

选择一个增量序列,按增量序列对序列进行排序

每趟排序的方法为插入排序,根据对应的增量 ,分为多次排序

直到趟数为1时,完成排序

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Document</title>
</head>
<body>
    <script>
        // 参考资料 https://blog.csdn.net/weixin_37818081/article/details/79202115
        // 希尔排序 (多个小的组别插入排序逐渐归为一个组别的插入方法)
        var arr = [22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]
        function shellSort(arr) {
            var len = arr.length,
                temp,
                gap = 1;
            while(gap < len/3) { //动态定义间隔序列
                gap =gap*3+1; 
            }
            // for 循环 顺序 1,gap ==>  2,gap > 0  ==>  3,console.log('for1', gap) ==>  4,gap = Math.floor(gap/3) ==>  2,gap > 0 
            for (gap; gap > 0; gap = Math.floor(gap/3)) {
                for (var i = gap; i < len; i++) {
                    temp = arr[i];
                    for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) { // 插入排序
                        arr[j+gap] = arr[j];
                    }
                    arr[j+gap] = temp;
                }
            }
            return arr;
        }
        console.log(shellSort(arr)) 
    </script>
</body>
</html>

相关文章

  • java实现快速排序、归并排序、希尔排序、基数排序算法...

    快速排序算法 归并排序算法 希尔排序算法 基数排序算法

  • web开发需要知道的几个算法

    算法分类 快速排序算法 深度优先算法 广度优先算法 堆排序算法 归并排序算法

  • 算法学习(1)-排序算法

    八大排序算法九大排序算法再总结[经典排序算法][集锦][直观学习排序算法] 视觉直观感受若干常用排序算法 快速排序...

  • 经典排序算法总结

    经典排序算法集锦 冒泡法 排序算法入门之冒泡排序 排序算法入门之冒泡排序优化

  • 前端算法学习-第一篇

    冒泡排序算法 冒泡排序算法是最慢的排序算法之一,也是最容易实现的排序算法。之所以叫冒泡排序是因为使用这种算法排序时...

  • 七大排序算法之冒泡排序

    七大排序算法之冒泡排序 @(算法笔记)[排序算法, 冒泡排序, C++实现] 冒泡排序介绍 冒泡排序是七大排序算法...

  • 算法-选择排序

    算 法:选择排序算法时间复杂度: 选择排序算法概述 选择排序伪代码 选择排序实现 选择排序算法概述 排序算法有许...

  • 浅谈排序算法

    排序算法有很多种,今天先谈谈一些简单的排序算法。包括桶排序、冒泡排序和快速排序算法。后期总结各种排序算法。 桶排序...

  • 线性排序

    桶排序、计数排序、基数排序 一、线性排序算法介绍 1.线性排序算法包括桶排序、计数排序、基数排序。2.线性排序算法...

  • 算法4:插入排序和选择排序算法的比较

    排序算法列表电梯: 选择排序算法:详见 《算法4》2.1 - 选择排序算法(Selection Sort), Py...

网友评论

      本文标题:排序算法

      本文链接:https://www.haomeiwen.com/subject/iculfqtx.html