排序算法

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

java实现快速排序、归并排序、希尔排序、基数排序算法...
web开发需要知道的几个算法
算法学习(1)-排序算法
经典排序算法总结
前端算法学习-第一篇
七大排序算法之冒泡排序
算法-选择排序
浅谈排序算法
线性排序
算法4：插入排序和选择排序算法的比较

冒泡

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

<!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>