算法研究之—冒泡排序

原理:n个元素的数组:第一轮从头开始两两比较,如果前一个大于(或小于)后一个,则交换,然后比较下一个,直到最大的数(或最小的数)移到末尾。第二轮重复第一轮操作,比较的数目为比上轮少1(因为已经定位到1个最大值);继续比较直到比较的数据为0;

冒泡排序实现:

优化:因为在经过m(0<m<n)轮比较后,如果在新的一轮比较中无任何交换,说明数组已经是排好序的了,即可终止循环。

冒泡排序的时间复杂度为 o(n^2)

算法研究之—希尔排序

原理:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。由于希尔排序是对相隔若干距离的数据进行直接插入排序,因此可以形象的称希尔排序为“跳着插”

算法实现:

参考:图解排序算法(二)之希尔排序

算法研究之—插入排序

插入排序原理:插入排序的工作方式像许多人排序一手扑克牌.开始时,我们的左手为空并且桌子上的牌面向下.然后,我们每次从桌子上拿走一张牌并将它插入左手中正确的位置.为了找到一张牌的正确位置,我们从右向左将它与已在手中的每张牌进行比较,拿在左手中的牌总是排序好的. 

INSERTION-SORT 伪代码:

代码实现:

插入排序的时间复杂度为 o(n^2)。

参考:算法导论(原书第3版)

每个程序员都应该收藏的算法复杂度速查表

算法复杂度这件事

这篇文章覆盖了计算机科学里面常见算法的时间和空间的大 OBig-O 复杂度。我之前在参加面试前,经常需要花费很多时间从互联网上查找各种搜索和排序算法的优劣,以便我在面试时不会被问住。最近这几年,我面试了几家硅谷的初创企业和一些更大一些的公司,如 Yahoo、eBay、LinkedIn[……]

Read more

C++开发之—内存对齐

网络数据协议的定义:

WORD为两个字节,BYTE是一个字节,但是sizeof(tagInfo)大小却是4

在头文件的开头和结尾处分别设置,然后sizeof(tagInfo)的大小就为3了。

下面摘自网络:

内存对齐的原则以及作用?

  • 结构体内的成员按自身长度自对齐(32位机器上,如char=1,short=2,int=4,double=8),所谓自对齐是指该成员的起始地址必须是它自身长度的整数倍。如int只能以0,4,8这类地址开始。[……]

Read more

C++开发之—单例类的实现

单倒模式是一种常见的设计模式,在cocos2d很多地方都使用到。下面贴出来我的一种方式。

Utils.h

Utils.cpp

原理都是类似的,使用类的静态变量或全局的静态变量保存唯一实例。最重要一点:将构造与析构声明 为私有,防止外部创建对象,保持此类只有唯一一个实例 

QQ群:239759131 cocos 技术交流 欢迎您

C++研究之—C++11 新特性

总结C++11新特性的功能用法和注意事项

  • auto
    功能:类型说明符,用于自动获取表达式所属的类型
  • long long 类型
    C++语言规定,一个int至少和一个short一样大,一个long至少和一个int一样大,一个long long至少和一个long一样大
  • 列表初始化
    用花括号来初始化变量
  • 空指针 nullptr
    特殊类型的字面值,可以转换为任意指针类型;
    C++程序最好使用nullptr,尽量避免使用NUL[……]

Read more

C++研究之—virtual 解析

OO编程有三大特性:封装,继承,多态

在C++中,从绑定时间来看,可以分成静态多态和动态多态,也称为编译期多态和运行期多态。静态多态即函数重载,在同一类内相同的函数名,不同的参数列表。相对简单,现在重点分析动态多态。

虚函数

C++中的虚函数的作用主要是实现了多态的机制。关于多态,简而言之就是用父类型别的指针指向其子类的实例,然后通过父类的指针调用实际子类的成员函数。这种技术可以让父类的指针有“多种形态”,这是一种泛型技术。所谓泛型技术,说白了就是试图使用不变的代码来实现可变的算法。比如:模板技术,RTTI技术,虚函数技术,要么是试图做到在编译时决议,要么试图做到运行时决议。[……]

Read more

服务器开发之—Redis

Redis 教程

1.安装(Mac)

2.启动连接

3.关闭服务