博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
冒泡排序分析
阅读量:6672 次
发布时间:2019-06-25

本文共 1951 字,大约阅读时间需要 6 分钟。

一.冒泡排序算法的原理:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了第一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

  冒泡排序是一个稳定的排序算法

二.冒泡排序时间复杂度:

  1.如果数据是正序的,只需要走一趟即可完成排序。所需的比较次数和记录移动次数均达到最小值,所以,冒泡排序最好的时间复杂度为O(n)

  2.如果数据是反序的,则需要进行n-1趟排序。每趟排序要进行n-i次比较(1 ≤ i ≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大次数,冒泡排序的最坏时间复杂度为:O(n2) 平均时间复杂度是O(n2)

三.代码实现(Java):

public class BubbleSort {
/** * 冒泡排序一,非优化版 * @param arr */ public static void sort1(int[] arr){ for(int i = 0; i
arr[j+1]){ int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } //System.out.println(arr.toString());//这里的toString返回的是哈希码 //数组的打印应该选择Arrays.toString(arr); System.out.println(Arrays.toString(arr)); } /** * 冒泡排序二,优化版 * @param arr */ public static void sort2(int[] arr){ for(int i = 0; i
arr[j+1]){ int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } System.out.println(Arrays.toString(arr)); } /** * 冒泡排序3,最终版(考虑了到某次一次交换顺序的情况都没发生的时候,不需要排序了,直接跳出循环) * @param arr */ public static void sort3(int[] arr){ boolean isSort = true; for(int i = 0; i
arr[j+1]){ int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; isSort = false; } } System.out.println(Arrays.toString(arr)); if(isSort){ break; } } System.out.println(Arrays.toString(arr)); }}

 测试以上代码:

public static void main(String[] args) {        int[] arr = {1,7,8,5,9,6,2,3,4};        sort3(arr); }

打印如下结果:

 

转载于:https://www.cnblogs.com/ywb-articles/p/10663467.html

你可能感兴趣的文章
度量平台角色的含义及运用
查看>>
前嗅ForeSpider教程:创建模板
查看>>
JAVA 排序 冒泡法
查看>>
Nginx安装和常用配置文档
查看>>
oracle数据库控制文件Control files
查看>>
docker常用网络模型:
查看>>
zTree模糊查询节点并且隐藏节点
查看>>
K3CLOUD自动备份Oracle数据库并删除指定天数前的备份
查看>>
java mail 签名 加密
查看>>
shell训练day15
查看>>
网络编程readn、writen和readline函数的编写
查看>>
CPU的位数,字长,地址总线
查看>>
vim 小技巧
查看>>
webbench
查看>>
使用递归遍历并转换树形数据(以 TypeScript 为例)
查看>>
WEB文件上传方案探索(一)
查看>>
PHP类推荐:QueryList|基于phpQuery的无比强大的PHP采集工具
查看>>
Spring实战笔记:Spring核心(一)
查看>>
nginx技术(5)日志管理和限速
查看>>
js正则集(用的时候找)
查看>>