目录

2. 算法 校招复习(持续更新~)

算法

算法复杂度的分析

时间复杂度

排序

术语铺垫

1. 稳定排序

如果 a 原本在 b 的前面,且 a == b,排序之后 a 仍然在 b 的前面,则为稳定排序。

2. 非稳定排序

如果 a 原本在 b 的前面,且 a == b,排序之后 a 可能不在 b 的前面,则为非稳定排序。

十大经典排序

简单排序

前言
两个 for 循环分别有什么作用?
  • 外层:控制排序轮数
  • 内层:控制每一轮里的每一个比较步骤
冒泡排序(必学)
核心思想

对相邻两个元素进行比较,如果左侧元素比右侧大/小,则交换元素,否则不交换;每一轮会将最小/大的元素“浮”到顶端,最终达到完全有序。

源码实现
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
private int[] bubbleSort(int[] arr) {
    // 外n-1 内n-i-1
    // 在第n-1轮的时候,只剩下一个元素没有位于有序区,但此时所有元素已经有序,所以总共遍历n-1轮
    for (int i = 0; i < arr.length - 1; i++) {
        // 内层用于遍历无序区
        // 每轮排序中:需要比较的元素个数比上一轮少一个
        // 即外层遍历i轮,无序区元素减少i个,所以内层应遍历n-i轮;
        // 又因为j+1可以遍历到最后一个元素,所以只需要遍历n-i-1轮(否则会数组越界),或者看成(n-1)-i来理解
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
            }
        }
    }
    return arr;
}
算法复杂度
  • 时间复杂度:O( n^2 )
优化

冒泡排序有个问题,是不管你是否原本就有序,都会进行循环比较。排序问题若原本就有序的元素序列就不需要排序了嘛~

针对这个问题,我们可以设一个临时变量来标记这个数组是否已经有序(在第一次循环的时候进行检查),如果有序就不用再遍历了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
private int[] bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        boolean isSorted = true;
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
                isSorted = false; // 若没有进判断条件则说明没有进行元素互换,也即数组已经有序,后面不需要继续遍历,isSorted值为true。
            }
        }
        if (isSorted) {
            break;
        }
    }
    return arr;
}
选择排序(必学)
核心思想

遍历元素集合,每次找(选择)最大/最小元素拎出来与无序区的第一个位置交换,如此循环,直到整个集合排序完成。

源码实现
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
private int[] selectSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int min = i;
        // 由于无序区的第一个元素一定会被比较,所以直接i+1开始即可
        for (int j = i + 1; j < arr.length; j++) {
            min = minIndex(arr, min, j);
        }
        swap(arr, i, min);
    }
    return arr;
}

public int minIndex(int[] arr, int min, int j) {
    return arr[min] < arr[j] ? min : j;
}
算法复杂度
  • 时间复杂度:O( n^2 )
直接插入排序(必学)
核心思想

跟打扑克牌时对扑克牌排序的道理是一样的。

  1. 随机选取序列里的一个元素作为待插元素(一般是无序区的第一个),与有序区的最后一个元素开始往前做比较;

    https://cdn.jsdelivr.net/gh/RebornQ/cdn.blog/img/reviews/%E7%9B%B4%E6%8E%A5%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E5%90%8E%E7%A7%BB%E5%85%83%E7%B4%A0%E7%A4%BA%E4%BE%8B1.png
    直接插入排序后移元素示例1

  2. 待插元素与第一个元素比较时,若比它大,则有序区的那个元素后移一位,为待插元素腾出空间,然后继续与下一个元素比较。如此反复,直到遇到不比它大的元素为止。如下图:

    https://cdn.jsdelivr.net/gh/RebornQ/cdn.blog/img/reviews/%E7%9B%B4%E6%8E%A5%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E5%90%8E%E7%A7%BB%E5%85%83%E7%B4%A0%E7%A4%BA%E4%BE%8B2.png
    直接插入排序后移元素示例2

  3. 然后在这个不比它大的元素的右边插入元素;

    https://cdn.jsdelivr.net/gh/RebornQ/cdn.blog/img/reviews/%E7%9B%B4%E6%8E%A5%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E5%90%8E%E7%A7%BB%E5%85%83%E7%B4%A0%E7%A4%BA%E4%BE%8B3.png
    直接插入排序后移元素示例3

  4. 重复步骤,直到序列有序。

