排序算法
稳定排序:(N是数组长度，K是不同键值的数量)
| 名称 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| bubble | \(O(N^2)\) | \(O(1)\) | 比较相邻的两个元素，每次将当前排列中最大的元素冒泡到最后 |
| Cocktail | \(O(N^2)\) | \(O(1)\) | 双向的冒泡排序 |
| insertion | \(O(N^2)\) | \(O(1)\) | 在一个有序数组中，插入一个给定的数到指定位置 |
| bucket | \(O(N)\) | 需要\(O(K)\)的额外空间 | 将数组分到有限数量的桶中，每个桶在分别排序，非比较排序，适合海量的均匀分布数据排序 |
| merge | \(O(NlogN)\) | 需要\(O(N)\)的额外空间 | 将两个（或两个以上）有序表合并成一个新的有序表 |
| binary tree | 期望时间\(O(NlogN)\)，最坏\(O(N^2)\) | \(O(N)\) | 二叉搜索树,左子树的所有结点值小于根结点 ,右子树所有结点值大于根结点,左右子树分别为二叉搜索树 |
不稳定排序:
| 名称 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| selection | \(O(N^2)\) | \(O(1)\) | 每次从待排序数据中选出最大/小的元素，放在序列的起始位置 |
| shell | \(O(NlogN)\) | \(O(1)\) | 插入排序的一种，也称缩小增量排序 |
| heapsort | \(O(NlogN)\) | \(O(1)\) | 利用堆积树，是选择排序的一种 |
| quicksort | 期望时间\(O(NlogN)\)，最坏\(O(N^2)\) | \(O(1)\) | 适合于大的，乱数列表;将数据分成两部分,一部分的所有数据比另一部所有数据都要小,递归排列,直到整组数据有序 |
算法题
1 大整数加、减、乘、除、求模运算实现 2 很多整数，找其中出现次数最多的那个数 3 单链表翻转（两个指针如何实现）、查找、删除、插入以及双向链表、有序链表合并 4 判断一个整数是否是2的整数次幂.(n&(n-1)) 5 二分查找（注意边界条件） 6 常见排序算法的实现以及稳定性（快排跟归并考的很多） 7 字符串翻转（O(n)）、匹配（KMP算法） 8 最长递增子序列（nlogn的算法） 9 链表判断是否有环，环的入口，两个链表是否相交（快慢指针）。 10 指定一个数组，求2个数的和等于指定的和（某一个数），如果是3,4,5，n个等于个的和（某一个数）呢？（可以看作背包问题） 11 跳台阶问题
参考链接
排序算法11