算法 算法复杂度的分析 时间复杂度 排序 术语铺垫 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 ;
}
算法复杂度 优化 冒泡排序有个问题,是不管你是否原本就有序,都会进行循环比较。排序问题若原本就有序的元素序列就不需要排序了嘛~
针对这个问题,我们可以设一个临时变量来标记这个数组是否已经有序(在第一次循环的时候进行检查),如果有序就不用再遍历了。
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 ;
}
算法复杂度 直接插入排序(必学) 核心思想 跟打扑克牌时对扑克牌排序的道理是一样的。
随机选取序列里的一个元素作为待插元素(一般是无序区的第一个),与有序区的最后一个元素开始往前 做比较;直接插入排序后移元素示例1
待插元素与第一个元素比较时,若比它大,则有序区的那个元素后移一位 ,为待插元素腾出空间,然后继续与下一个元素比较 。如此反复,直到遇到不比它大的元素为止 。如下图:直接插入排序后移元素示例2
然后在这个不比它大的元素的右边插入元素;直接插入排序后移元素示例3
重复步骤,直到序列有序。
源码实现 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 )对于 n 个元素,首先我的外层 for 循环要循环 n-1 次 内层 for 循环的循环次数是根据 i 来决定的,i = 1时,循环 1 次,i = 2,循环 2 次,…,i = n-1,循环 n-1 次,那总共加起来就是直接插入排序时间复杂度计算 根据复杂度计算规则,保留高阶项,并去掉系数,那么时间复杂度为O( n^2 ) 分治排序 归并排序(必学) 核心思想 源码实现 算法复杂度 快速排序(必学) 核心思想 快排的核心思想和归并排序一样也是分治法,分而治之 。
它的实现方式是每次从元素集合中选出一个基准值 (也有叫中轴元素 的),其他元素依次和基准值做比较 ,比基准值大的放右边,比基准值小的放左边,注意,此时基准值所处的位置是有序的 ;然后(通过递归 的方式)再对左边和右边的元素集合分别选出一个基准值,进行同样的比较移动;重复步骤 ,直到最后都变成单个元素,整个集合就成了有序的序列了。
快速排序流程示例 源码实现 通用代码:
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
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
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 ;
}
算法复杂度 中轴选取方式 为了降低极端情况出现的可能性,我们可以随机选取主元,而不是固定一个位置选取。代码如下:
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大排序算法的性质
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。