Skip to content

Latest commit

 

History

History
86 lines (44 loc) · 5.02 KB

File metadata and controls

86 lines (44 loc) · 5.02 KB

算法

排序算法

常见排序算法有10种,这里借用一张图总结下:

十大排序算法总结

冒泡排序源码: BubbleSort

选择排序源码: SelectionSort

插入排序源码: InsertionSort

希尔排序源码: ShellSort

快速排序源码: QuickSort

归并排序源码: MergeSort

堆排序源码: HeapSort

基数排序源码: RadixSort

计数排序源码: CountingSort

查找算法

二分查找算法源码: BinarySearch

插值查找算法源码: InterpolationSearch

斐波那契查找算法源码: FibonacciSearch

双索引算法-快慢指针(leetcode)

双指针,指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向的指针进行扫描,从而达到相应的目的。

个人认为此算法就是充分利用数组有序这一特征,将本来需要两次遍历的操作简化为一次遍历,从而大大提高的程序的效率

下面用图来简单解释一下这个算法:

以leetcode第283题为例,需要看源码的小伙伴我会放链接在下方

首先我们定义两个指针,一个名为left,一个名为right

双指针算法图示

一开始left指针不动,right指针向后搜索,遇到一个非0的数字,将其覆盖到left指针位置上的元素,之后left指针的也向后移动

双指针算法图示

继续搜索,以不断的将非0元素往前挪,当right指针达到数组末端后,搜索结束。

可以看到,我们已经将所有非0元素都移动到数组的头部了,接下来对left+1位之后的元素全都赋值为0即可。

双指针算法图示

最终效果如下:

双指针算法图示

leetcode-283题: 移动零源码:MoveZero

leetcode-26题: 删除数组的重复项源码:DeleteDuplicate

leetcode-27题: 移除元素源码:RemoveElement

字符串匹配算法

暴力匹配算法源码: ViolenceMatch

kmp匹配算法源码: KMPMatch