【JS排序算法】JavaScript实现冒泡排序

JavaScript

【JS排序算法】JavaScript实现冒泡排序

2021-01-04 14:24发布生成海报

站内文章 / JavaScript

954 0

写在前面

本文是学习"ben大叔"大佬的相关文章所总结而成。

作为一名前端，你可以不了解复杂的一些算法实现，但是关于排序算法你可要了解和掌握哦，比如以下这几种：

冒泡排序简介

冒泡排序作为排序算法家族中的成员来说，相当于编程语言学习中的"Hello World"，因为它是最简单的排序算法。冒泡排序会重复走访待排序序列，每次会比较序列中的相邻两个元素，如果这两个元素的顺序错误，就将它俩位置互换，依次重复进行此操作，直到待排序序列中没有要进行交换的操作为止，就意味着已经完成了排序。由于冒泡排序中每次重复比较两个元素、交换位置的过程中，值较小的数据往往会被排到数列的前面，值越大的数据会往后排，这就像是水里的水泡一样往上冒，所以它的名字由此而来。

冒泡排序实现过程

比较相邻的两个元素，如果第一个比第二个大，就交换它们位置；
对待排序序列中的每一对相邻元素做上面重复操作，从最开始的一对到最后的一对，这样每次一轮比较结束后，结尾的元素是最大的数；
重复以上两个步骤，直到排序完成。

冒泡排序的动图演示

冒泡排序代码实现

       
        function bubbleSort(arr) {
            var len = arr.length;
            for(var i = 0; i < len - 1; i++) {
                for(var j = 0; j < len - 1 - i; j++) {
                    if(arr[j + 1] < arr[j]) {
                        var middle = arr[j+1];
                        arr[j+1] = arr[j];
                        arr[j] = middle;
                    }
                }
            }
            return arr;
        };
 
        var defaultArr = [3, 5, 32, 15, 7, 26, 10, 55, 45, 12, 28, 88, 18];     //待排序序列
        var resultArr = bubbleSort(defaultArr);
        console.table(resultArr);

可以通过上面代码看到，冒泡排序的实现原理就是双重循环，如果后一个数小于前一个数，就替换它们的位置，这样重复进行直至循环结束。它每次比较时都将数值较大的数据放在结尾，所以将我们的数组实际上是从小到大进行了排序，同理，要想实现从大到小排序，我们只需要将条件判断语句中的小于号改成大于号即可。

冒泡排序应用场景

比较适用于小数据量的排序(从小到大或者从大到小)，因为原理简单，并且数据量大的话循环次数极多，降低性能；
适用于教学，因为原理简单。

冒泡排序的算法口诀

外层循环从0到N-1； (控制比较的轮数，N为元素个数)
内层循环从0到N-1-i; (控制每一轮比较次数)
两两比较作交换。

冒泡排序的优化

我们上述实现的仅仅是冒泡排序的基础版，也就是实现了一个能用的冒泡排序算法而已，如果数据量较大的话，它的性能是极低的，所以接下来我们优化一下(虽然并没有实质性的作用，但还是介绍下)。

冒泡排序的优化大家记住一点即可：冒泡排序优化其实就是减少比较次数，本质上不会有较大的性能提升。

1、添加flag的方式

     
        //flag版优化
        function bubbleSort_flag(arr) {
            var len = arr.length;
            var flag = false;     //添加一个flag，用于标识原序列是否是一个有序序列
 
            if(len <= 1) {     //如果仅仅有一个元素直接返回
                return arr;
            }
 
            for(var i = 0; i < len - 1; i++) {
                for(var j = 0; j < len - 1 - i; j++) {
                    if(arr[j + 1] < arr[j]) {
                        var middle = arr[j+1];
                        arr[j+1] = arr[j];
                        arr[j] = middle;
                        flag = true;
                    }
                }
 
                if(!flag) break;    //如果一次都没有发生数据交换就返回原序列，因为已经是一个有序序列
            }
            return arr;
        }
 
        var defaultArr = [3, 5, 32, 15, 7, 26, 10, 55, 45, 12, 28, 88, 18];
        var resultArr = bubbleSort_flag(defaultArr);
        console.table(resultArr);

2、双向冒泡排序(鸡尾酒排序)

基础版的冒泡排序是从一端开始，依次循环比较相邻元素实现的，为了减少比较次数，略微的提高一下性能，我们可以选择让排序从两头开始，即遵循"较大气泡从左往右移动，较小气泡从右往左移动"的方式来实现，如下：

      
        //双向冒泡排序
        function bubbleSort_twoway(arr) {
            var len = arr.length;    //依次将最大的数放置到数组末尾，将第二大的数放到倒数第二位...
            var flag = false;
            for(var i = 0; i < len/2; i++) {
                flag = false;
                for(var j = i; j < len - 1 - i; j++) {   //从前往后,比较相邻两个数,把大的放在后边.之前已放置成功的可以不再参与比较
                    if(arr[j] > arr[j + 1]) {
                        var middle = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = middle;
                        flag =true;
                    }
                }
                if(!flag){
                    break;
                }
 
                for(var j = len - 1 - i; j > i; j--){
                    if(arr[j] < arr[j - 1]) {
                        var middle = arr[j];
                        arr[j] = arr[j-1];
                        arr[j-1] = middle;
                        flag = true;
                    }
                }
                if(!flag){
                    break;
                }
            }
            return arr;
        }
 
        var defaultArr = [3, 5, 32, 15, 7, 26, 10, 55, 45, 12, 28, 88, 18];
        var resultArr = bubbleSort_twoway(defaultArr);
        console.table(resultArr);

冒泡排序优缺点：

优点：简单、空间复杂度低、稳定
缺点：时间复杂度高、效率低