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

痛定思痛。 2023-02-14 15:55 53阅读 0赞

### 写在前面 ###

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MTE3MDI0_size_16_color_FFFFFF_t_70][]

### 冒泡排序简介 ###

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

### 冒泡排序实现过程 ###

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

### 冒泡排序的动图演示 ###

![20200603210334654.png][]

### 冒泡排序代码实现 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MTE3MDI0_size_16_color_FFFFFF_t_70 1][]

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

### 冒泡排序应用场景 ###

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

### 冒泡排序的算法口诀 ###

*  外层循环从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);

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MTE3MDI0_size_16_color_FFFFFF_t_70 2][]

**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);

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MTE3MDI0_size_16_color_FFFFFF_t_70 3][]

### 冒泡排序优缺点： ###

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MTE3MDI0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200603210246225.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MTE3MDI0,size_16,color_FFFFFF,t_70
[20200603210334654.png]: https://img-blog.csdnimg.cn/20200603210334654.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MTE3MDI0_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200603210430760.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MTE3MDI0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MTE3MDI0_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200603210543106.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MTE3MDI0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MTE3MDI0_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200603210651777.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MTE3MDI0,size_16,color_FFFFFF,t_70