近5年常考Java面试题及答案整理（三）

发布时间：2020-12-24 14:06:24 所属栏目：交互来源：网络整理

导读：副标题#e# div id="article_content" class="article_content clearfix csdn-tracking-statistics" data-pid="blog" data-mod="popu_307" data-dsm="post" div id="content_views" class="htmledit_views" ?上一篇： 68、Java中如何实现序列化，有什么意义

答：冒泡排序几乎是个程序员都写得出来，但是面试的时候如何写一个逼格高的冒泡排序却不是每个人都能做到，下面提供一个参考代码：

> sort(T[] list,Comparator }

BubbleSorter > swapped = ( i = 1,len = list.length; i < len && swapped; ++ swapped = ( j = 0; j < len - i; ++ (list[j].compareTo(list[j + 1]) > 0 T temp = list[j] = list[j + 1 list[j + 1] = swapped = sort(T[] list,Comparator swapped = ( i = 1,len = list.length; i < len && swapped; ++ swapped = ( j = 0; j < len - i; ++ (comp.compare(list[j],list[j + 1]) > 0 T temp = list[j] = list[j + 1 list[j + 1] = swapped = }

95、用Java写一个折半查找。

答：折半查找，也称二分查找、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组已经为空，则表示找不到指定的元素。这种搜索算法每一次比较都使搜索范围缩小一半，其时间复杂度是O(logN)。

> binarySearch(x,x.length- 1 binarySearch(T[] x,T key,Comparator low = 0 high = x.length - 1 (low <= mid = (low + high) >>> 1 cmp = (cmp < 0 low= mid + 1 (cmp > 0 high= mid - 1 -1 > binarySearch(T[] x, low, (low <= mid = low + ((high - low) >> 1 (key.compareTo(x[mid])== 0 (key.compareTo(x[mid])< 0 binarySearch(x,low,mid - 1 binarySearch(x,mid + 1 -1 }

说明：上面的代码中给出了折半查找的两个版本，一个用递归实现，一个用循环实现。需要注意的是计算中间位置时不应该使用(high+ low) / 2的方式，因为加法运算可能导致整数越界，这里应该使用以下三种方式之一：low + (high - low) / 2或low + (high – low) >> 1或(low + high) >>> 1（>>>是逻辑右移，是不带符号位的右移）

（编辑：济南站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

13/13

首页

十个崛起的物联网职业	通过光伏能源驱动无电
中国移动初心向人民，	揭晓楼宇对讲防区控制