关灯
开启左侧

冒泡排序(三种实现方案思路与实现)

[复制链接]
doubleyong 发表于 2019-2-16 11:34:43 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
 
本帖最后由 doubleyong 于 2019-2-16 12:12 编辑

1、第一种是最简单的方法,不用考虑性能问题:

比较相邻的元素。如果第一个比第二个大(升序),就交换他们两个。
对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
针对所有的元素重复以上的步骤,除了最后一个。
持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
所以设置一个外循环控制每次比较的此时。内循环进行比较,如第一次外循环也就是第一个元素需要比较n-1次,每次都是前一个和后一个比较,所以内循环每次只需要比较外层的前一个。
  1. public static int[] sort(int[] ins){
  2.     boolean flag = true;      
  3.         for(int i=ins.length-1; i>0; i--){
  4.             for(int j=0; j<i; j++){//每次到达最后一个i下标的前一个,然后和后一个比较
  5.                 if(ins[j]>ins[j+1]){
  6.                     int temp = ins[j+1];
  7.                     ins[j+1] = ins[j];
  8.                     ins[j] = temp;
  9.                 }
  10.             }
  11.         }
  12.     return ins;
  13. }
复制代码


第二种:如果这个序列是一个有序的,那么此时不用每个都进行比较,一旦比较的中间一次没有交换数据,说明这个序列已经是有序了。所以可以设置一个标志位。一旦一个循环比较没有交换,将标志位设置为false,跳出循环。
  1. public static int[] sort2(int[] ins){
  2.         boolean flag = true;
  3.         int length = ins.length-1;
  4.         while(flag){
  5.             flag = false;
  6.                 for(int j=0; j< length; j++){
  7.                     if(ins[j]>ins[j+1]){
  8.                         int temp = ins[j+1];
  9.                         ins[j+1] = ins[j];
  10.                         ins[j] = temp;
  11.                         flag = true;
  12.                     }
  13.                 }
  14.             length --;
  15.         }  
  16.         return ins;   
  17.     }
复制代码
第三种:如果有10万个数据需要进行冒泡排序,那么这个时候如果只有前面200个是无序的,后面的都是有序,而且都比前面200个无序的大。所只需要比较前面200然后排好序就可以了,上面的这种方法其实前面200个排好序后也就停止了,因为再排序就会跳出循环,但是上面的那种方法每次一个比较都要和200后面的数据进行比较。其实只需要比较前面200个数据就可以了。这样比较后面的数据就会带来时间的问题。所以我们每次排序都找到一个节点,这个节点的后面的数据就是已经排好了,不用比较的数据。
  1. public static int[] sort3(int[] ins){
  2.     int flage = ins.length-1;
  3.     while(flage>0){
  4.         int k = flage;//k来记录遍历的尾边界
  5.         flage=0;
  6.         for(int i=0; i<k; i++){
  7.             if(ins[i] > ins[i+1]){
  8.                 int temp = ins[i+1];
  9.                 ins[i+1] = ins[i];
  10.                 ins[i] = temp;
  11.                 flage = i;//每次比较后将边界值重新设定,如果比较过程中没有执行这一行语句,说明已经完成了排序,和第二种方法一样
  12.             }
  13.         }
  14.     }
  15.     return null;   
  16. }
复制代码

  1. long t1 = System.currentTimeMillis();
  2. int[] ins2 = sort1(ins);
  3. System.out.println(System.currentTimeMillis()-t1);
  4. long t2 = System.currentTimeMillis();
  5. int[] ins3 = sort2(ins);
  6. System.out.println(System.currentTimeMillis()-t2);
  7. long t3 = System.currentTimeMillis();
  8. int[] ins4 = sort3(ins);
  9. System.out.println(System.currentTimeMillis()-t3);
复制代码
这个是三个分别的运行结果(这个是运行时间):
35
1
0

---------------------
作者:疯狂1024
来源:CSDN
原文:https://blog.csdn.net/qq_28081081/article/details/80591527
版权声明:本文为博主原创文章,转载请附上博文链接!

 
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

排行榜
关闭

站长推荐上一条 /1 下一条

官方微信

全国服务热线:

400-0708-360

公司地址:国家西部信息安全产业基地(成都市高新区云华路333号)

邮编:610000    Email:2908503813@qq.com

Copyright   ©2015-2016  EOIT论坛Powered by©Discuz!    ( 蜀ICP备11000634号-7 )