冒泡排序真的性能差吗
一个被人遗忘的排序算法-梳排序(combsort)
本质: 分组的冒泡排序。
先来看实现吧,基于冒泡排序和梳排序的一个直接对比
import java.util.Arrays; public class CombSort {//梳排序 基于冒泡排序的优化:分组冒泡排序 private static final CombSort opt = new CombSort(); public static void main(String[] args) { int[] arr = {2,1,2,5,4,3,3,6,7,8,6,5,4,3,5,2,1,2,5,4,3,3,6,7,8,6,5,4,3,5}; System.out.println("原数组:"+Arrays.toString(arr)); opt.bubbleSort(arr); System.out.println(Arrays.toString(arr)); int[] arr1 = {2,1,2,5,4,3,3,6,7,8,6,5,4,3,5,2,1,2,5,4,3,3,6,7,8,6,5,4,3,5}; opt.combSort(arr1); System.out.println(Arrays.toString(arr1)); } //冒泡排序 public void bubbleSort(int[] arr){//从小到大 int count = 0; for(int i=0;i<arr.length;i++){ for(int j=0;j<arr.length-i-1;j++){//时间复杂度O(n^2) (n-1)+(n-2)+...+2+1 = n(n-1)/2 等于n平方量阶 if(arr[j]>arr[j+1]){ arr[j] = arr[j] ^ arr[j+1]; arr[j+1] = arr[j] ^ arr[j+1]; arr[j] = arr[j] ^ arr[j+1]; count++; } } } System.out.println("bubbleSort交换次数:"+count); } //梳排序 /* * 分组冒泡 类比希尔排序:希尔排序基于插入排序实现, 梳排序基于冒泡实现 * 每次比较 i 和 i+j 以j跨步作冒泡排序 * j 数组长度每次除以1.3向下取整 * 同时设置一个标志位flag初始为true,每次进行内层判断时初始化false,只要内层进行了交换 * 说明当前的元素还没有排序好,所以设置flag为true继续循环 * */ public void combSort(int[] arr){ int step = arr.length; int count = 0; int count2 = 0; boolean flag = true; while (flag || step > 1){//step = 1 的时候 会做一次冒泡 只有在flagtrue时候才会执行 int i=0; flag = false; step = (step/1.3)>1?(int)(step/1.3):1; count2++; while(i+step<arr.length){ if(arr[i]>arr[i+step]){ arr[i] = arr[i] ^ arr[i+step]; arr[i+step] = arr[i] ^ arr[i+step]; arr[i] = arr[i] ^ arr[i+step]; flag = true; count++; } i++; } } System.out.println("combSort交换次数:"+count+";分组次数:"+count2); } }
冒泡排序性能之所以慢,是因为存在这样的一类问题
比如对数列 {9,8,7,6,5,4,3,2,1}进行升序排列
我们发现:
第一轮冒泡排序交换了 8次,结果{8,7,6,5,4,3,2,1,9}
第二轮冒泡排序交换了7次,结果{7,6,5,4,3,2,1,8,9}
第三轮冒泡排序交换了6次,结果{6,5,4,3,2,1,7,8,9}
........
最后经过8轮比较交换总共交换次数 8+7+6+5+4+3+2+1=36次
n个数据最大交换次数就是 (n-1)+(n-2)+...+3+2+1 = n(n-1)/2 ---->O(n^2) n平方量阶的时间复杂度,所以冒泡如果在数据很杂乱的情况下,时间消耗是很大的。
梳排序:梳排序的本质还是冒泡,只不过它对整个数列进行分组冒泡,可以类比希尔排序去理解
梳排序最终还是得进行一次完全的冒泡排序,但是呢在此前由于分组操作已经将元素基本上放好了,所以最后一次全体冒泡排序
我们看看梳排序对上述数列操作的效率
初始: step = length=9; flag = true;
判断:step>1,step如果=1说明内部做了一次完全冒泡排序了,那就没必要继续排了
第一次分组排序:
9>1;
flag = false;
step除以因子1.3,这个因子的选择只是为了让分组次数比较合适 并不是固定的 算法笔记这本书的介绍中,推荐了最合适的因子 1.3
step /1.3 --->6
进行组内冒泡排序 ----真正的分组 06,17,28 对三组分别冒泡
第一组:0 6号元素 也就是 9 3 冒泡:一次交换,排序后元素为{3,8,7,6,5,4,9,2,1}
第二组:1 7号元素 也就是 8,2 冒泡:一次交换,排序后元素为{3,2,7,6,5,4,9,8,1}
第三组:2 8号元素 也就是 7,1 冒泡:一次交换,排序后元素为{3,2,1,6,5,4,9,8,7}
最多只有8号元素 所以结束本次分组排序 总交换次数:3次 flag = true;
第二次分组排序:
6>1
6/=1.3--->4 flag = false;
进行组内冒泡排序---真正的分组:048,15,26,37 四组冒泡 对四组分别冒泡
以下是按照循环比较的逻辑:
第一组:0,4号元素,也就是3,5 不必交换
第二组:1,5号元素,也就是2,4 不必交换
第三组:2,6号元素,也就是1,9 不必交换
第四组:3,7号元素,也就是6,8 不必交换
第五组:4,8号元素,也就是5,7 不必交换
结束本次分组,总交换次数0 元素{3,2,1,6,5,4,9,8,7} flag = false;
第三次分组排序:
4>1 flag = false;
4/1.3---->3 真正的分组:036,147,258 三组 对三组分别冒泡
按照循环逻辑比较:
分组分别为 {0,3},{1,4},{2,5},{3,6},{4,7},{5,8}
对应元素为{3,6},{2,5},{1,4},{6,9},{5,8},{4,7}
结束分组,总交换次数0,元素{3,2,1,6,5,4,9,8,7} flag = false
第四次分组排序:
3>1 flag = false;
3/=1.3---->2 真正的分组:02468,1357 2组 对两组分别冒泡
按照循环逻辑比较:
分组分别为:
对应元素 一次交换结果
{0,2}---------------->{3,1}-------------------->{1,2,3,6,5,4,9,8,7} --->交换了一次
{1,3}---------------->{2,6}-------------------->{1,2,3,6,5,4,9,8,7}
{2,4}---------------->{3,5}-------------------->{1,2,3,6,5,4,9,8,7}
{3,5}---------------->{6,4}-------------------->{1,2,3,4,5,6,9,8,7}---->交换了一次
{4,6}---------------->{5,9}-------------------->{1,2,3,4,5,6,9,8,7}
{5,7}---------------->{6,8}-------------------->{1,2,3,4,5,6,9,8,7}
{6,8}---------------->{9,7}-------------------->{1,2,3,4,5,6,7,8,9}---->交换了一次
结束分组,总交换次数3 flag = true
此时其实已经排好序了
但是还会进行第五次分组,这是最后一次校验,进行一次完全冒泡,这时候已经不会再进行任何的交换了
step>1 flag =false
step/=1.3=1
完全冒泡分组:012345678 一组 flag = false
单个比较分组:01,12,23,34,45,56,67,78,89
总共交换次数才6次,远小于冒泡的36次交换,当数据很大的时候,这种性能差异会更明显 ===============================================================================================================================================
所以,咱们以后提到冒泡的时候,不要在说他性能差了。
良好的设计,也能够使冒泡排序有不亚于快排,希尔,桶排序等主流排序算法的性能。
记住这一个排序算法:
梳排序------分组冒泡排序