经典排序算法之冒泡排序的实现及优化( JAVA版)

一、排序思想

冒泡排序是一种典型的交换排序,类似于水中冒泡,较大的数沉下去,较小的数慢慢冒起来,假设从小到大,即为较大的数慢慢往后排,较小的数慢慢往前排。
冒泡排序的思想就是利用的比较交换,利用循环将第 i 小或者大的元素归位,归位操作利用的是对 n 个元素中相邻的两个进行比较,如果顺序正确就不交换,如果顺序错误就进行位置的交换。通过重复的循环访问数组,直到没有可以交换的元素,那么整个排序就已经完成了。

二、算法分析与图解

依次比较相邻的两个数,将比较小的数放在前面,比较大的数放在后面。
(1) 第一次比较:首先比较第一和第二个数,将小数放在前面,将大数放在后面。
(2) 比较第2个数和第3个数,将小数放在前面,大数放在后面。
.....
(3) 如此继续,直到比较到最后的两个数,将小数放在前面,大数放在后面,第一次比较完成。
(4) 第一次比较完成后,开始第二次比较,重复上述步骤,直至数组全部排序完成。
(5) 在上面一趟比较完成后,最后一个数一定是数组中最大的一个数,所以在比较第二趟的时候,最后一个数是不参加比较的。
(6) 在第二趟比较完成后,倒数第二个数也一定是数组中倒数第二大数,所以在第三趟的比较中,最后两个数是不参与比较的。
(7) 依次类推,每一趟比较次数减少一次

经典排序算法之冒泡排序的实现及优化( JAVA版)
演示动图
(图源网络,侵权请联系删除)

三、举例说明

举例,原始数组为 [60, 55, 41, 13, 25, 37, 23]

3.1 第一趟排序

比较次数 判定 结果
第1次比较  60和55比较,60大于55,所以交换位置 [55,60,41,13,25,37,23 ]
第2次比较  60和41比较,60大于41,所以交换位置  [55,41,60,13,25,37,23 ]
第3次比较  60和13比较,60大于12,所以交换位置  [55,41,13,60,25,37,23 ]
第4次比较  60和25比较,60大于25,所以交换位置  [55,41,13,25,60,37,23 ]
第5次比较  60和37比较,60大于37,所以交换位置  [55,41,13,25,37,60,23 ]
第6次比较  60和23比较,60大于23,所以交换位置  [55,41,13,25,37,23,60 ]

经典排序算法之冒泡排序的实现及优化( JAVA版)

3.2 第二趟排序

比较次数 判定 结果
第1次比较 41和55比较,55大于41,交换位置 [41,55,13,25,37,23,60 ]
第2次比较 55和13比较,55大于13,交换位置 [41,13,55,25,37,23,60 ]
第3次比较 55和25比较,55大于25,交换位置 [41,13,25,55,37,23,60 ]
第4次比较 55和37比较,55大于37,交换位置 [41,13,25,37,55,23,60 ]
第5次比较 55和23比较,55大于23,交换位置 [41,13,25,37,23,55,60 ]

经典排序算法之冒泡排序的实现及优化( JAVA版)

3.3 第三趟排序

比较次数 判定 结果
第1次比较 41和13比较,41大于41,交换位置 [13,41,25,37,23,55,60 ]
第2次比较 41和25比较,41大于25,交换位置 [13,25,41,37,23,55,60 ]
第3次比较 41和37比较,41大于37,交换位置 [13,25,37,41,23,55,60 ]
第4次比较 41和23比较,41大于23,交换位置 [13,25,37,23,41,55,60 ]

经典排序算法之冒泡排序的实现及优化( JAVA版)

3.4 第四趟比较

比较次数 判定 结果
第1次比较 13和25比较,13小于25,位置不变 [13,25,37,23,41,55,60 ]
第2次比较 25和37比较,25小于37,位置不变 [13,25,37,23,41,55,60 ]
第3次比较 37和23比较,37大于23,交换位置 [13,25,23,37,41,55,60 ]

经典排序算法之冒泡排序的实现及优化( JAVA版)

3.5 第五趟排序

比较次数 判定 结果
第1次比较 13和25比较,13小于25,位置不变 [13,25,23,37,41,55,60 ]
第2次比较 25和23比较,25大于23,交换位置 [13,23,25,37,41,55,60 ]

经典排序算法之冒泡排序的实现及优化( JAVA版)

3.6 第六趟排序

比较次数 判定 结果
第1次比较 13和25比较,13小于25,位置不变 [13,23,25,37,41,55,60 ]

经典排序算法之冒泡排序的实现及优化( JAVA版)

最终结果

排序完成后,数组排列如图所示:
经典排序算法之冒泡排序的实现及优化( JAVA版)

三、代码实现

/**
 * 冒泡排序
 * @param arr
 */
private static void bubbleSort(int[] arr) {
  if(arr==null || arr.length < 2 )
    return;
  for (int i = 0; i < arr.length - 1; i++) {
    for (int j = 0; j < arr.length - i -1; j++) {
      if (arr[j] > arr[j + 1]) {
        flag = true;
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

四、优化

冒泡排序的思想就是大的往上挪动,可是如果已经是一个排好序的数组,还需要继续冒泡吗?
答案肯定是不需要的,所以我们需要对其进行优化。
如果判定已经是一个有序数组,直接终止排序即可。

/**
 * 冒泡排序
 * @param arr
 */
private static void bubbleSort(int[] arr) {
  boolean flag = false;
  if(arr==null || arr.length < 2 )
    return;
  for (int i = 0; i < arr.length - 1; i++) {
    for (int j = 0; j < arr.length - i -1; j++) {
      if (arr[j] > arr[j + 1]) {
        flag = true;
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
    if(!flag)
      break;
    flag = false;
  }
}

上一篇:Linux下C连接MySql数据库


下一篇:Photoshop将美女图片打造质感咖啡色ELLE海报