JAVA十大排序算法之冒泡排序详解

目录
  • 冒泡排序
    • 代码实现
    • 代码实现
    • 时间复杂度
    • 算法稳定性
  • 总结

冒泡排序

1.从数组头开始，比较相邻的元素。如果第一个比第二个大(小)，就交换它们两个

2.对每一对相邻元素作同样的工作，从开始第一对到尾部的最后一对，这样在最后的元素应该会是最大(小)的数

3.重复步骤1~2，重复次数等于数组的长度，直到排序完成

代码实现

对下面数组实现排序：{24, 7, 43, 78, 62, 98, 82, 18, 54, 37, 73, 9}

代码实现

public class BubbleSort {
    public static final int[] ARRAY = {24, 7, 43, 78, 62, 98, 82, 18, 54, 37, 73, 9};
    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY));
    }
    public static int[] sort(int[] array) {
        if (array.length == 0) {
            return array;
        }
        for (int i = 0; i < array.length; i++) {
            //array.length - 1 -i 已经冒泡到合适位置无需在进行排序，减少比较次数
            for (int j = 0; j < array.length - 1 -i; j++) {
                //前面的数大于后面的数交换
                if (array[j + 1] < array[j]) {
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
        }
        return array;
    }
    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }
}

时间复杂度

对于上面12个数据项，从第一个元素开始，第一趟比较了11次，第二趟比较了10次，依次类推，一直到最后一趟，就是：

11 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 66次

若有n个元素，则第一趟比较为(n-1)次，第二趟比较为(n-2)次，依次类推：

(n-1) + (n-2) + (n-3) + ...+ 2 + 1 = n * (n-1)/2

在大O表示法中，去掉常数系数和低阶项，该排序方式的时间复杂度为：O(n2)

算法稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。——百度百科

在代码中可以看到，array[j + 1] = array[j]的时候，我们可以不移动array[i]和array[j]，所以冒泡排序是稳定的。

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注我们的更多内容！

赞 (0)

相关推荐

  • java 排序算法之冒泡排序

    java 排序算法之冒泡排序

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

  • Java实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等

    Java实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等

    本文实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 .快速排序.归并排序.堆排序和LST基数排序 首先是EightAlgorithms.java文件,代码如下: import java.util.Arrays; /* * 实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 * 以及快速排序.归并排序.堆排序和LST基数排序 * @author gkh178 */ public class EightAlgorithms { //插入排序:时间复杂度o(n^2) p

  • java排序算法之冒泡排序

    java排序算法之冒泡排序

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

  • 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实现冒泡排序算法及对其的简单优化示例

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

  • 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实现的各种排序算法(插入排序、选择排序算法、冒泡排序算法)

    一.插入排序算法实现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排序算法总结之冒泡排序.分享给大家供大家参考.具体分析如下: 前言:冒泡排序(BubbleSort)就是依次比较相邻的两个数,将小数放在前面,大数放在后面. 下面让我们一起    来看冒泡排序在Java中的算法实现. 冒泡排序是计算机的一种排序方法,它的时间复杂度为O(n^2),虽然不及堆排序.快速排序的O(nlogn,底数为2),但是有两个优点: 1."编程复杂度"很低,很容易写出代码: 2.具有稳定性,这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序后

  • JAVA十大排序算法之冒泡排序详解

    JAVA十大排序算法之冒泡排序详解

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

  • JAVA十大排序算法之归并排序详解

    JAVA十大排序算法之归并排序详解

    目录 归并排序 怎么分 怎么治 代码实现 时间复杂度 算法稳定性 总结 归并排序 归并,指合并,合在一起.归并排序(Merge Sort)是建立在归并操作上的一种排序算法.其主要思想是分而治之.什么是分而治之?分而治之就是将一个复杂的计算,按照设定的阈值进行分解成多个计算,然后将各个计算结果进行汇总.即"分"就是把一个大的通过递归拆成若干个小的,"治"就是将分后的结果在合在一起. 若将两个有序集合并成一个有序表,称为2-路归并,与之对应的还有多路归并. 怎么分 对于

  • JAVA十大排序算法之堆排序详解

    JAVA十大排序算法之堆排序详解

    目录 堆排序 知识补充 二叉树 满二叉树 完全二叉树 二叉堆 代码实现 时间复杂度 算法稳定性 思考 总结 堆排序 这里的堆并不是JVM中堆栈的堆,而是一种特殊的二叉树,通常也叫作二叉堆.它具有以下特点: 它是完全二叉树 堆中某个结点的值总是不大于或不小于其父结点的值 知识补充 二叉树 树中节点的子节点不超过2的有序树 满二叉树 二叉树中除了叶子节点,每个节点的子节点都为2,则此二叉树为满二叉树. 完全二叉树 如果对满二叉树的结点进行编号,约定编号从根结点起,自上而下,自左而右.则深度为k的,有

  • JAVA十大排序算法之基数排序详解

    JAVA十大排序算法之基数排序详解

    目录 基数排序 代码实现 时间复杂度 算法稳定性 基数排序 vs 桶排序 vs 计数排序 总结 基数排序 常见的数据元素一般是由若干位组成的,比如字符串由若干字符组成,整数由若干位0~9数字组成. 基数排序按照从右往左的顺序,依次将每一位都当做一次关键字,然后按照该关键字对数组排序,同时每一轮排序都基于上轮排序后的结果:当我们将所有的位排序后,整个数组就达到有序状态.基数排序不是基于比较的算法. 基数是什么意思?对于十进制整数,每一位都只可能是0~9中的某一个,总共10种可能.那10就是它的基,

  • JAVA十大排序算法之快速排序详解

    JAVA十大排序算法之快速排序详解

    目录 快速排序 问题 思路 荷兰国旗问题 代码实现 时间复杂度 算法稳定性 总结 快速排序 快速排序是对冒泡排序的一种改进,也是采用分治法的一个典型的应用.JDK中Arrays的sort()方法,具体的排序细节就是使用快速排序实现的. 从数组中任意选取一个数据(比如数组的第一个数或最后一个数)作为关键数据,我们称为基准数(pivot,或中轴数),然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序,也称为分区(partition)操作. 问题 若给定一个无序数组

  • JAVA十大排序算法之插入排序详解

    JAVA十大排序算法之插入排序详解

    目录 插入排序 代码实现 动图演示 代码实现 时间复杂度 算法稳定性 总结 插入排序 当我们在玩扑克牌的时候,总是在牌堆里面抽取最顶部的一张然后按顺序在手中排列. 插入排序是指在待排序的元素中,假设前面n-1(其中n>=2)个数已经是排好顺序的,现将第n个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的. 1.对于未排序数据(一般取数组的二个元素,把第一个元素当做有序数组),在已排序序列中从左往右扫描,找到相应位置并插入. 2.为了给要插入的元素腾出空

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

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

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

  • TypeScript实现十大排序算法之冒泡排序示例详解

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

  • Java 十大排序算法之插入排序刨析

    Java 十大排序算法之插入排序刨析

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

  • Java 十大排序算法之选择排序刨析

    Java 十大排序算法之选择排序刨析

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

随机推荐