java简单冒泡排序实例解析

2024-09-28 01:17:48

一、算法原理

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

二、实现思路

用二重循环实现，外循环变量设为i，内循环变量设为j。假如有n个数需要进行排序，则外循环重复n-1次，内循环依次重复n-1，n-2，...，1次。每次进行比较的两个元素都是与内循环j有关的，它们可以分别用a[j]和a[j+1]标识，i的值依次为1,2,...,n-1，对于每一个i，j的值依次为0,1,2,...n-i 。

设数组长度为N：

1．比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。
2．这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。
3．N=N-1，如果N不为0就重复前面二步，否则排序完成。

三、代码实现

package sort;
import java.util.Arrays;
/**
 * 冒泡排序
 * 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
 * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
 * 针对所有的元素重复以上的步骤，除了最后一个。
 * 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
 */

public class BubbleSort {
  public static void bubbleSort(int[] arr) {
    boolean flag=true;
    while (flag) {
      flag=false;
      int temp = 0;
      for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
          if (arr[j] > arr[j + 1]) {   //交换两数位置
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
            flag=true;
          }
        }
        if (!flag){
          break;
        }
        }
      }
    }
  public static void main(String[] args){
    int a[]=new int[]{345,22,43,12,65,335,124,636,3};
    BubbleSort.bubbleSort(a);
    System.out.print(Arrays.toString(a));
  }
}

四、性能分析

若记录序列的初始状态为"正序"，则冒泡排序过程只需进行一趟排序，在排序过程中只需进行n-1次比较，且不移动记录；反之，若记录序列的初始状态为"逆序"，则需进行n（n-1)/2次比较和记录移动。因此冒泡排序总的时间复杂度为O(n*n)。

五、算法优化

冒泡排序法存在的不足及改进方法：

第一、在排序过程中，执行完最后的排序后，虽然数据已全部排序完备，但程序无法判断是否完成排序，为了解决这一不足，可设置一个标志位flag，将其初始值设置为true，表示被排序的表是一个无序的表，每一次排序开始前设置flag值为true，在进行数据交换时，修改flag为false。在新一轮排序开始时，检查此标志，若此标志为false，表示上一次没有做过交换数据，则结束排序；否则进行排序；

第二、在冒泡排序中，一趟扫描有可能无数据交换，也有可能有一次或多次数据交换，在传统的冒泡排序算法及近年来的一些改进的算法中，只记录一趟扫描有无数据交换的信息，对数据交换发生的位置信息则不予处理。为了充分利用这一信息，可以在一趟全局扫描中，对每一反序数据对进行局部冒泡排序处理，称之为局部冒泡排序。局部冒泡排序与冒泡排序算法具有相同的时间复杂度，并且在正序和逆序的情况下，所需的关键字的比较次数和移动次数完全相同。由于局部冒泡排序和冒泡排序的数据移动次数总是相同的，而局部冒泡排序所需关键字的比较次数常少于冒泡排序，这意味着局部冒泡排序很可能在平均比较次数上对冒泡排序有所改进，当比较次数较少的优点不足以抵消其程序复杂度所带来的额外开销，而当数据量较大时，局部冒泡排序的时间性能则明显优于冒泡排序。对于N个无序数据，我们在进行一趟冒泡排序时，如果第k个数据和第k+1个数据逆序，那么对第k+1个数据进行一趟向前的冒泡排序，使其移动到合适的位置，也就是说让前面k+1个数据调节为正序。因为这种冒泡法只对前k+1个数据冒泡处理，所以我们称它为——局部冒泡

package sort;

import java.util.Arrays;

public class BubbleSort {
  public static void bubbleSort(int[] arr) {
    boolean flag=true;
    while (flag) {
      flag=false;
      int temp = 0;
      for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
          if (arr[j] > arr[j + 1]) {   //交换两数位置
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
            flag=true;
          }
        }
        if (!flag){
          break;
        }
        }
      }
    }
  public static void main(String[] args){
    int a[]=new int[]{345,22,43,12,65,335,124,636,3};
    BubbleSort.bubbleSort(a);
    System.out.print(Arrays.toString(a));
  }
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

冒泡排序算法原理及JAVA实现代码

