排序算法-冒泡排序

ustbfym 2019-11-04

排序算法系列博客:
直接插入排序
希尔排序
简单选择排序
堆排序
冒泡排序
快速排序
归并排序
计数排序
基数排序

九大排序排序是数据结构体系中最重要的内容之一,这一块必须要非常熟练的掌握,应该做到可以立马写出每个排序的代码,有多种实现方法的必须多种都能很快写出来,当然对各个排序的性能的了解也是基础且重要的。我们先对排序这一块进行一个整体的把握。
排序算法-冒泡排序

  • 内排序:在对待排序数据存放在内存中进行的排序过程。是我们主要讨论与学习的重点。
  • 外排序:待排数据量太大,无法一次性将所有待排序数据放入内存中,在排序过程中需要对磁盘等外部储存器进行访问。不是我们谈论与学习的重点,但也要通过相关资料或书籍了解其基本原理。
  • 比较排序:排序过程中需要对数据关键字进行比较。
  • 非比较排序:排序过程中不需要对数据关键字进行比较。
  • 排序算法的稳定性:在每一次单趟排序后,相同关键字的相对顺序不变。(后面讲到了再具体解释)

所有讲解都以升序为例(降序完全就是改个符号的问题啦),本篇先讲几个简单的,复杂些的后面每个单独写。

冒泡排序

待排序数组: 42 ,13 ,15 ,28 ,23 ,17 ,14
冒泡相对算是最简单的排序了。思想就是:冒泡,就像水中的气泡,越往上泡泡约大,每一趟排序,都确定下来一个最大值,也就是冒出一个大泡泡。太多的解释不在赘述,网上都是。看下图:
排序算法-冒泡排序
解析冒泡排序过程:
1.第一趟排序

  • 42和13比较,42>13 ,所以,42和13交换:
    排序算法-冒泡排序

  • 42和15比较,42>15,所以,42和15交换:
    排序算法-冒泡排序

  • 42和28比较,42>28,所以,42和28交换:
    排序算法-冒泡排序

  • 42和23比较,42>23,所以,42和23交换:
    排序算法-冒泡排序

  • 42和17比较,42>17,所以,42和17交换:
    排序算法-冒泡排序

  • 42和14比较,42>14,所以,42和14交换:
    排序算法-冒泡排序

  • 42和15比较,42>15,所以,42和15交换:
    排序算法-冒泡排序

到此:第一趟排序结果就出来了,也就是j=0那一行的排序结果。得到的最后42,这个值,是有序区,无需继续比较大小,排序。
2.第二趟排序
同理,得出第二趟排序结果。【最后那个42是有序区,第二趟排序,就不需要比较这个值了】
第二趟结果:
排序算法-冒泡排序

这里有序区就是(28,42)。继续第三趟排序时候,就可以不比较这几个值了。
3.第三趟排序
同理,得出第三趟排序结果。【最后那个 28,42 是有序区,第三趟排序,就不需要比较这几个值了】
第三趟结果:
排序算法-冒泡排序

这里有序区就是(23,28,42)。继续第四趟排序时候,就可以不比较这几个值了。
。。。等等。如此,就能得出最后结果。应该能理解他的过程了吧?

下面上代码(Java实现)

/**
 * 冒泡排序测试代码 - 优化前
 * 存在问题:产生很多不必须要继续比较的操作
 * 就是上文中说的有序区,这里代码依旧进行了比较操作,这是多余的。
 * @param num
 * @return
 */
public int[] maoTest1(int[] num) {
    // 数组长度
    int len = num.length;
    // 临时变量,用于ab交换值
    int temp = 0;   
    // 外循环- 一行行往下走
    for (int j = 0; j < len; j++) {
        // 内循环-两两冒泡,把大的值冒到最后-确定下来排序完的一行的结果
        for (int i = 0; i < len - 1; i++) {
            if (num[i] > num[i + 1]) {
                temp = num[i];
                num[i] = num[i + 1];
                num[i + 1] = temp;
            }
        }
    }    
    return num;
}

/**
 * 冒泡排序 - 优化后
 * @param num
 * @return
 */
public int[] maoTest2(int[] num) {
    // 数组长度
    int len = num.length;
    // 临时变量,用于ab交换值
    int temp = 0;  
    // 外循环- 一行行往下走
    for (int j = 0; j < len; j++) {
        // 内循环-两两冒泡,把大的值冒到最后-确定下来排序完的一行的结果
        for (int i = 0; i < len - 1 - j; i++) {
            if (num[i] > num[i + 1]) {
                temp = num[i];
                num[i] = num[i + 1];
                num[i + 1] = temp;
            }
        }       
    }   
    return num;
}

相关推荐

ustbfym / 0评论 2019-11-02