有关算法排序

常见排序

一、比较排序

sort 、

冒泡 - 每个元素遍历到，逐个替换位置上冒（01 - 12 - 23 ... length -1 ，length -2 ...） - 效率不变

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Document</title>
</head>

<body>

    <script>
        var arrIn = [0,100,1, 2, 3, 4, 7, 6, 5, 4,-1]
        var arrOut = sortArr(arrIn)

        // sort 自带排序
        function sortArr(arr) {
            arr = Object.assign([], arr)
            return arr.sort((a,b)=>a-b)
        }

        // 冒泡排序：  temp 中间变量 
        // function sortArr(arr) {
        //     arr = Object.assign([], arr)
        //     var temp
        //     for(var i=0,j=arr.length;i<j;i++){
        //         for(var m=0;m<j-i-1;m++){
        //             if(arr[m]>arr[m+1]){
        //                 temp = arr[m]
        //                 arr[m] = arr[m +1]
        //                 arr[m +1] = temp 
        //             }
        //         }
        //     }
        //     return arr
        // }

        // 冒泡排序： 无中间变量
        // function sortArr(arr) {
        //     arr = Object.assign([], arr) 
        //     for(var i=0,j=arr.length;i<j;i++){
        //         for(var m=0;m<j-i-1;m++){
        //             if(arr[m]>arr[m+1]){                        
        //                 arr[m] = arr[m] + arr[m + 1]
        //                 arr[m + 1] = arr[m] - arr[m + 1]
        //                 arr[m] = arr[m] -  arr[m + 1]
        //             }
        //         }
        //     }
        //     return arr
        // }

        console.log(arrIn)
        console.log(arrOut)


    </script>

</body>

</html>

View Code

选择排序 - 筛选出最大值后置（每个元素遍历比较，选出最大值，最大值与出现最大值元素对调），或者最小值前置 - 效率不变

// 选择排序: 取最大值及其索引与尾部替换
        console.time('start')
        var count = 0;
        var arrIn = [0, 100, 1, 2, 3, 4, 7, 6, 5, 4, -1]
        var arrOut = sortArr(arrIn)

        function sortArr(arr) {
            arr = Object.assign([], arr)

            var max = arr[0],
                index = 0;
            for (var i = 0, j = arr.length; i < j; i++) {
                for (var m = 0; m < j - 1 - i; m++) {
                    if (arr[m] > max) {
                        max = arr[m]
                        index = m
                    }
                    count++
                }
                max = arr[j - 1 - i]
                arr[j - 1 - i] = arr[index]
                arr[index] = max

            }
            console.log(count)
            console.timeEnd('start')
            return arr
        }

        console.log(arrIn)
        console.log(arrOut)

View Code

插入排序 - 左一视为起点，往后逐个高位置元素向低位置元素靠近作比较(需要排序则高位索引元素填入前一位，以此类推) - 适合修正顺序(效率高)

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Document</title>
</head>

<body>

    <script>
        // 插入排序 : 左一视为起点，往后 逐个高位置元素向低位置元素靠近作比较(需要排序则高位索引元素填入前一位，以此类推)  -  适合修正顺序(效率高)
        console.time('start')
        var arrIn = [0, 100, 1, 2, 3, 4, 7, 6, 5, 4, -1]
        var arrOut = sortArr(arrIn)
        console.timeEnd('start')

        function sortArr(arr) {
            arr = Object.assign([], arr)

            var preIndex, current;
            for (var i = 1, j = arr.length; i < j; i++) {
                // preIndex = i - 1
                // current = arr[i]
                // while (preIndex >= 0 && arr[preIndex] > current) {
                //     arr[preIndex + 1] = arr[preIndex]
                //     preIndex--
                // }
                for (preIndex = i - 1, current = arr[i]; preIndex >= 0 && arr[preIndex] > current; preIndex--) {
                    arr[preIndex + 1] = arr[preIndex]                
                }
                arr[preIndex + 1] = current
            }

            return arr;
        }

        console.log(arrIn)
        console.log(arrOut)
    </script>

</body>

</html>

View Code

二、非比较排序

计数排序

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Document</title>
</head>

<body>

    <script>
        console.time('start')
        var arrIn = [0, 100, 1, 2, 3, 4, 7, 6, 5, 4, 1]
        var arrOut = counting_sort(arrIn)
        console.timeEnd('start')

        // 计数排序 -    整数  数据集中
        function counting_sort(A) { 
            const max = Math.max(...A)
            let B = Array.from({ length: max + 1 }).fill(0); 
            let C = [];
            A.forEach((_, i) => B[A[i]]++)
            for (let i = 1; i < B.length; i++) {
                B[i] = B[i - 1] + B[i] 
            }
            for (let i = 0; i < A.length; i++) {
                const p = B[A[i]] - 1; 
                B[A[i]]-- 
                C[p] = A[i]
            }
            return C
        }

        console.log(arrIn)
        console.log(arrOut)
    </script>

</body>

</html>

View Code

javascript常用数组算法总结

JS的十大经典算法排序

javascript算法题：求任意一个1-9位不重复的N位数在该组合中的大小排列序号

有关算法 排序

有关算法排序