冒泡排序法:关键字较小的记录好比气泡逐趟上浮,关键字较大的记录好比石块下沉,每趟有一块最大的石块沉底. 算法本质:(最大值是关键点,肯定放到最后了,如此循环)每次都从第一位向后滚动比较,使最大值沉底,最小值上升一次,最后一位向前推进(即最后一位刚确定的最大值不再参加比较,比较次数减1) 复杂度: 时间复杂度 O(n2) ,空间复杂度O(1) JAVA源代码(成功运行,需要Date类) 复制代码代码如下: public static void bubbleSort(Date[] days) {
java数组排序示例(冒泡排序、快速排序、希尔排序、选择排序)

快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现. 冒泡法是运用遍历数组进行比较,通过不断的比较将最小值或者最大值一个一个的遍历出来. 选择排序法是将数组的第一个数据作为最大或者最小的值,然后通过比较循环,输出有序的数组. 插入排序是选择一个数组中的数据,通过不断的插入比较最后进行排序. 复制代码代码如下: package com.firewolf.sort; public class MySort { /** * @param args */ public s
Java冒泡排序（Bubble Sort）实例讲解

举个例子:int[] array = {2,4,9,7,6,5}; 第一轮2和4进行比较,2<4,位置不变.再4和9进行比较,4<9,位置不变.再9和7进行比较,9>7,9和7的位置互换.再9和6进行比较,9>6,9和6的位置互换.再9和5进行比较,9>5,位置互换.第一轮比较的结果就是2 4 7 6 5 9. 第二轮2和4进行比较,2<4,位置不变.再4和7进行比较,4<7,位置不变.再7和5进行比较,7>6,7和6的位置互换.再7和5进行比较,7>
深入Java冒泡排序与选择排序的区别详解

冒泡排序它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.代码如下: 复制代码代码如下: public class nums { public static void main(String[] args){ int []nums = {5,4,3,2,1}; for(int i = 0; i < nums.length; i++){
java利用冒泡排序对数组进行排序

本文实例讲述了java利用冒泡排序对数组进行排序的方法.分享给大家供大家参考.具体如下: 一.冒泡排序: 利用冒泡排序对数组进行排序二.基本概念: 依次比较相邻的两个数,将小数放在前面,大数放在后面.即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后.然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后.至此第一趟结束,将最大的数放到了最后.在第二趟:仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数
用java实现冒泡排序算法

冒泡排序的算法分析与改进交换排序的基本思想是:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止. 应用交换排序基本思想的主要排序方法有:冒泡排序和快速排序. 复制代码代码如下: public class BubbleSort implements SortUtil.Sort{ public void sort(int[] data) { int temp; for(int i=0;i<data.length;i++){ for(int j=data.le
java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述

算法是在有限步骤内求解某一问题所使用的一组定义明确的规则.通俗点说,就是计算机解题的过程.在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法.前者是推理实现的算法,后者是操作实现的算法. 一个算法应该具有以下五个重要的特征: 1.有穷性: 一个算法必须保证执行有限步之后结束: 2.确切性: 算法的每一步骤必须有确切的定义: 3.输入:一个算法有0个或多个输入,以刻画运算对象的初始情况: 4.输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果.没有输出的算法是毫无意义的:
Java中的数组排序方式(快速排序、冒泡排序、选择排序)

1.使用JavaApi文档中的Arrays类中的sort()进行快速排序复制代码代码如下: import java.util.Arrays; public class TestOne{ public static void main(String [] args){ int [] array={2,0,1,4,5,8}; Arrays.sort(array);//调用Arrays的静态方法Sort进行排序,升序排列 for(int show:array){ System.out.printl
java冒泡排序算法代码

复制代码代码如下: /** * 原理: * 进行n次循环,每次循环从后往前对相邻两个元素进行比较,小的往前,大的往后 * * 时间复杂度: * 平均情况:O(n^2) * 最好情况:O(n) * 最坏情况:O(n^2) * * 稳定性:稳定 **/public class 冒泡排序 { public int[] bubbleSort(int[] a, int n) { for (int i = 0; i < n; i++) { int flag = 0;
java简单冒泡排序实例解析

一.算法原理比较相邻的元素.如果第一个比第二个大,就交换他们两个. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数. 针对所有的元素重复以上的步骤,除了最后一个. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较. 二.实现思路用二重循环实现,外循环变量设为i,内循环变量设为j.假如有n个数需要进行排序,则外循环重复n-1次,内循环依次重复n-1,n-2,...,1次.每次进行比较的两个元素都是与内循环j有关的,它们可以分
Java简单冒泡排序示例解析

冒泡排序: 从小到大排序: package com.etime.test019; import java.util.Arrays; public class Test13 { public static void main(String[] args) { int[] array = { 6, 1, 2, 3, 8, 5, 4, 9, 7 }; int len = array.length; System.out.println("排序前的数组为:"+Arrays.toString(a
java简单快速排序实例解析

一.基本概念找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值都不小于基准值,如此作为基准的元素调整到排序后的正确位置.递归快速排序,将其他n-1个元素也调整到排序后的正确位置.最后每个元素都是在排序后的正确位置,排序完成.所以快速排序算法的核心算法是分区操作,即如何调整基准的位置以及调整返回基准的最终位置以便分治递归. 二.选择基准元 1.固定基准元如果输入序列是随机的,处理时间是可以接受的.如果数组已
bootstrap导航栏、下拉菜单、表单的简单应用实例解析

制作效果图如下: 代码如下(以后做东西可以改改就能直接用): <!DOCTYPE html> <html lang="zh-cn"> <head> <meta charset="utf-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <meta name="viewport"
Java String创建对象实例解析

本文研究的主要是Java String创建对象的问题,具体介绍如下. 首先我们要明白两个概念,引用变量和对象,对象一般通过new在堆中创建,String只是一个引用变量. 所有的字符串都是String对象,由于字符串常量的大量使用,java中为了节省时间,在编译阶段,会把所有字符串常量放在字符串常量池中,字符串常量池的一个好处就是可以把相同的字符串合并,占用一个空间. 虽然在Java中无法直接获取变量的地址,但是可以用==判断一下两个引用变量是否指向了一个地址即一个对象. 栈内存堆内存基础类
Java编程WeakHashMap实例解析

简述: <Thinking in Java>第4版 P519 页 WeakHashMap一章读书笔记 WeakHashMap 用来保存WeakReference,这一结构云逊垃圾回收器自动清理键和值在添加键和值的操作时,映射会自动使用WeakReference包装它们, 见jdk源代码, public V put(K key, V value) { Object k = maskNull(key); int h = hash(k); Entry<K,V>[] tab = getT
java hasNext()使用实例解析

这篇文章主要介绍了java hasNext()使用实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下编写一段程序实现如果输入的一组数中含非整数数字,输出数字相加的和以及"attention"字符,如果全部是数字便输出数字的和. 程序1: package mian; import java.util.Scanner; public class mian { public static void main(String[] args
Java数据类型转换实例解析

这篇文章主要介绍了Java数据类型转换实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下数据类型转换 Java程序中要求参与的计算的数据,必须要保证数据类型的一致性,如果数据类型不一致将发生类型的转换. 数据类型的转换分类自动类型转换自动类型转换(隐式):将取值范围小的类型自动提升为取值范围大的类型 . 转换规则 :范围小的类型向范围大的类型提升, byte.short.char 运算时直接提升为 int . byte.short.
Java Comparator比较器实例解析

这篇文章主要介绍了Java Comparator比较器实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下说几点需要注意的,提醒自己即可: 以下是单独定义一个比较器的类,实现了Comparator中的compare方法.(要在Main方法外面定义类噢) 一定是compare而不是Compare哦 package xixixi; import java.util.*; public class Main { public static voi
Java枚举抽象方法实例解析

这篇文章主要介绍了Java枚举抽象方法实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下需求背景需求已经确定了几个固定的常量值,并且每个常量值都有相同的行为,但是具体实现细节不同.建议使用枚举抽象方法,优点:结构清晰,便于扩展. 枚举类实现抽象方法与常规抽象类一样,enum类允许我们为其定义抽象方法,然后使每个枚举实例都实现该方法,以便产生不同的行为方式,注意abstract关键字对于枚举类来说并不是必须的,举个栗子: public

java简单冒泡排序实例解析

相关推荐

随机推荐