栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > 资讯 > 高等教育 > 考研政策

笔试时,冒泡排序也要写得优雅出众

笔试时,冒泡排序也要写得优雅出众

作者:三十六_

链接:https://www.jianshu.com/p/8abad5e9432b

导语

排序算法是笔试面试当中经常遇到的内容,之前参加的两个笔试都遇到了手写排序算法,可能大家都能写出来,但是要出众就要把代码优化一下,让人一看到就觉得你想的不简单。首先从最简单的冒泡排序开始,相信大家都能默出来,由于大部分人写的都一样,所以你要更出众的代码。

冒泡排序算法的步骤:

1.比较相邻的元素。如果第一个比第二个大,就交换他们两个。

2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。最后的元素应该会是最大的数。

3.针对所有的元素重复以上的步骤,除了最后一个。

4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

首先给出严格按照定义写的代码:

void bubbleSort(int array[], int length){ for (int i = 0; i < length; i++) { for (int j = 1; j < length - i; j++) { if (array[j-1] > array[j]) { swap(array[j-1], array[j]); } } }}

这里先给出交换函数,交换函数有很多种写法,最基本的写法是:

void swap(int &a, int &b) { int temp = a; a = b; b = temp;}

据说会在笔试中考不用中间变量交换两个数,网上有种写法:(其实这类方法还可已通过加减乘等代换方式实现,但都有一定弊端,虽然我们在平时的编程中不会这么写,不装X的话还是写第一种)

void swap(int &a, int &b) { a = a ^ b; b = b ^ a; a = a ^ b;}

但这种写法有个问题,当交换同一元素时,该元素会被置零,在选择排序中会有bug所以还是建议第一种写法,当然你也可以在里面加个判断:

void swap(int &a, int &b) { if (a != b) { a = a ^ b; b = b ^ a; a = a ^ b; }}

很明显上面的经典算法有些不足,当我们需要排序的数组基本有序时,上面的代码还会做出很多不必要的查找判断,降低了代码的执行效率。下面我们进行第一步优化,我们先定义一个标志flag,用来判断本次排序中是否发生交换,如果没有发生交换,说明排序已经完成,我们不需要再做不必要的循环判断,代码为:

void bubbleSort(int array[], int length) { bool flag = true;//判断是否发生交换 while (flag) { flag = false; for (int j = 1; j < length; j++) { if (array[j-1] > array[j]) { swap(array[j-1], array[j]); flag = true; } } length --; }}

对比下两种方法的比较大小次数:

第一种方法

第二种方法

由上图对比可见,第二种方法大大减少了对比的次数。

再做进一步优化,如果有数组前面几个是无序的,而后面的元素都已经是有序的,那我们就可以记录下无序的位置,下次排序判断时,只需要从数组头部遍历到该位置就可以了,这样可以省去遍历后面的元素,提高了代码的执行效率。代码为:

void bubbleSort(int array[], int length){ int flag = length; while (flag > 0) { int k = flag; flag = 0; for (int j = 1; j < k; j++) { if (array[j - 1] > array[j]) { swap(array[j - 1], array[j]); flag = j; } } }}

该方法和第二种的区别就是:先判断有没有交换,若有交换我也只遍历无序的区域。比较次数:

屏幕快照 2016-06-01 下午4.09.07.png

很明显比上面的少了很多次。

最后要说一句,冒泡排序写起来简单,相对于其他的排序算法效率比较低下,数据规模不大时,可以使用。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/news/1539474.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号