源码实现
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
private int[] insertSort(int[] arr) {
    // 遍历无序区,默认第一个元素有序,从 1 开始
    for (int i = 1; i < arr.length; i++) {
        int sortingVal = arr[i];
        // 遍历有序区(0~i-1),找到插入位置;移动有序区,为插入元素挪出一个单元
        int j = 0;
        for (j = i - 1; j >= 0; j--) {
            // 待排序元素与有序区的每一个元素进行比较,如果遇到小于有序区的元素,则有序区的那个元素之后的所有元素后移一位,往前插入元素
            if (sortingVal < arr[j]) arr[j+1] = arr[j];
            else break;
        }
        // 插入元素,因为循环最后 j-- 了,所以插入位置是 j+1
        arr[j+1] = sortingVal;
    }
    return arr;
}
算法复杂度
  • 时间复杂度:O( n^2 )
    1. 对于 n 个元素,首先我的外层 for 循环要循环 n-1 次
    2. 内层 for 循环的循环次数是根据 i 来决定的,i = 1时,循环 1 次,i = 2,循环 2 次,…,i = n-1,循环 n-1 次,那总共加起来就是
      https://cdn.jsdelivr.net/gh/RebornQ/cdn.blog/img/reviews/%E7%9B%B4%E6%8E%A5%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E8%AE%A1%E7%AE%97.png
      直接插入排序时间复杂度计算
    3. 根据复杂度计算规则,保留高阶项,并去掉系数,那么时间复杂度为O( n^2 )

分治排序

归并排序(必学)
核心思想
源码实现
算法复杂度
快速排序(必学)
核心思想

快排的核心思想和归并排序一样也是分治法,分而治之

它的实现方式是每次从元素集合中选出一个基准值(也有叫中轴元素的),其他元素依次和基准值做比较,比基准值大的放右边,比基准值小的放左边,注意,此时基准值所处的位置是有序的;然后(通过递归的方式)再对左边和右边的元素集合分别选出一个基准值,进行同样的比较移动;重复步骤,直到最后都变成单个元素,整个集合就成了有序的序列了。

https://cdn.jsdelivr.net/gh/RebornQ/cdn.blog/img/reviews/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E6%B5%81%E7%A8%8B%E7%A4%BA%E4%BE%8B.png
快速排序流程示例
源码实现

