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

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

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秒，冒泡排序基本就卡着不动了。。。。