js两个数组排列组合

JavaScript09

js两个数组排列组合,第1张

<html>

<head>

    <title>js两个数组排列组合</title>

    <script type="text/javascript">

    var a = ["A","B","C"]

    var b = ["1", "2","3"]

    window.onload = function () {

        var a1 = new objPL(a)//计算数组a的排列组合

        var b1 = new objPL(b)//计算数组b的排列组合

        var str = ""

        var n = 0

        //a1和b1的排列组合个数就是两者相乘（双层循环）

        for (var i = 0 i < a1.length i++) {

            for (var j = 0 j < b1.length j++) {

                str += a1[i] + b1[j] + " "

                n++

            }

            str += "<br/>"

        }

        document.write("共" + n + "个<br/>")

        document.write(str)

    }

    //取数组的排列组合

    function objPL(arr) {

        this.a = arr

        this.r = []

        this.n = 0

        //从M个数里面取N个(递归)

        this.mGetN = function (curIndex, num, curSelect) {

            if (num == 0) {

                this.r[this.n++] = curSelect return

            }

            if (this.a.length - curIndex < num) return

            this.mGetN(curIndex + 1, num - 1, curSelect + this.a[curIndex])

            this.mGetN(curIndex + 1, num, curSelect)

        }

        for (var i = 1 i <= this.a.length i++) {

            this.mGetN(0, i, "")

        }

        return this.r

    }

    </script>

</head>

<body></body>

</html>

["A","B","C"]与["1","2","3"]组合的结果：

一、 冒泡排序

平均复杂度：o(n^2)空间复杂度：o(1)稳定性：稳定

步骤： 1、比较相邻的元素。如果第一个比第二个大，就交换他们两个；

2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样，最后的元素应该会是最大的数；

3、针对所有的元素重复以上的步骤，除了最后一个；

4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

二、选择排序

平均复杂度：o(n^2)空间复杂度：o(1)稳定性：不稳定

步骤： 1、每一次循环，找到最小的那个数，并用变量记住它的索引

2、然后将最小值放在它该在的位置上

3、持续对越来越少的元素重复上面的步骤

三、插入排序

平均复杂度：o(n^2)空间复杂度：o(1)稳定性：稳定

（1）直接插入排序：将第一个数和第二个数排序，然后构成一个有序序列；将第三个数插入进去，构成一个新的有序序列；对第四个数、第五个数......直到最后一个数，重复第二步

（2）二分插入排序：将寻找每个数插入位置的方法改为折半比较即可

四、Shell排序（插入排序的一种，又称为缩小增量排序）

平均复杂度：o(nlogn)空间复杂度：o(1)稳定性：不稳定

步骤：把数组按下标的一定增量分组，然后对每组使用直接插入排序

想学习更多前端开发的知识，就来北京尚学堂！