排序算法之冒泡排序详解

企鹅博客
企鹅博客
企鹅博客
25193
文章
0
评论
2019年9月30日00:12:03 评论 160 views
广告也精彩

冒泡排序是一种非常常见的排序算法。如同水中的一排泡泡,先冒出最大的一个泡泡。再冒出剩余泡泡中的最大泡泡,依次类推,它的排序规则如下:

  1. 从第一个元素开始,比较相邻的两个元素,如果后面的小于前面的,交换两个的位置,一直比较到最后一个
  2. 循环1中的操作,但已经确定的最大的元素不再参与比较
  3. 直到不确定大小顺序的元素剩余两个,然后对这两个进行比较,然后结束循环

排序图示(图片来源网络)

排序算法之冒泡排序详解

Java实现

用java实现一个简单的冒泡排序。为了便于理解,在寻找到第一个最大元素完成后,称之为第一趟,依次类推,可以发现一共需要n-1趟

  publicvoidbubbleSort() {
    int[] array = {6, 2, 5, 3};
    for (int i = 0; i < array.length - 1; i++) {// 需要排序的趟数
      for (int j = 0; j < array.length - i - 1; j++) {// 每一趟需要比较的次数
        if (array[j + 1] < array[j]) {
          int variable = array[j + 1];
          array[j + 1] = array[j];
          array[j] = variable;
        }
      }
      System.out.println("第" + (i + 1) + "趟排序后的结果:" + Arrays.toString(array));
    }
    System.out.println("最终的排序结果:" + Arrays.toString(array));
  }

console

1趟排序后的结果:[2, 5, 3, 6]
第2趟排序后的结果:[2, 3, 5, 6]
第3趟排序后的结果:[2, 3, 5, 6]
最终的排序结果:[2, 3, 5, 6]

排序过程分析

第一趟排序

排序前:[6, 2, 5, 3]
排序后:[2, 5, 3, 6]
6与2比较,然后互换位置,然后与5比较,互换位置,最后与3比较,互换位置,此时6在最后的位置,确定最大值6,一共比较3次

第二趟排序

排序前:[2, 5, 3, 6]
排序后:[2, 3, 5, 6]
2与3比较,位置不变,然后5与3比较,然后互换位置,因为6的位置已经确定,所以5与6不再比较,一共比较2次

第三趟排序

排序前:[2, 3, 5, 6]
排序后:[2, 3, 5, 6]
2与3比较,位置不变,5,6的位置已经确定,所以不再比较,一共比较1次

由上面的分析可以看出,一共进行了1+2+...+n-1次比较。也就是n(n-1)/2次,即(N^2 - n)/2次,去除对结果影响不大的N^2 - n中的-n,以及系数0.5,得出时间复杂度为 O(N^2) (注:此处的时间复杂度自己尚未完全理解,希望明白的朋友可以给予解答)

优化

  publicvoidbubbleSort() {
    int[] array = {6, 2, 5, 3};
    for (int i = 0; i < array.length - 1; i++) {// 需要排序的趟数
      boolean flag = false;// 默认不存在位置交换
      for (int j = 0; j < array.length - i - 1; j++) {// 每一趟需要比较的次数
        if (array[j + 1] < array[j]) {
          flag = true;// 存在位置交换,修改flag为true
          int variable = array[j + 1];
          array[j + 1] = array[j];
          array[j] = variable;
        }
      }
      if (!flag) {
        break;// 不存在位置交换 跳出循环
      }
    }
    System.out.println("最终的排序结果:" + Arrays.toString(array));
  }
企鹅博客
  • 本文由 发表于 2019年9月30日00:12:03
  • 转载请务必保留本文链接:https://www.qieseo.com/135891.html
Android短信应用——短信信息实时获取 Linux编程

Android短信应用——短信信息实时获取

我们知道,只需通过代码就可以读到收件箱中的短信,发件箱中的短信;但是却没办法在短信发来的瞬间获取;如果我们在短信发来的一瞬间能得到相应的信息内容,那么我们就可以依次来展开很多应用了——也就是通过短信去...
LRU缓存设计 Linux编程

LRU缓存设计

缓存的数据结构采用哈希表,key到value的映射。 网上有些资料采用记录数据的使用时刻 实现LRU策略,此处采用双向链表 实现LRU策略。LRU Least Recently Used,MRUMos...
R 语言 简单介绍 Linux编程

R 语言 简单介绍

一.统计分析软件说明  统计分析软件有:SPSS, SAS、R语言,Matlab,S-PLUS,S-Miner。 SPSS: 最简单的,都是菜单操作,不过不利于二次程序开发。 SAS: 需要...

发表评论