面试常用算法(java)

1. 排序 1. 冒泡排序（O(n2)） 把最大的沉到最后，两两交换 public void bubbleSort(int[] nums) { // 外层循环控制排序的轮数 for (int i = nums.length - 1 ; i > 0; i--) { boolean isSorted = true; // 内层循环每次将未排序序列中最大的数冒泡到最后端 for (int j = 0; j nums[j+1]) { swap(nums,j,j+ 在IT行业的面试中，算法是衡量候选人技术能力的重要标准之一，尤其对于Java开发者来说，掌握常见算法至关重要。这里我们详细探讨几种在面试中常见的排序算法和链表操作。 1. **冒泡排序**：冒泡排序是一种简单的排序算法，其基本思想是通过两两比较相邻元素并交换位置，使得每一轮遍历后最大（或最小）的元素“浮”到数组的一端。时间复杂度为O(n^2)，其中n是数组长度。如描述中所示，冒泡排序包含一个外层循环控制排序轮数，一个内层循环进行两两比较并交换。 2. **快速排序**：快速排序是一种高效的排序算法，采用分治策略。它通过选取一个基准值，将数组分为两个部分，一部分所有元素小于基准，另一部分所有元素大于基准，然后对这两部分递归地进行快速排序。时间复杂度平均为O(nlogn)。在实现中，使用哨兵简化代码，避免边界条件判断。 3. **选择排序**：选择排序每次从未排序的元素中找到最小（或最大）的元素，放置到已排序序列的末尾，直到所有元素都排好序。时间复杂度同样为O(n^2)。选择排序的特点是交换次数较少，但比较次数较多。 4. **插入排序**：插入排序将当前元素插入到已排序序列的合适位置，使得插入后整个序列仍然有序。时间复杂度在最好情况（已排序）下为O(n)，最坏情况（逆序）为O(n^2)。插入排序对于小规模数据或部分有序的数据表现良好。 5. **二分插入排序**：二分插入排序是插入排序的一种优化，利用二分查找法确定插入位置，减少查找时间，使得时间复杂度降低到O(nlogn)。但实际的插入操作仍需O(n^2)的时间，因此总体时间复杂度仍为O(n^2)。 除了排序算法，链表操作也是面试中常见的问题： 1. **判断链表相交**：给定两个链表，判断它们是否在某个节点相交。可以使用双指针法，让两个指针分别从两个链表的头节点开始，如果链表相交，则最终会指向同一个节点。 2. **找到链表的交点**：如果两个链表相交，可以找到相交节点。通过同时遍历两个链表，当其中一个链表走到尽头，另一个链表的剩余部分就是相交部分，接着将两个链表的头节点连接起来，继续遍历即可找到交点。 3. **判断环**：检测链表中是否存在环。使用快慢指针，快指针每次前进两步，慢指针每次前进一步。如果链表有环，快慢指针最终会在环内相遇；如果没有环，快指针会先到达链表尾部。 4. **找到环的入口**：若已知链表有环，可以找到环的入口节点。快慢指针在相遇后，将快指针重置为头节点，慢指针保持在相遇点，之后两者同步前进，最终相遇的点即为环的入口。 这些算法在面试中常被用来测试候选人的逻辑思维、编程能力和对数据结构的理解。熟练掌握并能够灵活运用这些基础算法，对于提升面试成功率至关重要。