0%

​ 堆排序像合并排序一样,时间复杂度为$O(nlogn)$;像插入排序一样,是一种原地排序(在任何时候只有常数个元素存储在数组外)。

阅读全文 »

分治法:将原问题划分为n个规模较小而结构与原问题相似的子问题;递归地解决这些子问题,然后再合并其结果,就得到了原问题的解。分治法在每一个递归上都有三个步骤:分解、解决、合并。而在本文中的合并排序法正是运用了这种分而治之的策略:把一个n个元素的数组先分成两个数组,然后继续分下去,知道分成n个数组;然后将其逐一合并排序,最终得到排列好了的数组。下面我们首先看一看合并排序了原理框图:(图中黑色部分看不见不要紧,只需了解是将数组L、R中浅颜色的元素从小到大依次填入数组A中

阅读全文 »

对于秒/毫秒级计时,我们可以使用其自带库函数。在头文件time.h中,clock() 函数返回从 开启这个程序进程 到 程序中调用clock()函数 时之间的CPU时钟计时单元数,返回单位是毫秒。另外,系统还定义了一个符号常量CLOCKS_PER_SEC。该常量等于每秒钟包括的系统时间单位数。因此,除以这个单位数,就可以得到秒数。time.h中将clock_t作为clock()作为clock()返回类型的别名。

对于微秒级计时,我们可以使用windows.h中的库函数QueryPerformanceCounter()。这个函数返回高精确度性能计数器的值,它可以以微妙为单位计时。由于该函数的精确计时的最小单位是与系统有关的,所以我们必须使用QueryPerformanceFrequency() 查询系统以得到QueryPerformanceCounter()返回的嘀哒声的频率,即返回每秒嘀哒声的个数。

阅读全文 »

插入排序法的时间复杂度为n的平方,对于较小的输入规模来说,插入排序法比合并排序法更快些。在最佳情况下,即输入数组已经排序好,则时间复杂度可表示为n,是一个线性函数;在最差情况下,即输入数组是逆序排列时,时间复杂度为 $an^2+bn+c$. 插入排序法的具体实现方法如下:

阅读全文 »

为成为国际语言,C++必须能处理需要16位的国际字符集Unicode,于是在传统的8位char型的基础上添加了wchar_t字符类型。在程序包含iostream文件时,将自动创建8个流对象:cin、cout、cerr、clog以及相对应的用于宽字符流的:wcin、wcout、wcerr、wclog。

阅读全文 »

在上篇文章《内存对齐》中说到了内存问题,今天我也遇到了可以用内存映射来解释的问题: 数组越界访问,出现死循环。

阅读全文 »

在了解内存对齐方式前,先介绍计算机的存储方式:Big Endian与Little Endian:

  • Big Endian: 即数据的高位在低地址,地位在高地址,并且把最高字节的地址作为变量的首地址
  • Little Endian: 即数据的高位在高地址,数据的低位在低地址,并且把最低字节的地址作为变量首地址。

    阅读全文 »

  1. 匈牙利命名法
    通过在变量名之前增加小写字母的符号前缀,以标识变量的属性、类型、作用域等参数。简单地说,即“变量名=属性+类型+对象描述”的形式。
    示例:m_lpszStr,表示指向以 0 字符结尾的字符串的长指针成员变量
  2. 骆驼命名法
    也叫驼峰式大小写。其主要规范为,混合使用大小写字母来构造变量名或函数名。
    示例:printEmployeePaychecks(),如代码所示,函数的每一个逻辑断点均用大写字母标识
  3. 帕斯卡命名法
    与骆驼命名法类似,骆驼命名法是首字母小写,而帕斯卡命名法则需要首字母大写。源自 Pascal 语言的命名惯例,也称为大驼峰式命名法。
    示例:LoginCheck(),string UserName
阅读全文 »

c++中头文件为 ,c中则是

这些函数以一个数值或者字符作为参数并返回布尔值true或flase,或者是字符,具体因函数不同

这里面的函数可以分为两类:

阅读全文 »

编程时经常要使用ASCII字符集,所以专门放在这里,以便日后查看:

阅读全文 »