存档

文章标签 ‘反转内存’

二路归并 & 插入归并 & 原地归并

2012年5月31日 4 条评论

---

本节回顾整理归并排序算法常见的几种形式,并实现。一般来讲,我们所说的归并排序都是指二路归并(非多路归并),归并排序很基础,其涉及的分治思想应用也很广泛。这里不赘述基本归并排序的思想。

插入归并

归并排序的时间复杂度为O(nlgn),空间复杂度为O(n);

但是一般来讲,基于从单个记录开始两两归并的排序并不是特别提倡,一种比较常用的改进就是结合插入排序,即先利用插入排序获得较长的有序子序列,然后再两两归并(改进后的归并亦是稳定的,因为插入排序是稳定的)。之所以这样改进是有原因的:尽管插入排序的最坏情况是O(n^2),看起来大于归并的最坏情况O(nlgn),但通常情况下,由于插入排序的常数因子使得它在n比较小的情况下能运行的更快一些,因此,归并时,当子问题足够小时,采用插入排序是比较合适的。

复杂度分析

下面分析下插入归并排序最坏情况下的复杂度:假设整个序列长度为n,当子序列长度为k时,采取插入排序策略,这样一共有n/k个子序列。

子序列完成排序复杂度:最坏情况下,n/k个子序列完成排序的时间复杂度为O(nk)。证明:每个子序列完成插入排序复杂度为O(k^2),一共n/k个子序列,故为O(nk)。

子序列完成合并复杂度:最坏情况下,合并两个子序列的时间复杂度为O(n),一共有n/k个子序列,两两合并,共需要lg(n/k)步的合并,所以这些子序列完成合并的复杂度为O(nlg(n/k))。

所以改进后的插入归并排序的最坏情况的复杂度为O(nk+nlg(n/k)),这里k的最大取值不能超过lgn,显然如果k大于lgn,复杂度就不是与归并一个级别了,也就是说假设一个1000长度的数组,采用插入策略排序子序列时,子序列的最大长度不能超过10。

阅读全文...

交换两段连续(不连续)内存

2011年9月4日 没有评论

在《编程珠玑,第二版》和《编程之美》中都有关于交换两段连续的内存块的题目,而且非常经典,交换两段连续内存块的问题又可以延伸到交换两段不连续内存块的问题,无论是哪种情况都需要一个基本操作:反转内存块

反转内存时,比较简单,可以两个指针同时走,也可以一个指针,随意,实现如下:

01 // reverse the memory block
02 // goal: |12345| -> |54321|
03 void * reverseMemory(void *pMemory, const size_t memSize)
04 {
05     if(NULL == pMemory) return pMemory;
06     if(memSize < 2)        return pMemory;
07
08     char * beg = static_cast<char *>(pMemory);
09     char * end = beg + memSize -1;
10     for(; beg < end; ++beg, --end)
11     {
12         char memTmp = *beg;
13         *beg = *end;
14         *end = memTmp;
15     }
16     return pMemory;
17 }

其中,函数的两个形参分别为要反转内存的起始地址和内存块的大小。返回值类型为void*,指向反转内存块的起始地址。

实现了反转内存块这一基本操作后,我们就可以用它来交换两段连续的内存,从而解决类似“数组循环移位”的问题。具体算法在编程珠玑和编程之美中都有详细介绍,这里简单说一下:

假设有连续的内存块M和N形如:|----M---|--------N---------|

  1. 首先反转内存块M:M’=reverse(M)
  2. 反转内存块N:N’=reverse(N)
  3. 对整个内存块M’ N’进行反转:(M’N’)’ = NM


阅读全文...