数组排序是大家经常遇到的问题,从面试,工作中各个情况遇到的时候很多,往往遇到排序,首先想到的是冒泡,可能冒泡排序的时间复杂性是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秒,冒泡排序基本就卡着不动了。。。。
相关推荐
3进一步改进的冒泡排序,如果在某次冒泡过程中,最后一次进行交换的位置为flag,则表示flag之后的序列已经有序,那么下一次冒泡就无需比较flag之后的序列,即只要比较到flag就可以结束此次冒泡过程。当flag=0时,...
js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序...
冒泡排序详解,简单而详细的讲清楚了,什么是冒泡排序。 冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首...
C语言冒泡排序C语言冒泡排序C语言冒泡排序
初学LabelView写的冒泡排序。 随机产生数组元素,并进行冒泡排序。
C++实现冒泡排序,多层次,快速实现排序算法
比如用冒泡排序将4、5、7、1、2、3这6个数排序。在该列中,第二趟排序结束后,数组已排好序,但计算机此时并不知道已经反排好序,计算机还需要进行一趟比较,如果这一趟比较,未发生任何数据交换,则知道已排序好,...
C++中的冒泡排序 C++中的冒泡排序C++中的冒泡排序C++中的冒泡排序C++中的冒泡排序 C++中的冒泡排序 C++中的冒泡排序 C++中的冒泡排序
直接插入排序 选择排序 堆排序 归并排序 快速排序 冒泡排序等七种排序方法
js冒泡排序,冒泡排序的工作原理,我们有一个未排序的数组arr = [ 1, 4, 2, 5, -2, 3 ]任务是使用冒泡排序对数组进行排序。 冒泡排序比较索引 0 中的元素,如果第 0 索引大于第 1 索引,则交换值,如果第 0 索引...
冒泡排序冒泡排序冒泡排序冒泡排序冒泡排序冒泡排序冒泡排序冒泡排序冒泡排序冒泡排序冒泡排序冒泡排序冒泡排序冒泡排序冒泡排序冒泡排序冒泡排序冒泡排序冒泡排序冒泡排序冒泡排序冒泡排序冒泡排序冒泡排序冒泡排序...
合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序的C语言实现,原创。
java冒泡排序代码,亲测能用,控制台输入数据,自动排序
冒泡排序法 程序 绝对原创 老师布置的作业,绝对原创,欢迎大家下载
实验3 冒泡排序程序
VerilogHDL/VHDL开发之Verilog实现冒泡排序
C语言 冒泡法排序 C语言 冒泡法排序 C语言 冒泡法排序 C语言 冒泡法排序 C语言 冒泡法排序 C语言 冒泡法排序
冒泡排序和快速排序的时间性能 冒泡排序和快速排序的时间性能 冒泡排序和快速排序的时间性能 冒泡排序和快速排序的时间性能 冒泡排序和快速排序的时间性能
数据结构(c语言版)严蔚敏 吴伟民编著 中直接插入排序、折半排序、shell排序、冒泡排序、快速排序、选择排序、堆排序的实现、归并排序,使用c语言实现
选择排序、插入排序、冒泡排序以及快速排序和归并排序的C语言实现,绝对可用