文章标题

2019-11-14 09:03:33

字体：大中小

来源：转载

供稿：网友

***排序算法是平常面试中常见的，平时没有做过总结，所以就想着总结一下东西，写点博客，就不记笔记了，记了也没有时间去看他，所以就在博客上记录下来，忘得时候能查（说明》》默认是从小到大进行排列）***首先最经典的排序算法（便利默认从 0 开始进行便利）简单理解：冒泡排序的主要思想为对需要排序的数列进行扫描每次扫描找出最大的（或最小的）到两边的位置（即冒泡浮起到上面），经过一定的次数就可以使数列有序例如对数据量为n 的数列进行排序，需要 n-1 趟第j趟需要n-1-j次比较，最多需要 n-1-j 次交换，最少不交换。基本实现为（java实现）：public static void bubble_sort(int[] arr){ int len = arr.length; for(int i=0;i<=len-2;i++){ for(int j=0;j<=len-2-i;j++){ if(arr[j]>arr[j+1]){ int temp = 0; temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } for(int i:arr){ System.out.PRint(i+" "); } }**优化方向：从算法本身来说，由于比较趟数和每次比较需要比较得次数是无法进行优化的，所以优化的方向就只有从每趟交换的次数来进行想办法了，①：可以对该趟是否有数列进行交换为切入点如果该趟没有数交换，那么说明该数列已经有序，无需继续进行，②：可以对每趟最后交换的位置进行记录，以减少每次必须比较的次数（减少了比较的次数） ③：当然你可以把两种优化同时加上**

实现①：

// 优化一 public static void bubble_sort_1(int[] arr){ boolean noEXChange = true;// 记录改数列是否该趟没有数字交换 (默认没有数字交换) int len = arr.length; for(int i=0;i<=len-2;i++){ System.out.println("第"+(i+1)+"趟"); for(int j=0;j<=len-2-i;j++){ if(arr[j]>arr[j+1]){ // 有数字交换改变状态 noEXChange = false; int temp = 0; temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } // 检查该趟是否有数字交换如果没有的话，就跳出最外层循环 if(noEXChange){ break; } } for(int i:arr){ System.out.print(i+" "); } }

实现②：

上一篇：HDU - 3634 离散化

下一篇：疑问拾遗