通用代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
private int[] quickSort(int[] arr, int left, int right) {
    // 递归结束条件 left >= right
    if (left < right) {
        // 得到基准元素位置
        int pivotIndex = randomPartition(arr, left, right);
        // 根据基准元素,分成两部分进行递归排序
        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }
    return arr;
}
  1. 单边扫描法
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public int partition(int[] arr, int left, int right) {
    // 设定基准值,由于前面已经随机并且交换到序列头部,因此此处只需要选取头部位置即可
    int pivotIndex = left;
    int mark = left;    // 设置一个mark指针指向数列起始位置,表示 小于基准元素的区域边界
    // 从基准元素的下一个位置开始遍历数组
    for (int i = pivotIndex + 1; i <= right; i++) {
        if (arr[i] < arr[pivotIndex]) {  // 遍历到的元素小于基准元素,需做两件事
            mark++; // 1.mark指针右移一位,因为小于基准元素的区域边界增大了1
            swap(arr, mark, i); // 2.让最新遍历到的元素和mark指针所在位置的元素交换位置,因为最新遍历的元素要归属于小于pivot的区域
        }
    }
    // 最后把pivot交换到mark指针所在位置
    swap(arr, pivotIndex, mark);
    return mark;
}
  1. 双边扫描法
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
private int partitionV2(int[] arr, int left, int right) {
    // 设定基准值,由于前面已经随机并且交换到序列头部,因此此处只需要选取头部位置即可
    int pivotIndex = left;
    int start = pivotIndex + 1;  // 因为基准值元素是有序的,所以不需要比较
    int end = right;
    while (true) {
        // 从左往右扫描,找到第一个大于等于 基准值(pivot) 的元素位置
        while (start <= end && arr[start] <= arr[pivotIndex]) start++;
        // 从右往左扫描,找到第一个小于等于 基准值(pivot) 的元素位置
        while (start <= end && arr[end] >= arr[pivotIndex]) end--;
        // 左右指针相遇
        if (start >= end) break;
        // 交换左右数据,使得左边的元素不大于pivot,右边的不小于pivot
        swap(arr, start, end);
    }
    // 将基准值元素插入序列
    swap(arr, pivotIndex, end);
    return end;
}
算法复杂度
  • 时间复杂度:O(nlogn)
中轴选取方式

为了降低极端情况出现的可能性,我们可以随机选取主元,而不是固定一个位置选取。代码如下:

1
2
3
4
5
6
7
int randomPartition(int[] arr, int left, int right) {
    // 随机设定基准值
    int pivotIndex = (new Random()).nextInt(right) % (right - left + 1) + left;
    // 把基准值元素交换到序列头部,完成分治后再换回去
    swap(arr, left, pivotIndex);
    return partitionV2(arr, left, right);
}

分配排序

桶排序
基数排序

树状排序

堆排序(必学)
核心思想
源码实现
算法复杂度

其他

计数排序(必学)
核心思想
源码实现
算法复杂度
希尔排序

总结

用一张图汇总了10大排序算法的性质

https://cdn.jsdelivr.net/gh/RebornQ/cdn.blog/img/reviews/10%E5%A4%A7%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E7%9A%84%E6%80%A7%E8%B4%A8.jpeg
10大排序算法的性质

遍历/查找

二分法/分治法/二分查找

递归

其他

字符串匹配

朴素算法 Brute-Force

KMP 算法

位运算

简介

运算符含义例子注意事项
«左移0011 « 1 => 0110左移1位相当于乘以2,每移动一位数值增倍
»右移0110 » 1 => 0011右移1位相当于除以2,每移动一位数值减半
»>0填充的右移
(无符号右移)
1. 8 »> 2 => 2
2. -5 »> 3 => 536870911
3. -14 »> 2 ==> 1073741820
Java中int类型占32位;
正数右移,高位用0补;
负数右移,高位用1补;
当负数使用无符号右移时,用0进行部位
(自然而然的,就由负数变成了正数了)
&按位与
1. false & true => false
2. true & true => true
3. false & false => false
4. 0010 & 1001 => 0000
对于 a & b,
当 a 为 false 时,
仍需要判断 b 是否为 false
|按位或
1. false | true => true
2. true | true => true
3. false | false => false
4. 0010 | 1001 => 1011
对于 a | b,
当 a 为 true 时,
仍然需要判断 b 是否为 true
^按位异或
1. false ^ true => false
2. true ^ true => false
3. false ^ false => true
4. 0010 ^ 1001 => 0100
相同为 false,不同为true
(相同为0不同为1)
~按位取反0010 => 1101

常见面试题

假定 0 < x < 65535,那么计算 x*16 最好的方式是?(卓动2020秋招笔试真题)

位运算,x « 4(2^4 =16),可能需要判断一下边界

为什么 x 要小于 65535?

65535 = 2 ^ 16 - 1,同时 16 位系统,每个整数都是用 16 位 2 进制数来表示的,最大的数就是 16 个 1,所以 int 最大值就是 65535。