常用算法

1、数据结构

1.1、线性表

1.2、栈

1.3、队列

1.4、树

1.5、图

2、排序

2.1、插入排序（Insertion Sort）

• 算法思想：每趟将一个待排序的关键字，按照其值的大小插入到已经排好的部分序列中。
• 时间复杂度：O(n*n)
• 空间复杂度：O(1)

2.2、希尔排序（Shell Sort）

• 算法思想：将待排序的序列按按照增量规则划分为几个子序列，分别对这几个子序列进行插入排序，每趟排序中的增量逐渐缩小。
• 时间复杂度：O(n*logn)
• 空间复杂度：O(1)

2.3、冒泡排序（Bubble Sort）

• 算法思想：依次比较相邻元素并交换，直到一趟中没有元素进行交换。
• 时间复杂度：O(n*n)
• 空间复杂度：O(1)

2.4、快速排序（Quick Sort）

• 算法思想：以一个枢轴，将序列分为两部分，枢轴的一边比它小而另一边比他大。
• 时间复杂度：O(n*logn)
• 空间复杂度：O(logn)

2.5、选择排序（Selection Sort）

• 算法思想：从头至尾扫描序列，找出最小的记录与第一个记录交换，接着从剩下的记录中继续选择和交换，最终使序列有序。
• 时间复杂度：O(n*n)
• 空间复杂度：O(1)

2.6、堆排序（Heap Sort）

• 算法思想：将序列视为二叉树，并不断调整使之转变为符合堆定义的完全二叉树。
• 时间复杂度：O(n*logn)
• 空间复杂度：O(1)

2.7、归并排序（Merge Sort）

• 算法思想：将原始序列视为每个只含有单独1个元素的子序列，两两归并形成若干有序的二元组，不断对二元组进行归并完成排序。
• 时间复杂度：O(n*logn)
• 空间复杂度：O(n)

2.8、计数排序（Counting Sort）

2.9、桶排序（Bucket Sort）

2.10、基数排序（Radix Sort）

3、查找

3.1、二分查找

3.2、差值查找

3.3、Hash查找

• Hash函数：

常用算法

原文：https://www.cnblogs.com/cxc1357/p/9006196.html