Java 十大排序算法之冒泡排序刨析

2024-10-01 11:45:46

冒泡排序原理

①比较相邻的元素，如果前一个元素比后一个元素大，则交换这两个元素的位置

②对每一对相邻的元素循环上面的步骤，最终最后面的元素就是最大值

冒泡排序API设计

类名

Bubble

构造方法

Bubble:创建Bubble对象

成员方法

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

2.private static void greater(Comparable v,Comparable w)；判断v是否大于w

3.private static void exchange(Comparable[] a,int x,int y):交换a数组中，索引x和索引y处的值

冒泡排序的代码实现

public class Bubble {
    //对数组a进行排序
    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])){
                    exchange(a,j,j+1);
                }
            }
        }

    }
    //比较v元素是否大于w元素
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0;
    }
    //数组元素x和y交换位置
    private static void exchange(Comparable[] a,int x,int y){
        Comparable t=a[x];
        a[x]=a[y];
        a[y]=t;
    }
}
//测试代码
 class Test{
    public static void main(String[] args) {
        Integer[] a={4,5,6,3,2,1};
        Bubble.sort(a);
        System.out.println(Arrays.toString(a));
    }
}

测试结果：

冒泡排序的时间复杂度分析

冒泡排序虽然采用了双层for循环遍历，但是真正完成排序的代码在内循环中，所以主要分析内层循环体的执行次数即可

在最坏的情况下。即数组为{6,5,4,3,2,1}的逆序

元素的比较次数为：(N-1)+(N-2)+(N-3)+...+2+1=

((N-1)+1)*(N-1)/2=N^2/2-N/2;

元素的交换次数为：(N-1)+(N-2)+(N-3)+...+2+1=

((N-1)+1)*(N-1)/2=N^2/2-N/2;

总执行次数为：2*(N^2/2-N/2)=N^2-N;

根据大O推导法则，保留最高阶项，即冒泡排序的时间复杂度为O(N^2)

到此这篇关于Java 十大排序算法之冒泡排序刨析的文章就介绍到这了,更多相关Java 冒泡排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

Java实现的各种排序算法(插入排序、选择排序算法、冒泡排序算法)

