文档章节

冒泡排序实现及算法优化(java)

Demens
 Demens
发布于 2017/05/17 22:21
字数 1382
阅读 16
收藏 0

一、算法原理

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

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

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

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

 

二、实现思路

       用二重循环实现,外循环变量设为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));
    }
}

 

© 著作权归作者所有

共有 人打赏支持
Demens
粉丝 0
博文 11
码字总数 14760
作品 0
java 通配符的应用— java 排序算法

这几天无聊,又重新学起java的排序算法,为DualPivotQuickSort做准备。为了更好地适应各种情况,我们选择使用通用类型T和通配符的上下界来实现,同时这次谈的是对数组对象的排序。如果你对j...

天地一MADAO_
2014/03/02
0
0
2017 届 今日头条校招 Android 面试之成功篇

记录今日头条校招面试经历,废话不多说,直接上问题 一面-电面(34 min) 专业方向及其内容; 操作系统进程和线程的区别; 嵌入式底层了解没; 多核里面进程和线程的表现; APK 包含了哪些东西...

Hello_Google
2016/10/26
0
0
JAVA中运用数组的四种排序方法

JAVA中在运用数组进行排序功能时,一般有四种方法:快速排序法、冒泡法、选择排序法、插入排序法。 快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现。 冒泡法是运用遍历数组进...

IceRainYWC
2014/03/17
0
0
JAVA中运用数组的四种排序方法

JAVA中在运用数组进行排序功能时,一般有四种方法:快速排序法、冒泡法、选择排序法、插入排序法。 快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现。 冒泡法是运用遍历数组进...

闫三
2012/05/08
0
0
面试 10:玩转 Java 选择排序和插入排序

面试 10:Java 玩转选择排序和插入排序 昨天给大家讲解了 Java 玩转冒泡排序,大家一定觉得并没有什么难度吧,不知道大佬们玩转了吗?不知道大家有没有多加思考,实际上在我们最后的一种思路...

nanchen2251
07/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

74.expect脚本同步文件以及指定host同步文件 构建分发系统文件和命令

20.31 expect脚本同步文件: 在expect脚本中去实现在一台机器上把文件同步到另外一台机器上去。核心命令用的是rsync ~1.自动同步文件 #!/usr/bin/expect set passwd "123456" spawn rsync -a...

王鑫linux
25分钟前
0
0
TypeScript项目引用(project references)

转发 TypeScript项目引用(project references) TypeScript新特性之项目引用(project references) 项目引用是TypeScript 3.0中的一项新功能,允许您将TypeScript程序构建为更小的部分。 通过这...

durban
30分钟前
0
0
爬虫入门

导读 网络爬虫(Web crawler),是一种按照一定的规则,自动地抓取万维网信息的程序或者脚本,它们被广泛用于互联网搜索引擎或其他类似网站,可以自动采集所有其能够访问到的页面内容,以获取...

问题终结者
30分钟前
0
0
ppwjs之bootstrap文字排版:无序列表项不换行

<!DOCTYPT html><html><head><meta http-equiv="content-type" content="text/html; charset=utf-8" /><title>ppwjs欢迎您</title><link rel="icon" href="/favicon.ico" ......

ppwjs
37分钟前
0
0
SpringBoot 学习一

本文将从以下几个方面介绍: 前言 HelloWorld 读取配置文件 例子(CURD) 前言 Spring Boot是由Pivotal团队提供的全新框架,其设计目的是用来简化新Spring应用的初始搭建以及开发过程。该框架...

tsmyk0715
37分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部