美文网首页
JavaScript数组的常用算法

JavaScript数组的常用算法

作者: 小五丶_ | 来源:发表于2019-12-05 21:08 被阅读0次

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    欢迎大家去我的个人技术博客看看,点赞收藏注册的都是好人哦~

    https://xiaowu.xyz

    一、数组的常见算法

    由于算法的性能要从时间复杂度和空间复杂度两个方面考虑,所以这里不做性能的研究,仅仅为了理解

    1、冒泡排序:

      假设有数组[54, 68, 46, 75, 36, 20, 65, 11, 79, 45]

    var list = [54, 68, 46, 75, 36, 20, 65, 11, 79, 45];   // 要排序的数组

       需求:从小到大排列数组

    因为我们要把大的数放在后面,所以我们每个数都和右边的数比较,如果左边的数大于右边的数,就将两个数换位置

       循环一圈后,就能得到最大的值,放在最右边,每次循环一圈,就能得到相对最大的值放在最右边

        

    第一轮  就得到最大值  j=0

        54 68  [54, 68, 46, 75, 36, 20, 65, 11, 79, 45]

        68 46  [54, 46, 68, 75, 36, 20, 65, 11, 79, 45]

        68 75  [54, 46, 68, 75, 36, 20, 65, 11, 79, 45]

        75 36  [54, 46, 68, 36, 75, 20, 65, 11, 79, 45]

        75 20  [54, 46, 68, 36, 20, 75, 65, 11, 79, 45]

        75 65  [54, 46, 68, 36, 20, 65, 75, 11, 79, 45]

        75 11  [54, 46, 68, 36, 20, 65, 11, 75, 79, 45]

        75 79  [54, 46, 68, 36, 20, 65, 11, 75, 79, 45]

        75 45  [54, 46, 68, 36, 20, 65, 11, 75, 45, 79]

        for (var i = 0; i < list.length - 1; i++) {  //第一次循环

            if (list[i] > list[i + 1]) {  // 68 46   //如果左边的值大于右边成立

                var temp = list[i];    // 设置一个临时变量,将左边的值先存起来

                list[i] = list[i + 1];     // 将右边的值赋给左边

                list[i + 1] = temp;    //  将临时变量中存的最初的左边的值给右边   完成一次交换位置

            }

        }

        console.log(list);

        

    第二轮  得到  第二大的值  j=1

        54 46  [46, 54, 68, 36, 20, 65, 11, 75, 45, 79]

        54 68  [46, 54, 68, 36, 20, 65, 11, 75, 45, 79]

        68 36  [46, 54, 36, 68, 20, 65, 11, 75, 45, 79]

        68 20  [46, 54, 36, 20, 68, 65, 11, 75, 45, 79]

        68 65  [46, 54, 36, 20, 65, 68, 11, 75, 45, 79]

        68 11  [46, 54, 36, 20, 65, 11, 68, 75, 45, 79]

        68 75  [46, 54, 36, 20, 65, 11, 68, 75, 45, 79]

        75 45  [46, 54, 36, 20, 65, 11, 68, 45, 75, 79]

        75 79  [46, 54, 36, 20, 65, 11, 68, 45, 75, 79]  //多余一次   由于第一次已经取到最大的值了,所以最后一次不用比较

        for (var i = 0; i < list.length - 1; i++) {   //第二次循环

            if (list[i] > list[i + 1]) {  

                var temp = list[i];     // 设置一个临时变量,将左边的值先存起来

                list[i] = list[i + 1];       // 将右边的值赋给左边

                list[i + 1] = temp;      //  将临时变量中存的最初的左边的值给右边   完成一次交换位置

            }

        }

        console.log(list);

     

    第三轮  得到 第三大的值  j=2

        45 54  [46, 54, 36, 20, 65, 11, 68, 45, 75, 79]

        54 36  [46, 36, 54, 20, 65, 11, 68, 45, 75, 79]

        54 20  [46, 36, 20, 54, 65, 11, 68, 45, 75, 79]

        54 65  [46, 36, 20, 54, 65, 11, 68, 45, 75, 79]

        65 11  [46, 36, 20, 54, 11, 65, 68, 45, 75, 79]

        65 68  [46, 36, 20, 54, 11, 65, 68, 45, 75, 79]

        65 45  [46, 36, 20, 54, 11, 65, 45, 68, 75, 79]

        65 75  [46, 36, 20, 54, 11, 65, 45, 68, 75, 79]  //多余

        75 79  [46, 36, 20, 54, 11, 65, 45, 68, 75, 79]  //多余      //多余两次   由于前两次已经取到最大的值和第二大的值了,所以最后两次不用比较

        ......

    所以完整的冒泡排序

    var list = [54, 68, 46, 75, 36, 20, 65, 11, 79, 45];   // 要排序的数组

    for (var j = 0; j < list.length - 1; j++) {   //外层决定执行多少轮  因为最后一个元素没有下一个元素和他比较,所以 j要小于list.length - 1

            for (var i = 0; i < list.length - 1 - j; i++) {    // 内层从最左边开始比较,-j是为了性能优化,将多余的比较减掉

                if (list[i] > list[i + 1]) {  

                    var temp = list[i];

                    list[i] = list[i + 1];

                    list[i + 1] = temp;

                }

            }

        }

        console.log(list);

    递归写法:

        function maoPao(list, j) {

            for (var i = 0; i < list.length - 1; i++) {

                if (list[i] > list[i + 1]) {  // 68 46

                    var temp = list[i];

                    list[i] = list[i + 1];

                    list[i + 1] = temp;

                }

            }

            console.log(list);

            if (j == 1) {

                return list;

            }

            return maoPao(list, j - 1);

        }

        var list = [54, 68, 46, 75, 36, 20, 65, 11, 79, 45];   // 要排序的数组

        maoPao(list, list.length); //10 

    // 这里的能用循环还是最好用循环,这里只是为了练习递归

    2、选择排序:

    假设我们有数组[54, 68, 46, 75, 36, 20, 65, 11, 79, 45],我们要求从小到大的排列

    var list = [54, 68, 46, 75, 36, 20, 65, 11, 79, 45];    

    选择排序和冒泡排序不同,冒泡排序每轮循环都要换很多次位置,而选择排序每次循环只换一次位置。

    从下标0开始,与其后所有元素相比较,找到后面最小的值,然后与其交换位置

    然后再从下标1开始找,找到后面最小的值,然后与其交换位置

      var list = [54, 68, 46, 75, 36, 20, 65, 11, 79, 45];

        for (var j = 0; j < list.length - 1; j++) {//0

            var min = list[j];      // 把每次循环的次数对应的那个值保存下来

            var minIndex = j;  //把每次循环的次数对应的那个值对应的下标也保存下来

            for (var i = j + 1; i < list.length; i++) {

                if (min > list[i]) {     

                    min = list[i];

                    minIndex = i;

                }

            }

            // 内层for循环执行结束后,就一定能得到后面最小的那个值的下标和值

            // 将当前的值和后面最小的值交换顺序

            var temp = list[j];

            list[j] = list[minIndex];

            list[minIndex] = temp;

        }

    console.log(list);

    3、快速排序(二分排序):

    这里利用递归来实现快速排序

    ① 选取待排序数组中其中一个数作为基数(这里选择了位置偏中间的数Math.floor(list.length / 2)),使midIndex等于基数的下标,将基数从数组中裁切下来,建立两个空数组,left数组和right数组

    ② 将数组中比基数小的数放到left数组中,比基数大的数放到rigth数组中。

    ③ 将基数左边的数组作为待排序数组,重复①步骤。

    ④ 将基数右边的数组作为待排序数组,重复①步骤。

    ⑤ 直到left和right的长度都小于2(数组长度为1或0),代表数组已经划分为最小单位(待排序数组长度小于等于1),即该部分排序完毕,无需继续分割数组。

        function quickSort(list) {

            if (list.length < 2) {

                return list;

            }

            var midIndex = Math.floor(list.length / 2);

            var mid = list.splice(midIndex, 1)[0];   //返回的是数组

            var left = [];

            var right = [];

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

                if (list[i] < mid) {

                    left.push(list[i]);

                } else {

                    right.push(list[i]);

                }

            }

            // console.log(left, mid, right);

            return quickSort(left).concat(mid, quickSort(right));

        }

    相关文章

      网友评论

          本文标题:JavaScript数组的常用算法

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