一.插入排序算法实现java版本 public static int[] insert_sort(int[] a) { for (int i = 0; i < a.length; i++) { for(int j=i+1;j>0&&j<a.length;j--) { if(a[j]<a[j-1]) { int tmp = a[j]; //这样定义初始化逻辑上是可以的,j变量,每次tmp的值变化的 a[j] = a[j-1]; a[j-1] = tmp; } } }
java实现的冒泡排序算法示例

本文实例讲述了java实现的冒泡排序算法.分享给大家供大家参考,具体如下: public class PaoPaixu { public static void sort(int[] data){ int tmp; for (int i = 0; i < data.length; i++) { for (int j = i+1; j < data.length; j++) { if(data[i]>data[j]){ /*tmp=data[i]; data[i]=data[j]; dat
Java实现冒泡排序算法

冒泡排序: 就是按索引逐次比较相邻的两个元素,如果大于/小于(取决于需要升序排还是降序排),则置换,否则不做改变这样一轮下来,比较了n-1次,n等于元素的个数:n-2,n-3 ... 一直到最后一轮,比较了1次所以比较次数为递减:从n-1 到 1 那么总的比较次数为:1+2+3+--+(n-1), 以等差公式计算:(1+n-1)/2*(n-1) ==> n/2*(n-1) ==> (n^2-n) * 0.5 用大O表示算法的时间复杂度:O(n^2) , 忽略了系数0.5和常数-n. 算
Java实现冒泡排序与双向冒泡排序算法的代码示例

冒泡排序: 就是按索引逐次比较相邻的两个元素,如果大于/小于(取决于需要升序排还是降序排),则置换,否则不做改变这样一轮下来,比较了n-1次,n等于元素的个数:n-2, n-3 ... 一直到最后一轮,比较了1次所以比较次数为递减:从n-1 到 1 那么总的比较次数为:1+2+3+...+(n-1), 以等差公式计算:(1+n-1)/2*(n-1) ==> n/2*(n-1) ==> (n^2-n) * 0.5 用大O表示算法的时间复杂度:O(n^2) , 忽略了系数0.5和常数-n
JAVA十大排序算法之冒泡排序详解

目录冒泡排序代码实现代码实现时间复杂度算法稳定性总结冒泡排序 1.从数组头开始,比较相邻的元素.如果第一个比第二个大(小),就交换它们两个 2.对每一对相邻元素作同样的工作,从开始第一对到尾部的最后一对,这样在最后的元素应该会是最大(小)的数 3.重复步骤1~2,重复次数等于数组的长度,直到排序完成代码实现对下面数组实现排序:{24, 7, 43, 78, 62, 98, 82, 18, 54, 37, 73, 9} 代码实现 public class BubbleSort {
Java实现冒泡排序算法及对其的简单优化示例

原理冒泡排序大概是所有程序员都会用的算法,也是最熟悉的算法之一. 它的思路并不复杂: 设现在要给数组arr[]排序,它有n个元素. 1.如果n=1:显然不用排了.(实际上这个讨论似乎没什么必要) 2.如果n>1: (1)我们从第一个元素开始,把每两个相邻元素进行比较,如果前面的元素比后面的大,那么在最后的结果里面前者肯定排在后面.所以,我们把这两个元素交换.然后进行下两个相邻的元素的比较.如此直到最后一对元素比较完毕,则第一轮排序完成.可以肯定,最后一个元素一定是数组中最大的(因为每次都把相对
java排序算法之冒泡排序

本文实例为大家分享了java排序算法之冒泡排序的具体代码,供大家参考,具体内容如下冒泡排序冒泡排序无疑是最为出名的排序算法之一,从序列的一端开始往另一端冒泡(你可以从左往右冒泡,也可以从右往左冒泡,看心情),依次比较相邻的两个数的大小(到底是比大还是比小也看你心情) java代码实现bubblesort冒泡排序 package com.zy.test; import java.util.Arrays; public class BubbleSort { public static void
java 排序算法之冒泡排序

目录基本介绍图解冒泡排序算法的过程代码实现演变过程优化封装算法大量数据耗时测试基本介绍冒泡排序(Bubble Sorting)(时间复杂度为 O(n²))的基本思想:通过对待排序序列从前向后(从下标较小的元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前移向后部,就像水底下的旗袍一样逐渐向上冒. 优化点:因为排序过程中,个元素不断接近自己的位置,如果一趟比较下来没有进行过交换,就说明序列有序,因此要在排序过程中设置一个标志判断元素是否进行过交换.从而减
Java 十大排序算法之冒泡排序刨析

目录冒泡排序原理冒泡排序API设计冒泡排序的代码实现冒泡排序的时间复杂度分析冒泡排序原理 ①比较相邻的元素,如果前一个元素比后一个元素大,则交换这两个元素的位置 ②对每一对相邻的元素循环上面的步骤,最终最后面的元素就是最大值冒泡排序API设计类名 Bubble 构造方法 Bubble:创建Bubble对象成员方法 1.public static void sort(Comparable[] a):对数组内元素进行排序 2.private static void greater(C
Java 十大排序算法之插入排序刨析

目录插入排序原理插入排序API设计插入排序代码实现插入排序的时间复杂度分析插入排序原理 ①把所有元素分成已排序和未排序两组 ②找到未排序组的第一个元素,向已经排序的组中进行插入 ③倒序遍历已经排好的元素,依次和待插入的元素进行比较,直到找到一个元素小于等于待插入元素,那么就把待插入元素放到这个位置,其他元素向后移动一位插入排序API设计类名 Insertion 构造方法 Insertion():创建Insertion对象成员方法 1.public static void sort
Java 十大排序算法之归并排序刨析

目录归并排序原理归并排序API设计归并排序代码实现归并排序的时间复杂度分析归并排序原理 1.尽可能的一组数据拆分成两个元素相等的子组,并对每一个子组继续拆分,直到拆分后的每个子组的元素个数是1为止. ⒉将相邻的两个子组进行合并成一个有序的大组. 3.不断的重复步骤2,直到最终只有一个组为止. 归并排序API设计类名 Merge 构造方法 Merge():创建Merge对象成员方法 1.public static void sort(Comparable[] a):对数组内的元素进行
Java 十大排序算法之堆排序刨析

二叉堆是完全二叉树或者是近似完全二叉树. 二叉堆满足二个特性︰ 1．父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值. 2．每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆). 任意节点的值都大于其子节点的值--大顶堆(最后输出从小到大排) 任意节点的值都小于其子节点的值---小顶堆(最后输出从大到小排) 堆排序步骤 1.堆化,反向调整使得每个子树都是大顶或者小顶堆(建堆) 2.按序输出元素∶把堆顶和最末元素对调,然后调整堆顶元素(排序) 堆排序代码实现(大顶堆) publ
Java 十大排序算法之选择排序刨析

目录选择排序原理选择排序API设计选择排序代码实现选择排序的时间复杂度选择排序原理 ①假设第一个索引处的元素为最小值,和其他值进行比较,如果当前的索引处的元素大于其他某个索引处的值,则假定其他某个索引处的值为最小值,最后找到最小值所在的索引 ②交换第一个索引处和最小值所在的索引处的值选择排序API设计类名 Selection 构造方法 Selection():创建Selection对象成员方法 1.public static void sort(Comparable[] a):对
Java 十大排序算法之希尔排序刨析

目录希尔排序原理希尔排序的API设计希尔排序的代码实现希尔排序是插入排序的一种,又称"缩小增量排序",是插入排序算法的一种更高效的改进版本. 希尔排序原理 1.选定一个增长量h,按照增长量h作为数据分组的依据,对数据进行分组. 2.对分好组的每一组数据完成插入排序. 3.减小增长量,最小减为1,重复第二步操作. 希尔排序的API设计类名 Shell 构造方法 Shell():创建Shell对象成员方法 1.public static void sort(Comparable
Java 十大排序算法之计数排序刨析

计数排序是非比较的排序算法,用辅助数组对数组中出现的数字计数,元素转下标,下标转元素计数排序优缺点优点:快缺点:数据范围很大,比较稀疏,会导致辅助空间很大,造成空间的浪费使用范围:数据较为密集或范围较小时适用. 思路 1.找出最大元素max 2.初始化一个max+1的数组 3.将每个元素的计数存储在数组中各自的索引处 4.存储计数数组元素的累积和 5.数组中找到原始数组的每个元素的索引计数排序代码实现 public class CountingSort { private static
TypeScript实现十大排序算法之冒泡排序示例详解

目录一. 冒泡排序的定义二. 冒泡排序的流程三. 冒泡排序的图解四. 冒泡排序的代码五. 冒泡排序的时间复杂度六. 冒泡排序的总结一. 冒泡排序的定义冒泡排序是一种简单的排序方法. 基本思路是通过两两比较相邻的元素并交换它们的位置,从而使整个序列按照顺序排列. 该算法一趟排序后,最大值总是会移到数组最后面,那么接下来就不用再考虑这个最大值. 一直重复这样的操作,最终就可以得到排序完成的数组. 这种算法是稳定的,即相等元素的相对位置不会发生变化. 而且在最坏情况下,时间复杂度为O(
JAVA十大排序算法之桶排序详解

目录桶排序代码实现时间复杂度算法稳定性总结桶排序桶排序是计数排序的升级,计数排序可以看成每个桶只存储相同元素,而桶排序每个桶存储一定范围的元素,通过函数的某种映射关系,将待排序数组中的元素映射到各个对应的桶中,对每个桶中的元素进行排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序),最后将非空桶中的元素逐个放入原序列中. 桶排序需要尽量保证元素分散均匀,否则当所有数据集中在同一个桶中时,桶排序失效. 代码实现 1.找出数组中的最大值max和最小值min,可以确定出数组所在范

Java 十大排序算法之冒泡排序刨析

目录

冒泡排序原理

冒泡排序API设计

冒泡排序的代码实现

冒泡排序的时间复杂度分析

相关推荐

随机推荐