摘要:外层循环让内层循环继续排没有排序过的数组,排序过的不用再排。那么优化后的算法能快多少呢。我们都以数组长度为来计算传统冒泡排序步,优化后的冒泡排序步。因为优化后的冒泡排序,每排完一次,最后一个数已经是最大的,就不需要再比较了。
冒泡排序的时间用大O表示法是O(N^2).
传统的冒泡排序:
/** * @param total 要排序的数组长度 */ public void sort(int total){ int num[]; if(total <= 0){ System.out.println("请输入大于0的正整数"); }else{ num = new int[total]; for (int i = 0 ; i < total; i++){ //生成随机1到100之间的数 Random ra =new Random(); num[i] = ra.nextInt(100)+1; } System.out.println("要排序的数组为:" + Arrays.toString(num)); int sum = 0; int out,in; for (out = total - 1; out > 1; out--){ for (in = 0 ; in < out; in++){ sum ++; if(num[in] > num[in+1]){ int temp = num[in]; num[in] = num[in+1]; num[in+1] = temp; } } } // 最原始的冒泡排序 for(int i = 0; i < total -1 ; i ++){ for (int j = 0 ; j < total -1 ; j++){ sum ++; if(num[j] > num[j+1]){ int temp = num[j]; num[j] = num[j+1]; num[j+1] = temp; } } } System.out.println("排序完成的数组为:" + Arrays.toString(num)); System.out.println("总共用次数:" + sum); } }
优化过后的冒泡排序:
/** * @param total 要排序的数组长度 */ public void sort(int total){ int num[]; if(total <= 0){ System.out.println("请输入大于0的正整数"); }else{ num = new int[total]; for (int i = 0 ; i < total; i++){ //生成随机1到100之间的数 Random ra =new Random(); num[i] = ra.nextInt(100)+1; } System.out.println("要排序的数组为:" + Arrays.toString(num)); /**核心算法: * 双重循环,外层循环用于控制排多少次序。 * 内层循环从第一位开始一直往后比较,内层循环一次后,可以将最大的数至于末尾。 * 外层循环让内层循环继续排没有排序过的数组,排序过的不用再排。 */ int sum = 0; int out,in; for (out = total - 1; out > 1; out--){ for (in = 0 ; in < out; in++){ sum ++; if(num[in] > num[in+1]){ int temp = num[in]; num[in] = num[in+1]; num[in+1] = temp; } } } System.out.println("排序完成的数组为:" + Arrays.toString(num)); System.out.println("总共用次数:" + sum); } }
大家对比可以发现,就是外层循环的时候有点变化,其他的代码都是一模一样的。
那么优化后的算法能快多少呢。我们都以数组长度为10来计算:
传统冒泡排序:9x9=81步,
优化后的冒泡排序:9+8+7+6+5+4+3+2=44步。
因为优化后的冒泡排序,每排完一次,最后一个数已经是最大的,就不需要再比较了。
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/73305.html
摘要:二分查找法要查找的数数组长度设定的数组花了多少次找到最小值最大值当前猜的值打印猜的每个数找到了花了次如果猜的数大于选定的数,则把设为猜的数,否则把设为猜的数请输入大于等于的正整数且查找的数不能大于数组里最大的数调用方法执行结果找到了花了次 大O表示法使用大写字母O,可以认为其含义为order of(大约是)。我们可以使用大O法来描述线性查找使用了O(N)级时间,二分查找使用了O(log...
摘要:多练练排序算法,不仅能够让我们知道一些排序方法的底层实现细节,更能够锻炼我们的思维,提升编程能力。排序算法的稳定性一个稳定的排序,指的是在排序之后,相同元素的前后顺序不会被改变,反之就称为不稳定。 1. 导言 因为这是排序算法系列的第一篇文章,所以多啰嗦几句。 排序是很常见的算法之一,现在很多编程语言都集成了一些排序算法,比如Java 的Arrays.sort()方法,这种方式让我们可...
摘要:插入排序特殊从第二个元素开始,和第一个元素比较,如果满足排序的顺序,则交换顺序。优化后选择排序从第一个位置开始遍历待排序的元素,找到最小值和第一元素交换从位置开始往后遍历,找到之后元素中的最小值,和第个元素交换位置。 插入排序1、特殊:从第二个元素开始,和第一个元素比较,如果满足排序的顺序,则交换顺序。2、一般:把待比较和他之前的所有元素相比(从右往左),如果满足排序的顺序,这交换。 ...
阅读 2104·2023-04-25 18:49
阅读 1823·2019-08-30 14:02
阅读 2619·2019-08-29 17:24
阅读 3301·2019-08-28 18:10
阅读 2909·2019-08-28 18:03
阅读 454·2019-08-26 12:01
阅读 3291·2019-08-26 11:31
阅读 1355·2019-08-26 10:29