数据结构:链表、二叉树、并查集、图等
算法:排序算法、贪心算法、递归—动态规划、单调栈、滑动窗口、KMP、bfprt、Manacher、Morris、线段树等
时间复杂度和空间复杂度是计算算法效率的两个重要指标。
时间复杂度:时间复杂度(Time Complexity)是衡量算法执行时间随输入规模增长而增长的度量。 它表示算法执行所需的时间与问题规模之间的关系。通常用大O符号(O)来表示时间复杂度。(通俗的说就是判断一个算法流程做了多少次常数操作)
常见的时间复杂度有:
O(1):常数时间复杂度,表示算法的执行时间是一个常数,与输入规模无关。
O(logN):对数时间复杂度,表示算法的执行时间与输入规模的对数成正比。
O(N):线性时间复杂度,表示算法的执行时间与输入规模成正比。
O(N^2):平方时间复杂度,表示算法的执行时间与输入规模的平方成正比。
O(2^N):指数时间复杂度,表示算法的执行时间以指数方式增长。
空间复杂度:空间复杂度(Space Complexity)是衡量算法所需的额外空间随输入规模增长而增长的度量。它表示算法执行所需的额外空间与问题规模之间的关系。也使用大O符号(O)来表示空间复杂度。(通俗的说就是判断一个算法流程需要开辟多少的内存空间)
常见的空间复杂度有:
O(1):常数空间复杂度,表示算法的执行所需的额外空间是一个常数,与输入规模无关(有限几个变量)。
O(N):线性空间复杂度,表示算法的执行所需的额外空间与输入规模成正比(一个等长的数组)。
O(N^2):平方空间复杂度,表示算法的执行所需的额外空间与输入规模的平方成正比。
数组中相邻两个元素依次比较大小,如果满足条件(前一个元素大于或小于后一个元素),就进行交换,进行完一轮后就可以确定一个位置的最终位置,进行完N
轮后整个数组就做到有序。
要求数组最后为升序排列
eg: 原数组:5、8、6、3、9、2、1、7
第一轮:5、6、3、8、2、1、7、9
第二轮:5、3、6、2、1、7、8、9
第三轮:3、5、2、1、6、7、8、9
因为要进行N
轮比较,每轮又需要N
级别(N-1、N-2、N-3......)比较交换,所以冒泡排序的时间复杂度为O(N^2)
只需要用到有限几个额外变量就可以完成交换,所以冒泡排序的空间复杂度为O(1)
因为相邻元素两两交换排序,有相同值的元素的相对位置不会改变,所以冒泡排序具有稳定性
。
冒泡排序代码在Sort/BubbleSort.java
声明一个最小(大)值的变量,初始值为这轮中的初始位置(从一个数组的首位置或末位置开始),检索这一轮中的每一个数,通过比较(大于或小于这轮循环的最小(大)值的变量)进行标记,这轮比较之后,这轮最小(大)值就被这个变量标记上,然后和初始位置进行交换,最后就确定的下来一个位置的值,经过N
轮这样的比较后,整个数据变有序。
eg:
要求数组最后为升序排列
原数组:5、8、6、3、9、2、1、7
第一轮:1、8、6、3、9、2、5、7 最终被标记的元素为1
第二轮:1、2、6、3、9、8、5、7 最终被标记的元素为2
第三轮:1、2、3、6、9、8、5、7 最终被标记的元素为3
要进行N
轮比较,每轮又需要N
级别(N-1、N-2、N-3......)比较标记,所以选择排序的时间复杂度为O(N^2)
只需要用到有限几个额外变量就可以完成标记和交换,所以选择排序的空间复杂度为O(1)
因为每轮会对最小(大)的值进行标记,如果有比相同值的元素的数值更低(且是这轮中的最小元素)的元素,那么相同值的元素的相对位置就会改变,例:(3 3 5 3 3 1 1 3),所以选择排序不具备稳定性
选择排序代码在Sort/SelectionSort.java
从数据的某个位置进行插入,然后向前(下标比这个位置小的位置)看,这个位置的元素和与这个位置相邻的前面元素满足排序要求(如这个位置前面还有元素并且这个元素大于这个位置的元素)的话,就进行交换,然后继续向前看,直到这个位置元素之前所有的元素都满足排序所要求的条件。
eg:
要求数组最后为升序排列
原数组:5、8、6、3、9、2、1、7
第一轮:5、8、6、3、9、2、1、7 第一个元素插入往前看
第二轮:5、8、6、3、9、2、1、7 第二个元素插入往前看
第三轮:5、6、8、3、9、2、1、7 第三个元素插入往前看
第四轮:3、5、6、8、9、2、1、7 第四个元素插入往前看
要进行N
轮插入,每轮又需要N
级别(N-1、N-2、N-3......)比较标记,所以插入排序的时间复杂度为O(N^2)
只需要用到有限几个额外变量就可以完成标记和交换,所以插入排序的空间复杂度为O(1)
插入排序也相当于相邻元素两两交换排序,不会有跳跃的情况,有相同值的元素的相对位置不会改变,所以插入排序具有稳定性
。
插入排序代码在Sort/InsertionSort.java
将待查找的元素与数组中间的元素进行比较,如果中间元素等于待查找元素,则返回找到的位置;如果中间元素大于待查找元素,则在左半部分继续查找;如果中间元素小于待查找元素,则在右半部分继续查找。通过不断缩小查找范围,最终可以找到目标元素或者确定目标元素不存在。
因为将数据进行二分化,每次比较都将数组的规模减半,所以时间复杂度为O(logN)
只用到了几个有限变量,空间复杂度为O(1)
因为后面排序需要二分的**,所以二分查找是后面一些算法的**基础。
二分查找的代码和题目在Sort/BSExist.java
简单的来说归并排序的中心**就是:将一个数组等量的分割为左右两部分(二分**),然后分别让数组的左边排好序,右边排好序,最后左右两边合并成一个有序数组。
eg:
要求数组最后为升序排列
原数组:5、8、6、3、9、2、1、7
将数组分为左右两部分
左边:5、8、6、3
右边:9、2、1、7
左边排好序为:3、5、6、8
右边排好序为:1、2、7、9
左部分右部分比较合并
第一次:1
第二次:1、2
第三次:1、2、3
第四次:1、2、3、5
......
整体`merge`有序:1、2、3、5、6、7、8、9
因为归并排序主要是由递归算法实现的,所以这里判断归并排序的时间复杂度我们使用master
公式。
归并排序算法中,等规模的子问题发生了2
次,a=2。
子问题为N/2
规模的,b=2。
合并子问题的时间复杂度为O(N)
d=1。
根据master
公式结论log(a,b)=d 得出归并排序的时间复杂度为O(N * logN)
归并排序中使用了N
规模的数组,所以额外空间复杂度为O(N)
归并排序算法具备排序稳定性。
插入排序代码在Sort/MergeSort.java
快排的中心**就是将数组分成为左中右三个部分(荷兰国旗问题),左边为小于划分值(随机数组中一个数),中间为等于划分值,右边为大于划分值的数,第一次划分完毕,然后让左侧和右侧范围内继续划分(递归),最后整体有序。
eg:
要求数组最后为升序排列
原数组:5、8、6、3、9、2、1、7
随机以6为划分值
第一次完整划分完毕后为:
5、1、2、3、6、9、7、8
可以看出第一次完整划分后数组左边为小于6的,右边为大于6的
然后同样方法递归划分左部分和右部分,最后就能得到有序数组。
当测试快排数据量足够大时候,数学概率证明随机数快排时间复杂度为O(N * logN)
每次划分数据都需要开辟O(1)的空间,大约需要划分O(logN)次,所以额外空间复杂度为O(logN)
随机快速排序不具备稳定性
快速排序代码在Sort/QuickSort.java
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。
基本**:
- 将待排序的数列构造成一个大(小)根堆,数列的最大值为根节点
- 依次将根节点与待排序序列的最后一个元素交换
- 再维护从根节点到该元素的前一个节点为最大堆,如此往复,最终得到一个递增序列。
对于N个元素的数列排序,最坏情况下每个节点需要比较log(N)次来进行维护,所以堆排的时间复杂度为O(N*log(N))
堆排序过程中,只需要了几个有限的变量,所以堆排的额外空间复杂度为O(1)
因为过程中需要依次将根节点与待排序序列的最后一个元素交换
,易得堆排不具备排序稳定性
堆排序代码在Sort/HeapSort.java
不基于比较的排序
计数排序是一种不基于比较排序算法,适用于已知待排序元素范围的情况。它的基本**是统计每个元素出现的次数,然后根据元素的计数信息将它们放回原数组中的正确位置
eg:
要求数组最后为升序排列
原数组:0、5、7、3、3、0、2、5
计数数组:2、0、1、2、0、2、0、1
计数数组中的索引值就相当于一个桶,每个值就是桶里有多少个相同的数据,最后将这些桶里的数据倒出来就可做到有序
计数排序时间复杂度为 O(N)
额外空间复杂度为O(N)
计数排序代码在Sort/CountSort.java
基数排序是根据数组中最大数的位数来模拟的几次入桶出桶,同时也有个长度为10的计数器,来给每一次入桶计数,完成了几次的入桶出桶,数组整体就会有序。
eg:
要求数组最后为升序排列
原数组:013、021、011、052、062
count数组:0、2、4、5、5、5、5、5、5、5
辅助数组:021、011、052、062、013
首先在数组中找到最大值,来确定入桶出桶的次数。
创建一个长度为10的计数数组,创建一个辅助数组。
为数组中元素某位的数进行计数到计数数组当中去,并且变成前缀和。
从数组最右边的元素开始入桶,例如上图中,062为最右边的数,个位数是2,定位到count的数组下标为2的元素,元素减去1的值为3,为元素在辅助数组中的下标,然后倒数第二的元素,052,个位数为2,定位到count的数组下标为2的元素,元素减去1的值就变成2,为元素在辅助数组中的下标,就这样遍历一轮,完成一次入桶。
完成已经确定的入桶出桶的次数后,最后就排好了序。
基数排序的时间复杂度为O(N)
,额外空间复杂度为O(N)
基数排序的代码在Sort/RadixSort.java