常见的加密算法、排序算法都需要自己提前了解一下，排序算法最好自己能够独立手写出来。
我觉得面试中最刺激、最有压力或者说最有挑战的一个环节就是手撕算法了。面试中大部分算法题目都是来自于Leetcode、剑指offer上面，建议大家可以每天挤出一点时间刷一下算法题。
推荐两个刷题必备网站：
LeetCode：
- LeetCode（中国）官网
- 如何高效地使用 LeetCode
牛客网：
- 牛客网首页
8.1 举个栗子（手写快排）
面试官可能会问你，了解哪些排序方法啊？除了冒泡排序和选择排序能不能给我手写一个其他的排序算法。或者面试官可能会直接问你：“能不能给我手写一个快排出来？”。
快排的基本思想： 通过选择的参考值将待排序记录分割成独立的两部分，一部分全小于选取的参考值，另一部分全大于选取的参考值。对分割之后的部分再进行同样的操作直到无法再进行该操作位置(可以使用递归)。
下面是我写的一个简单的快排算法，我选择的参考值是数组的第一个元素。
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] num = { 1, 3, 4, 8, 5, 10, 22, 15, 16 };
QuickSort.quickSort(num, 0, num.length - 1);
System.out.println(Arrays.toString(num));
}
public static void quickSort(int[] a, int start, int end) {
// 该值定义了从哪个位置开始分割数组
int ref;
if (start < end) {
// 调用partition方法对数组进行排序
ref = partition(a, start, end);
// 对分割之后的两个数组继续进行排序
quickSort(a, start, ref - 1);
quickSort(a, ref + 1, end);
}
}
/**
* 选定参考值对给定数组进行一趟快速排序
*
* @param a
* 数组
* @param start
* （切分）每个数组的第一个的元素的位置
* @param end
* （切分）每个数组的最后一个的元素位置
* @return 下一次要切割数组的位置
*/
public static int partition(int[] a, int start, int end) {
// 取数组的第一个值作为参考值（关键数据）
int refvalue = a[start];
// 从数组的右边开始往左遍历，直到找到小于参考值的元素
while (start < end) {
while (end > start && a[end] >= refvalue) {
end--;
}
// 将元素直接赋予给左边第一个元素，即pivotkey所在的位置
a[start] = a[end];
// 从序列的左边边开始往右遍历，直到找到大于基准值的元素
while (end > start && a[start] <= refvalue) {
start++;
}
a[end] = a[start];
return end;
}
// 最后的start是基准值所在的位置
a[start] = refvalue;
return start;
}
}
复制代码时间复杂度分析：
- 在最优的情况下，Partition每次都划分得很均匀，快速排序算法的时间复杂度为O(nlogn)。
- 最糟糕情况下的快排，当待排序的序列为正序或逆序排列时，时间复杂度为O(n^2)。
空间复杂度分析：
- 最好情况，递归树的深度为log2n，其空间复杂度也就为O(logn)
- 最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)。
一种简单优化的方式：
三向切分快速排序 ：核心思想就是将待排序的数据分为三部分,左边都小于比较值,右边都大于比较值,中间的数和比较值相等.三向切分快速排序的特性就是遇到和比较值相同时,不进行数据交换, 这样对于有大量重复数据的排序时,三向切分快速排序算法就会优于普通快速排序算法,但由于它整体判断代码比普通快速排序多一点,所以对于常见的大量非重复数据,它并不能比普通快速排序多大多的优势 。
关注我，私信回复“资料”，即可领取更多java架构资料！！
分享到:
