排序算法

基于比较的排序

介绍

下面所介绍的几种算法都是基于比较的排序，所谓基于比较的排序，就是通过比较大小来决定位置，可以通过决策树来分析这个过程。

时间下界证明

对于任意的一颗决策树，叶子节点代表一次排序，故n个元素应该有n!个排序，即叶子节点为n!个，假设决策树高度为h，而对于一颗二叉树，节点树最多为2^h，故2^h >= n!，可以得出h >= lg(n!) = Ω(nlgn)。

leetcode第9题

  • 题目：Determine whether an integer is a palindrome. Do this without extra space.
  • 解析：判断一个数字是否是回文数，即如123321,98789类似的数字，首先负数不是回文数，以0结尾的非负数不是回文数，对于一般的非负数字，只需要将整个数字反转判断是否相等即可，但是一个int类型反转有可能会溢出，这里用到了一个技巧，即反转一半，如123321反转一般，剩下的为123，得到的为123，相等就是回文数字，对于12321，反转后为12，得到的是123，如何判断呢，只需要将得到的除以10就可以判断啦，若想等极为回文数，代码如下，运行时间60ms。

图相关

###1. 图的表示

  • 邻接矩阵：这种表示方式存储了每一个顶点，因此大小为$o(n^2)$,对于那些稀疏矩阵来说很浪费空间。
  • 邻接表：存储每一个顶点和其他顶点的关系时将其顶点按升序排列，可以快速定位至某一顶点。

STL之set，multiset

  • 头文件及声明
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    #include <set>
    namespace std
    {
        template <typename T,
                  typename Compare = less<T>,
                  typename Allocator = allocator<T>>
        class set;
        
        template <typename T,
                  typename Compare = less<T>,
                  typename Allocator = allocator<T>>
        class multiset;
    }

leetcode第8题

题目大意是实现自己的atoi函数，即将将字符串中的数字转换为int型，如果不能转换则将其转换为0，若超过整形范围。则以最大值或最小值保存。代码如下，运行时间12ms.ret保存的是结果，sign标记第一个字符是+或-，代码首先将i定位到第一个不是空格的位置，base保存了INT_MAX/10的结果，若ret>base了，则ret10必定大于INT_MAX，若ret=base，而INT_MAX-ret10 =7,则说明当前的字符不能大于7，否则就超过了最大整数.。