冒泡排序实现与性能优化及JDK排序类分享
2017-01-23 本文已影响325人
阿_毅
开心一笑
【我现在出门都得带口罩，要不然就嗓子疼还咳嗽，想吸一口新鲜空气真的是太难了，估计以后纯净的空气得比红酒还值钱啊。那些有钱人出门都得背个空气瓶，见面就问：哎呦，王总啊，你的是几几年的空气啊？王总：“啊，我吸的是80年的”。我：“哦，那我比你强啊，我吸的是93年的”。王总：“哦，那，你那味咋样啊？”。我：“还行吧，要不你吸一口我这，尝尝”。所以说好好珍惜呼吸的机会吧。估计以后连喘气都费劲。】
唯美泡泡
提出问题
java中的冒泡排序以及JDK其他排序类学习???
解决问题
1.冒泡排序的简单介绍
8大经典算法中的经典的一个，可以实现对数组值得排序。小的值就像泡泡一样，在排序中不断的冒到顶端。网上有很多这方面的介绍，不多说。
2.冒泡排序Java实现
网上冒泡排序算法很多。冒泡排序在工作中，说实话用的比较少。但是，在面试中经常会问到。
package com.evada.de;
import org.junit.Test;
/**
* @Author 阿毅
* Created by Ay on 2016/01/21.
*/
public class Ay{
@Test
public void test(int[] arr){
// int [] arr = {3,2,1,4,5};
//定义临时变量
int temp;
//外层循环次数：总长度（arr.length） - 1
for(int i=0;i<arr.length-1;i++){
//外层每循环一次，内层循环依次减 1
for(int j=0;j<arr.length-i-1;j++){
if(arr[j+1]<arr[j]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
}
3.冒泡排序的性能分析和算法优化（外层循环优化）
对于这样的数组[2,1,3,4,5,6,7]，冒泡排序经过第一轮，已经变成有序的了，但是的冒泡还是要继续进行没有营养的两两比较，从而牺牲了时间。
由于冒泡排序的时间复杂度为O(n*n)。所以，当数据越多的时候越慢，非常不适合大数据的排序，所以我们测试的时候也是用的长度为800的随机数组。
解决方法：如果用一个flag来判断一下，当前数组是否已经有序，如果有序就退出循环，这样可以明显的提高冒泡排序的性能。
Java代码实现
package com.evada.de;
import org.junit.Test;
import java.util.*;
/**
* @Author 阿毅
* Created by Ay on 2016/01/21.
*/
public class Ay{
@Test
public void test(){
boolean flag = true;
int [] arr = {3,2,1,4,5};
//定义临时变量
int temp;
//冒泡趟数，n-1趟
for(int i=0;i<arr.length-1;i++){
for(int j=0;j<arr.length-i-1;j++){
if(arr[j+1]<arr[j]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag = true;
}
}
if(!flag){
break;//若果没有发生交换，则退出循环
}
}
System.out.println(Arrays.toString(arr));
}
}
4.冒泡排序第二种优化（内层循环优化）
记住最后一次交换发生位置的冒泡排序
package com.evada.de;
import org.junit.Test;
/**
* @Author 阿毅
* Created by Ay on 2016/01/21.
*/
public class Ay{
@Test
public void test(int[] arr){
int i = 0, j = 0;
//pos变量用来标记循环里最后一次交换的位置
int k = arr.length - 1,pos = 0;
//一共要排序size-1次
for (i = 0; i < arr.length - 1; i++){
//每次遍历标志位都要先置为0，才能判断后面的元素是否发生了交换
int flag = 0;
//选出该趟排序的最大值往后移动
for (j = 0; j <k; j++){
if (arr[j] > arr[j + 1]){
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
//只要有发生了交换，flag就置为1
flag = 1;
//循环里最后一次交换的位置 j 赋给pos
pos = j;
}
}
k = pos;
//判断标志位是否为0，如果为0，说明后面的元素已经有序，就直接return
if (flag == 0){
return;
}
}
}
}
5.JDK基本类型数组排序Arrays.sort
package com.evada.de;
import org.junit.Test;
import java.util.Arrays;
/**
* @Author 阿毅
* Created by Ay on 2016/01/21.
*/
public class Ay{
@Test
public void test(){
// 数组初始化
int[] a = { 3, 5, 2, 1, 8, 6, 9, 4, 0};
// 排序
Arrays.sort(a);
// 输出排序之后的结果
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
}
6.JDK中Collections.sort()实现排序第一种
第一种是list中的对象实现Comparable接口：
package com.evada.de;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* @Author 阿毅
* Created by Ay on 2016/01/21.
*/
public class Ay{
@Test
public void test(){
User user1 = new User();
user1.setName("a");
user1.setOrder(1);
User user2 = new User();
user2.setName("b");
user2.setOrder(2);
List<User> list = new ArrayList<>();
list.add(user2);
list.add(user1);
Collections.sort(list);
for(User user : list){
System.out.println(user.getName());
}
}
/**
* 根据order对User排序
*/
class User implements Comparable<User>{
private String name;
private Integer order;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getOrder() {
return order;
}
public void setOrder(Integer order) {
this.order = order;
}
public int compareTo(User arg0) {
return this.getOrder().compareTo(arg0.getOrder());
}
}
}
7.JDK中Collections.sort()实现排序第二种
第二种方法是根据Collections.sort重载方法来实现：
package com.evada.de;
import org.junit.Test;
import java.util.*;
/**
* @Author 阿毅
* Created by Ay on 2016/01/21.
*/
public class Ay{
@Test
public void test(){
User user1 = new User();
user1.setName("a");
user1.setPrice(11);
User user2 = new User();
user2.setName("b");
user2.setPrice(2);
Set<User> Hset = new HashSet<>();
Hset.add(user2);
Hset.add(user1);
List<User> list = new ArrayList<>();
list.addAll(Hset);
Collections.sort(list,new Comparator<User>(){
public int compare(User arg0, User arg1) {
//升序
return arg0.getPrice().compareTo(arg1.getPrice());
}
});
for(User u : list){
System.out.println(u.getName());
}
}
/**
* 根据order对User排序,无需实现Comparable接口
*/
class User {
private String name;
private Integer order;
private Integer price;
public Integer getPrice() {
return price;
}
public void setPrice(Integer price) {
this.price = price;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getOrder() {
return order;
}
public void setOrder(Integer order) {
this.order = order;
}
}
}
读书感悟
来自近藤麻理惠《怦然心动的人生整理魔法》
- 所谓整理，就是整理每一件物品的"过去"。
- 一旦把东西放进袋子里，就不会再使用了。
- 说的夸张一点，生而为人，对"什么能让自己心动"的判断是了解自己到底是一个怎样的人的重要线索。
- 如果是男女共用衣柜的情况，我的建议是男士的衣服放在上层，女士的衣服放在下层。摆放鞋子的时候，不管是男鞋还是女鞋都含有"支撑的基础"的意思，性质相同。所以，只需简单地把体积大、分量重的男鞋放在下层，女鞋放在上层就能保持平衡。
- 并不是"这个也扔，那个也扔"，而是"有选择地留下发光的东西，这才是理想生活的开端"。
- 无论丢弃物品还是拥有物品，都是为了让自己幸福。
- 教孩子折衣服，有助于培养他的整理习惯。
- 对有心动感的物品判断速度会很快，拿着物品的手指很柔软，看着物品的眼睛会闪闪发光。如果拿着没有心动感的物品，则双手会瞬间停止动作，还会摇头皱眉地作思考状，最后还会漫不经心地把物品扔到"留存处"。
- 为了珍惜真正富有价值的物品，必须首先丢弃已经完成了使命的物品。
- 真正的必需品肯定是能让自己幸福的东西，所以，应该积极地把必需品当作"心动物品"来对待。
- 凡是不符合"现在正使用""暂且需要""需要永存"这三项标准的文件，都应该毫不犹豫地全部丢掉。
- 珍惜物品，从某种程度上来说也是珍惜自己的一种表现。
经典故事
【一个佛陀在旅途中，碰到一个不喜欢他的人。连续好几天，好长一段路，那人用尽各种方法污蔑他。最后，佛陀转身问那人："若有人送你一份礼物，但你拒绝接受，那么这份礼物属于谁呢？"那人回答："属于原本送礼的那个人。"佛陀笑着说："没错。若我不接受你的谩骂，那你就是在骂自己？"那人摸摸鼻子走了。
启发：只要心灵健康，别人怎么想都影响不了我们。若我们一味地在乎别人的想法或说法，就会失去自主权。】
大神文章
【1】java实现冒泡排序
【2】冒泡排序优化版,性能近乎翻倍
【3】黑马程序员——冒泡排序的优化和选择排序
【4】冒泡排序算法及其两种优化
【5】Java中排序总结
【6】JDK7中的排序算法详解--Collections.sort和Arrays.sort
【7】JDK1.7 Collections.sort Arrays.sort发现的问题
【8】java List 排序 Collections.sort()
唯美泡泡
其他
如果有带给你一丝丝小快乐，就让快乐继续传递下去，欢迎点赞、顶、欢迎留下宝贵的意见、多谢支持！
