算法基础学习2——冒泡排序

简介: 要比较的每一对元素是相邻的,从下标为0开始,到最后一个元素,如果下标设为 j,则相邻元素下标值为 j +1,搜索到最后一个元素:j+1<a.length,而 a.length - 1 = i ;所以终止条件是 j < i

🟡前言


21天挑战赛第二天,本文主要讲述有关冒泡排序内容


活动地址CSDN21天学习挑战赛


🟡概述


冒泡排序是从第一个元素开始比较相邻两个数,并将大的放在后面,直到数据完成从小到大的排序。如下图所示是其原理


70df9ad6a4914cf2ae5c454d5b55a628.jpg


🟡两种解题思路及代码实现


1️⃣调用API解决


这种解题思路将会牵扯到三个API


  • public static void sort(Comparable[]a):对数组a中元素进行排序


  • public static boolean greater(Comparable x, Cpmparable y):判断x是否大于y;

一般使用时会这么写:x.compareTo(y) ,再判断值是否 >0 , >0则表示 x>y


  • public static void exch(Comparable[]a, int i, int j):交换数组a中下标为 i 和 j 的元素


解题思路如下


1.想要对数组内元素进行排序,就要调用public static void sort(Comparable[]a)


2.调用循环语句比较元素,比较次数取决于元素个数 j,比较次数 = 元素个数-1 ,即a.length - 1 = i ,每循环一次,次数减去1,直至次数为0


3.要比较的每一对元素是相邻的,从下标为0开始,到最后一个元素,如果下标设为 j,则相邻元素下标值为 j +1,搜索到最后一个元素:j+1<a.length,而 a.length - 1 = i ;所以终止条件是 j < i


4.在循环体内比较相邻两个元素的大小,当前者大于后者时,调换二者次序


5.转换成字符串后打印输出


使用IDEA验证一下程序


3fd1e725abf9417cb7ba3378d41b73b1.png


具体代码如下


public class BubbleSort {
    public static void sort(Comparable[] a) {
        for(int i=a.length-1; i>0; i--){
            for(int j=0; j<i; j++){
                if(greater(a[j], a[j+1])){
                    exch(a,j,j+1);
                }
            }
        }
    }
  //比较两数大小
    private static boolean greater(Comparable x, Comparable y){
        return x.compareTo(y) > 0;
    }
  //交换数组内两个元素
    private static void exch(Comparable[] a, int i, int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
import java.util.Arrays;
public class BubbleSortTest {
    public static void main(String[] args) {
        Integer[] arr = {4,5,6,3,2,1};
        BubbleSort.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}


要注意的是,在写原数组时,要使用Integer来实现Comparable接口


2️⃣普通解法


public class test {
    public static void main(String[] args) {
        int arr[] = {4,5,6,3,2,1};
        int temp = 0;
        System.out.println("原数组是");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        for(int i = 0; i <arr.length; i++){
            for(int j = i+1; j < arr.length; j++){
                if(arr[i] > arr[j]){
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        System.out.println("\n排序后数组是");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

e341dba149574e81a128ad74c027cf13.png


🟡时间复杂度


比较元素:(n-1) + (n-2) + … + 2 + 1 = 1/2 * (n^2 - n)

交换元素:(n-1) + (n-2) + … + 2 + 1 = 1/2 * (n^2 - n)

总计:n^2 - n

时间复杂度为:O(n^2)


🟡结语


冒泡排序比较容易理解,接下来会介绍选择排序


相关文章
|
15天前
|
存储 算法
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
这篇文章详细介绍了图的概念、表示方式以及深度优先遍历和广度优先遍历的算法实现。
30 1
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
|
12天前
|
缓存 算法 Java
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
这篇文章详细介绍了Java虚拟机(JVM)中的垃圾回收机制,包括垃圾的定义、垃圾回收算法、堆内存的逻辑分区、对象的内存分配和回收过程,以及不同垃圾回收器的工作原理和参数设置。
36 4
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
|
13天前
|
算法
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
40 2
动态规划算法学习三:0-1背包问题
|
1天前
|
搜索推荐
冒泡排序算法
【10月更文挑战第19天】冒泡排序是一种基础的排序算法,虽然在实际应用中可能不是最优的选择,但对于理解排序算法的基本原理和过程具有重要意义。
|
13天前
|
算法
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
48 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
|
13天前
|
算法
动态规划算法学习二:最长公共子序列
这篇文章介绍了如何使用动态规划算法解决最长公共子序列(LCS)问题,包括问题描述、最优子结构性质、状态表示、状态递归方程、计算最优值的方法,以及具体的代码实现。
55 0
动态规划算法学习二:最长公共子序列
|
13天前
|
缓存 负载均衡 算法
nginx学习:配置文件详解,负载均衡三种算法学习,上接nginx实操篇
Nginx 是一款高性能的 HTTP 和反向代理服务器,也是一个通用的 TCP/UDP 代理服务器,以及一个邮件代理服务器和通用的 HTTP 缓存服务器。
19 0
nginx学习:配置文件详解,负载均衡三种算法学习,上接nginx实操篇
|
15天前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
14 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
15天前
|
存储 算法 数据管理
数据结构与算法学习二零:二叉排序树(BST)、平衡二叉树(AVL)
这篇文章通过需求分析、代码实现和测试验证,详细介绍了二叉排序树的创建、遍历和删除操作,以及二叉平衡树(AVL)的自平衡特性和单旋转操作,旨在提高树结构在数据管理中的效率和性能。
18 0
数据结构与算法学习二零:二叉排序树(BST)、平衡二叉树(AVL)
|
13天前
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
56 0