快速排序的变种——快速选择算法
快速排序的变种——快速选择算法
给出一个数组,例如[1,4,2,6,8,3],现在要求出第 k 大的数字,即将数组从大到小排列,选择第k个数。用什么算法更快找到这个数?
最容易想到的就是先将数组排序,就可以很容易找到第 k 大的数字。就算用快速排序,时间复杂度为 O(nlgn)。有没有更快的算法?
Python 常用数据结构(列表,字典,元组,集合,序列,栈,队列)及方法
列表
insert
、remove
、sort
等方法只修改列表,不输出返回值——返回的默认值为 None
。这是所有 Python 可变数据结构的设计原则。
不是所有数据都可以排序或比较。例如,[None, 'hello', 10]
就不可排序,因为整数不能与字符串对比,而 None 不能与其他类型对比。
C++单例设计模式的两种实现
单例设计模式的两种实现
单例模式的定义
保证一个类仅有一个实例,并提供一个它的全局访问点,该实例被所有程序模块所共享。
那么就必须保证:
- 该类不能被实例化
- 该类不能被复制。
对于 C++,意味着:它的构造函数,拷贝构造函数和拷贝赋值运算符不能被公开调用。
静态库和动态库制作
什么是库
库文件是计算机上的一类文件,提供给使用者一些开箱即用的变量、函数或类。静态库和动态库,静态库和动态库的区别体现在程序的链接阶段:静态库在程序的链接阶段被复制到了程序中;动态库在链接阶段没有被复制到程序中,而是程序在运行时由系统动态加载到内存中供程序调用。
假设当前目录下有以下文件
├── main.c
├── tools.c
└── tools.h
C++ STL标准模版库总结
STL 的组成部分
模版是C++程序设计语言的一个重要特征,STL 正是基于这一特征,STL 具有强大的功能,同时兼具良好的可扩展性。
STL 分为 3 类:Algorithm(算法)、Container(容器)和Iterator(迭代器),容器和算法通过迭代器可以进行无缝地连接。
STL 由 6 部分组成:容器(Container)、算法(Algorithm)、 迭代器(Iterator)、仿函数(Function object)、适配器(Adaptor)、空间配制器(Allocator)。