排序算法---冒泡排序

1. 原理

对数组进行遍历,每次对相邻的两个元素进行比较,如果大的在前面,则交换两个元素的位置,完成一趟遍历后,数组中最大的数值到了数组的末尾。再对前面n-1个数值进行相同的遍历。一共完成n-1趟遍历就实现了排序。

 

1. 进行第一趟遍历: 

 

从上图中可以看出 一共比较了5次, 也就是 n-1

下面的每趟和第一趟的算法流程相同:

第二趟:2,3,5,1,7,10    --->  比较了4次   (n-2)

第三趟:2,3,1,5,7,10    --->  比较了3次   (n-3)

第四趟:2,1,3,5,7,10    --->  比较了2次   (n-4)

第五趟:1,2,3,5,7,10    --->  比较了1次   (n-5)

总共经过5趟,完成排序

2. 代码实现

这边需要两个for循环, 外层for循环控制共经过多少趟, 内层for循环控制每一趟比较的次数

        for (let i = 0; i < arr.length-1; i++) {
            for(let j = 0; j < arr.length-i-1; j++) {
                if (arr[j] > arr[j+1]) {
                    let t = arr[j]
                    arr[j] = arr[j+1]
                    arr[j+1] = t
                }
            }
        }

3. 代码优化

如果一趟走完,没有数据进行交换,说明已经排好序了,不需要进行遍历了,则可以引入标记flag.

        for (let i = 0; i < arr.length-1; i++) {
            let flag = 0  
            for(let j = 0; j < arr.length-i-1; j++) {
                if (arr[j] > arr[j+1]) {
                    let t = arr[j]
                    arr[j] = arr[j+1]
                    arr[j+1] = t
                    flag = 1   //发生数据交换,置flag为1
                }
            }
            if (flag == 0) {   //若flag为0,则没有发生交换,跳出循环
                break
            }
        }

4. 复杂度分析

1. 时间复杂度:找出执行次数最多的语句即可

if (arr[j] > arr[j+1]) {}

即这个if 判断语句执行的次数最多

基于上述每一趟比较的次数,可以得到总的比较次数,就是这个判断语句执行的次数

=>  (n-1)+(n-2)+(n-3)+...+1 = [n(n-1)]/2  = n^2/2 - n/2 + 1/2

=> 去掉系数、低阶和常量  

=> 则时间复杂度为  O(n^2)

2. 空间复杂度: 冒泡排序中并没有用到额外的空间,所以空间复杂度为 O(1)

3. 冒泡排序是稳定的排序算法:因为当两个元素相同的话,是不会交换位置的 

相关推荐

  1. 排序算法——冒泡排序

    2023-12-13 13:36:01       62 阅读
  2. 排序算法冒泡排序

    2023-12-13 13:36:01       44 阅读
  3. 排序算法-冒泡排序

    2023-12-13 13:36:01       36 阅读
  4. 排序算法_冒泡排序

    2023-12-13 13:36:01       24 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2023-12-13 13:36:01       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2023-12-13 13:36:01       102 阅读
  3. 在Django里面运行非项目文件

    2023-12-13 13:36:01       83 阅读
  4. Python语言-面向对象

    2023-12-13 13:36:01       92 阅读

热门阅读

  1. 如何定制专属app:定制app教程

    2023-12-13 13:36:01       62 阅读
  2. PHP是什么?

    2023-12-13 13:36:01       62 阅读
  3. C语言猜数字游戏

    2023-12-13 13:36:01       59 阅读
  4. 设计模式(1)--面向对象的设计原则

    2023-12-13 13:36:01       59 阅读
  5. 《C++新经典设计模式》之第4章 策略模式

    2023-12-13 13:36:01       54 阅读
  6. 【每日一题】力扣:修车的最少时间

    2023-12-13 13:36:01       60 阅读