0%

时间复杂度:$O(n)$.

基本思想:和快速排序的思想相似,也是对数组进行递归划分,但是有所差别的是,快速排序会递归处理划分的两边,而随机化的选择算法只选择一边。

阅读全文 »

时间复杂度:$O(3*floor(n/2))$

基本思想:成对地处理元素。先将一对输入元素相互比较,然后把较小的与当前最小值比较,较大的与当前最大值比较,因此每两个元素比较三次。

阅读全文 »

比较排序:通过元素间的比较对序列进行排序的算法称为比较排序。

常见的比较排序算法有:冒泡排序法、插入排序法、合并排序法、快速排序法,堆排序法等等。任何比较排序法在最坏情况下的时间复杂度为$O(nlogn)$。因此,合并排序和堆排序是渐进最优的

阅读全文 »

​ 快速排序的最坏运行时间为$O(n^2)$,虽然这最坏情况的时间复杂度比较大,但快速排序通常是用于排序的最佳实用选择,这是因为其平均性能相当好,平均时间复杂度为$O(nlogn)$,并且$O(nlogn)$中的隐含常数因子很小。另外,它能够进行就地排序,因此在虚拟内存中也能较好的运行。

阅读全文 »

​ 堆排序像合并排序一样,时间复杂度为$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。

阅读全文 »

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

阅读全文 »