Everyday , it gets a little easier .
- 快速排序（Quick Sort）
- 时间复杂度 O(nlogn) 空间复杂度O（logn） 不稳定 【两个时间复杂度O(nlogn) 的排序算法都不稳定】
- 时间复杂度：最坏O（n^2） 当划分不均匀时候 逆序and排好序都是最坏情况，最好O（n） 当划分均匀 partition的时间复杂度: O（n）一共需要logn次partition
- 空间复杂度：递归造成的栈空间的使用，最好情况，递归树的深度logn 空间复杂的logn，最坏情况，需要进行n‐1 递归调用，其空间复杂度为 O(n)，平均情况，空间复杂度也为O(log2n)。 由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。
- 插入排序（Insertion Sort）
- 时间复杂度O(n^2), 空间复杂度O(1)
- 排序时间与输入有关：输入的元素个数；元素已排序的程度
- 最佳情况，输入数组是已经排好序的数组，运行时间是n的线性函数； 最坏情况，输入数组是逆序，运行时间是n的二次函数
- 选择排序（Selection Sort）
- 时间复杂度O(n^2), 空间复杂度O(1)
- 排序时间与输入无关
- 最佳情况，最坏情况都是如此, 不稳定 如 {5,5,2}
- 归并排序 （Merge Sort）
- 时间复杂度 O(nlogn), 空间复杂度O(n) +O(logn)
- 排序时间与输入无关
- 最佳情况，最坏情况都是如此, 稳定
- 冒泡排序 (Bubble Sort)
- 时间复杂度O(n^2), 空间复杂度O(1)， 稳定，因为存在两两比较，不存在跳跃
- 排序时间与输入无关
- 最好，最差，平均都是O(n^2)
- 堆排序
- 时间复杂度 O(nlogn), 空间复杂度O(1). 从这一点就可以看出，堆排序在时间上类似归并，但是它又是一种原地排序，时间复杂度小于归并的O(n+logn)
- 排序时间与输入无关
- 最好，最差，平均都是O(nlogn). 不稳定
- 计数排序 (Counting Sort)
- 最好，最坏，平均的时间复杂度O(n+k), 天了噜， 线性时间完成排序，且稳定
- 优点：不需要比较函数，利用地址偏移，对范围固定在[0,k]的整数排序的最佳选择。是排序字节串最快的排序算法
- 缺点：由于用来计数的数组的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存
- 基数排序 (Radix Sort)
- 时间复杂度O（n） (实际上是O(d(n+k)) d是位数)
- 桶排序 (Bucket Sort)
- 平均时间复杂度为线性的 O(n+C) 最优情形下，桶排序的时间复杂度为O(n)
- 桶排序的空间复杂度通常是比较高的，额外开销为O(n+m)（因为要维护 M 个数组的引用）
- 桶越多，时间效率就越高，而桶越多，空间却就越大，由此可见时间和空间是一个矛盾的两个方面
关于稳定性：
选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法， 冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。 常用时间复杂度的大小关系：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)。
参考文章： 常用排序算法总结（性能+代码）
- 顺序查找 (Sequential Search）
- 时间复杂度：O(n)
- 优点：算法简单，对查找表的记录没有任何要求
- 缺点：效率低下
- 适用：数据量较少时的查找
- 二分查找/折半查找 （Binary Search）
- 时间复杂度：O(logn)
- 优点：比较次数少，查找速度快，平均性能好；
- 缺点：要求待查表为有序表，且插入删除困难。
- 适用：折半查找方法适用于不经常变动而查找频繁的有序列表。
- 插值查找 （Interpolation Search）
- 时间复杂度：O(logn)
- 适用：数据量较大，而关键字分布又比较均匀的查找表
- 斐波那契查找
- 时间复杂度：O(logn)
- 优点：平均性能要比折半查找好；
- 缺点：要求待查找的查找表必须顺序存储并且有序，且需满足条件：如果一个有序表的元素个数为n，并且n正好是（某个斐波那契数-1),时，才能用斐波那契查找法。
- 哈希查找
- 时间复杂度：O(1)
- 适用：数据本身是无法排序、无法比较