你还在用冒泡排序?学习从点滴开始(原创)_JAVA_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > JAVA > 你还在用冒泡排序?学习从点滴开始(原创)

你还在用冒泡排序?学习从点滴开始(原创)

 2015/4/15 15:23:56  学习从点滴开始  程序员俱乐部  我要评论(0)
  • 摘要:数组排序是大家经常遇到的问题,从面试,工作中各个情况遇到的时候很多,往往遇到排序,首先想到的是冒泡,可能冒泡排序的时间复杂性是O的两次幂,性能很差,对于小数组排序还算可以,但是大数据比较性能就不敢恭维了今天要给大家讲的是一个其他的办法-----------------------二分查找。。。思路是循环数组,每次循环到i的位置的时候,就认为i前面的数组是已经排序过的,然后将i对应的数值插入到i之前的位置,难点就是找到位置,每次选择i的二分之一的位置进行比较,快速定位,也就是说如果i是1024
  • 标签:原创 学习 冒泡排序

数组排序是大家经常遇到的问题,从面试,工作中各个情况遇到的时候很多,往往遇到排序,首先想到的是冒泡,可能冒泡排序的时间复杂性是O的两次幂,性能很差,对于小数组排序还算可以,但是大数据比较性能就不敢恭维了
??????????? 今天要给大家讲的是一个其他的办法-----------------------二分查找。。。思路是循环数组,每次循环到i的位置的时候,就认为i前面的数组是已经排序过的,然后将i对应的数值插入到i之前的位置,难点就是找到位置,每次选择i的二分之一的位置进行比较,快速定位,也就是说如果i是1024,那么只需要快速定位10次,而且是最糟糕的情况,查到i对应的位置k后,将(k-1)---- i 位置顺移,将i位置的数值放到k的位置,依次继续。。。。。直接上代码吧

class="java" name="code">package suanfa; 

import java.util.Random; 

public class WZGL { 

public static void main(String[] args) { 

int num = 100000; 

int intC[] = new int[num]; 

int value1=0; 

for (int i = 0; i < num; i++) { 
value1 += new Random().nextInt(num); 
intC[i] = value1; 
} 

int intA[] = new int[num]; 

System.arraycopy(intC, 0, intA, 0, num); 

long time1 = System.currentTimeMillis(); 
paixu(intC); 
long time2 = System.currentTimeMillis(); 


for (int i = 1; i < intA.length; i++) { 

int index = findIndex(intA[i], 0, i - 1, intA); 

int value = intA[i]; 

System.arraycopy(intA, index, intA, index + 1, i - index); 
intA[index] = value; 
} 

long time3 = System.currentTimeMillis(); 
System.out.println(time2 - time1); 
System.out.println(time3 - time2); 

} 

// 冒泡排序 
public static void paixu(int[] iaaa) { 

for (int i = 0; i < iaaa.length; i++) { 

for (int j = i + 1; j < iaaa.length; j++) { 
if (iaaa[j] < iaaa[i]) { 
int aa = iaaa[i]; 
iaaa[i] = iaaa[j]; 
iaaa[j] = aa; 
} 
} 
} 
} 

//二分查找排序 
public static int findIndex(int thisval, int from, int to, int[] thissz) { 

int index = 0; 

if (thissz[from] >= thisval) { 
index = from; 
return index; 
} 

if (thissz[to] <= thisval) { 
index = to + 1; 
return index; 
} 

if (to - from == 1) { 
return to; 
} 

int zhongjian = (to - from) / 2 + from; 

if (thissz[zhongjian] >= thisval) { 
return findIndex(thisval, from, zhongjian, thissz); 
} else { 
return findIndex(thisval, zhongjian, to, thissz); 
} 
} 

} 

?

100000条数据的性能比较:
5749
438

当然数据越大,越明显,测试过100万条数据的比较,二分查找大约40秒,冒泡排序基本就卡着不动了。。。。

?

发表评论
用户名: 匿名