1 / 22
文档名称:

面试时的java数据结构与算法word版.doc

格式:doc   大小:640KB   页数:22页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

面试时的java数据结构与算法word版.doc

上传人:精品小课件 2021/7/3 文件大小:640 KB

下载得到文件列表

面试时的java数据结构与算法word版.doc

相关文档

文档介绍

文档介绍:面试时的Java数据结构与算法
查找和排序算法是算法的入门知识,其经典思想可以用于很多算法当中。因为其实现代码较短,应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗,只要熟悉了思想,灵活运用也不是难事。一般在面试中最常考的是快速排序和归并排序,并且经常有面试官要求现场写出这两种排序的代码。对这两种排序的代码一定要信手拈来才行。还有插入排序、冒泡排序、堆排序、基数排序、桶排序等。
面试官对于这些排序可能会要求比较各自的优劣、各种算法的思想及其使用场景。还有要会分析算法的时间和空间复杂度。通常查找和排序算法的考察是面试的开始,如果这些问题回答不好,估计面试官都没有继续面试下去的兴趣都没了。所以想开个好头就要把常见的排序算法思想及其特点要熟练掌握,有必要时要熟练写出代码。
接下来我们就分析一下常见的排序算法及其使用场景。限于篇幅,某些算法的详细演示和图示请自行寻找详细的参考。
冒泡排序
冒泡排序是最简单的排序之一了,其大体思想就是通过与相邻元素的比较和交换来把小的数交换到最前面。这个过程类似于水泡向上升一样,因此而得名。举个栗子,对5,3,8,6,4这个无序序列进行冒泡排序。首先从后向前冒泡,4和6比较,把4交换到前面,序列变成5,3,8,4,6。同理4和8交换,变成5,3,4,8,6,3和4无需交换。5和3交换,变成3,5,4,8,6,,把最小的数3排到最前面了。对剩下的序列依次冒泡就会得到一个有序序列。冒泡排序的时间复杂度为O(n^2)。
实现代码:
/**
****@Description:冒泡排序算法实现
****@author 王旭
*/
public class BubbleSort {
public static void bubbleSort(int[] arr) {
if(arr == null || == 0)
return ;
for(int i=0; i) {
for(int j=-1; j>i; j--) {
if(arr[j] ]) {
swap(arr, j-1, j);
}
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
选择排序
选择排序的思想其实和冒泡排序有点类似,都是在一次排序后把最小的元素放到最前面。但是过程不同,冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。举个栗子,对5,3,8,6,4这个无序序列进行简单选择排序,首先要选择5以外的最小数来和5交换,也就是选择3和5交换,一次排序后就变成了3,5,8,6,,最终就会得到一个有序序列。其实选择排序可以看成冒泡排序的优化,因为其目的相同,只是选择排序只有在确定了最小数的前提下才进行交换,大大减少了交换的次数。选择排序的时间复杂度为O(n^2)。
实现代码:
/**
****@Description:简单选择排序算法的实现
****@author 王旭
*/
public class SelectSort {
public static void selectSort(int[] arr) {
if(arr == null || == 0)
return ;
int minIndex = 0;
for(int i=0; i//只需要比较n-1次
minIndex = i;
for(int j=i+1; j//从i+1开始比较,因为minIndex默认为i了,i就没必要比了。
if(arr[j] arr[minIndex]) {
minIndex = j;
}
}
if(minIndex != i) { /

最近更新

化工原料矿石运输合同 9页

人力资源部门如何优化人力资源管理流程 3页

人力资源部绩效考核指标库 4页

人力资源部的年终考核总结与评价6 5页

创意办公空间装饰设计 8页

人力资源部KPI指标库 4页

人力资源规划方案参考范文(6) 6页

农村办公楼装修合同范本 9页

人力资源绩效管理与激励机制总结 5页

写字楼项目部装修协议 9页

人力资源管理论文范本 5页

儿童医院全包装修合同样本 9页

人力资源管理的成功之道 5页

体育馆装修验收合作协议 9页

人力资源管理现状对策研究毕业论文(共5) 5页

人力资源管理对提高企业经济效益的作用 6页

亲子活动中心装修合同 9页

人力资源管理基本原则 4页

二零二五年度高端人才引进与培养招聘合作协议.. 7页

人力资源管理中的绩效评估与激励机制 4页

二零二五年度雏鸡养殖与农产品深加工合同 11页

二零二五年度镀锌协议品绿色包装及价格优惠合.. 10页

二零二五年度重型货车购销合同 11页

人力资源管理与组织能力 6页

人力资源管理(一)-第二章--员工激励。 6页

二零二五年度跨境矿山开采技术引进承包协议 9页

二零二五年度超市租赁合同(含装修改造费用协.. 8页

二零二五年度财税代理与税收争议解决服务协议.. 10页

人力资源总经理的主要工作职责(4) 6页

2025年吕梁职业技术学院单招职业适应性测试题.. 74页