大家好,欢迎来到IT知识分享网。
冒泡排序的原理
冒泡排序的原理是从第一个数字开始,依次让相邻的两个数字进行比较,按照从大到小或从小到大的顺序进行交换(如果是升序排列就把小的放前面,如果降序排列就把大的放前面)。
第一趟比较后,就把最大的的数字放在最后一个位置(假设按照升序排列),然后进行第二趟比较,依次进行相邻数字比较,第二趟比较后次大的数字放在了倒数第二个位置。
进行n-1(n代表待排序的数字个数)趟比较后(最后只剩一个无需比较),数字即为有序排列。
图解展示冒泡过程
假设要排列的数字为 3 1 4 2 ,当进行第一趟排序时,如下图所示(其中i表示数组的下标)
第一趟排序执行完后,数组中最大的数字4已找到,并放在数组的最后一后位置,所以后续比较无需再跟最后一个比较。下面看第二趟排序过程,如下图
第二趟排序执行完,数组的次大数字3已找到,并放在数组的倒数第二的位置。此时由于我们选取的排列数据巧合,第三大的数字2也放在了倒数第三的位置,但按照我们比较逻辑,此时并不知道第三大数字已经找到,所以还会进行第三趟比较。如下图所示
按照我们的逻辑,当第三趟比较执行完后,第三大的数字2已找到并放在倒数第三位的位置。剩下最后一个数字1无需再比较它本身的位置就是它应该所在的位置。
我们可以发现,当有4个数字时,只需进行3趟排序即可将无序数字变为有序,而每趟比较都会比上一次少比较一次(因上一趟比较已经确定了一个较大数字位置)
另外,在我们例子中,第三趟比较前数字已经处于正确的序列,所以无需再进行后续比较(当然我们刚好只比较三趟,如果有5个或更多数字,则可以省去后续比较)
下面看一下具体代码实现
1 public static void bubbleSort(int array[]){ 2 int temp = 0; 3 for (int i = 0; i < array.length - 1; i++) { 4 //有n个数据,只需要n-1趟排序即可 5 boolean flag = true; 6 for(int j=0;j<array.length -1 -i ;j++){ 7 if(array[j] > array[j+1]){ 8 flag = false; 9 temp = array[j]; 10 array[j] = array[j+1]; 11 array[j+1] = temp; 12 } 13 } 14 if(flag){ 15 break; 16 } 17 } 18 }
代码分析
1)第一层for循环用于确定进行几趟比较,前面我们分析过,只需进行n-1趟比较即可
2)第二层for循环用于从第1个数字开始,依次跟相邻数字进行比较。每进行一趟比较后,就可少比较一位数字
3)在进行第二层循环比较时,设定一个标志位flag,用于标示是否进行了数字交换,如果一次都没有交换,说明此时数字已经有序,无需进行后续趟的比较
时间复杂度
冒泡排序嵌套两层循环进行排序,所以其时间复杂度为T(n)=O(n^2)。
测试执行时间代码
下面我们生成10万个随机数的数组,使用冒泡排序方法进行排序,看其执行时间。在我的后续文章中,会继续分享其他几种排序算法,并会在其他几种排序算法中也使用10万个随机数计算排序时间。
1 public static void main(String []args){ 2 int array[] = new int[100000]; 3 bubbleSort(array); 4 for(int i=0; i<100000; i++){ 5 array[i] = (int)(Math.random()*1000000); 6 } 7 long begin = System.currentTimeMillis(); 8 bubbleSort(array); 9 System.out.println("总耗时="+(System.currentTimeMillis()-begin)); 10 }
执行结果(单位为毫秒)
可以看出在我们机器上使用冒泡排序算法对10万条数据进行排序,大概需要17秒时间。下一篇我将分享选择排序算法,选择排序算法的执行时间是否会减小呢?一起期待吧!
总结
冒泡排序需要记住三点,一是比较的趟数n-1(最后一个数字无需比较),二是每进行一趟比较后就会确定一个较大的数字位置,后续趟的比较次数会少一次。还有一点是优化点,当在比较过程中数字的正确顺序已经产生后,无需再进行后续趟的比较。
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/32642.html