Web Analytics
yangyang

码农兼一个普普通通小青年

All Posts


浅谈算法和数据结构: 四 快速排序

上篇文章介绍了时间复杂度为O(nlgn)的合并排序,本篇文章介绍时间复杂度同样为O(nlgn)但是排序速度比合并排序更快的快速排序(Quick Sort)。 快速排序是20世纪科技领域的十大算法之一 ,他由C. A. R. Hoare于1960年提出的一种划分交换排序。 快速排序也是一种采用分治法解决问题的一个典型应用。在很多编程语言中,对数组,列表进行的非稳定排序在内部实现中都使用的是快速排序。而且快速排序在面试中经常会遇到。 本文首先介绍快速排序的思路,算法的实现、分析、优化及改进,最后分析了.NET 中列表排序的内部实现。 一 原理 快速排序的基本思想如下: 对数组进行随机化。 从数列中取出一个数作为中轴数(pivot)。 将比这个数大的数放到它的右边,小于或等于它的数放到它的左边。 再对左右区间重复第三步,直到各区间只有一个数。 如上图所 …

Quick Sort Median of three partitioning 3-way partitioning

浅谈Excel开发:十一 针对64位Excel的插件的开发和部署

自Office 2010版本开始有了32位和64位之分,对Excel来说,32位的Excel和64位的Excel在性能上的主要区别是64位的Excel能够处理2G及2G以上的大数据集。 随着64位操作系统的安装,Office 2010及以上版本的普及以及计算机的内存容量越来越高,使用64位Excel的用户越来越多,所以让插件支持64位Excel能够赢得一部分用户。前面十篇文章中所讲解的技术适用于不同版本和不同位数的Excel,但是由于32位的COM组件不支持64位的Excel,所以在针对不同位数的Excel的编译和部署的时候,有些地方可能需要注意和有所不同。 64位版本的Office只能安装在64位的操作系统之上,32位的Office采用Windows-32-on-Windows-64 (WOW64) 技术可以安装在64位操作系统上,这也是32位Office在64位操作系统上的默认安装 …

Excel Development VSTO Shared Add-in

浅谈算法和数据结构: 三 合并排序

合并排序,顾名思义,就是通过将两个有序的序列合并为一个大的有序的序列的方式来实现排序。合并排序是一种典型的分治算法:首先将序列分为两部分,然后对每一部分进行循环递归的排序,然后逐个将结果进行合并。 合并排序最大的优点是它的时间复杂度为O(nlgn),这个是我们之前的选择排序和插入排序所达不到的。他还是一种稳定性排序,也就是相等的元素在序列中的相对位置在排序前后不会发生变化。他的唯一缺点是,需要利用额外的N的空间来进行排序。 一 原理 合并排序依赖于合并操作,即将两个已经排序的序列合并成一个序列,具体的过程如下: 申请空间,使其大小为两个已经排序序列之和,然后将待排序数组复制到该数组中。 设定两个指针,最初位置分别为两个已经排序序列的起始位置 比较复制数组中两个指针所指向的元素,选择相对小的元素放入到原始待排序数组中,并移动指针到下一位置 重复步骤3直到某一指 …

Merge Sort Algorithm

浅谈算法和数据结构: 二 基本排序算法

本篇开始学习排序算法。排序与我们日常生活中息息相关,比如,我们要从电话簿中找到某个联系人首先会按照姓氏排序、买火车票会按照出发时间或者时长排序、买东西会按照销量或者好评度排序、查找文件会按照修改时间排序等等。在计算机程序设计中,排序和查找也是最基本的算法,很多其他的算法都是以排序算法为基础,在一般的数据处理或分析中,通常第一步就是进行排序,比如说二分查找,首先要对数据进行排序。在Donald Knuth 的计算机程序设计的艺术这四卷书中,有一卷是专门介绍排序和查找的。 排序的算法有很多,在维基百科上有这么一个分类,另外大家有兴趣也可以直接上维基百科上看相关算法,本文也参考了上面的内容。 首先来看比较简单的选择排序(Selection sort),插入排序(Insertion sort),然后在分析插入排序的特征和缺点的基础上,介绍在插入排序基础上改进的希尔排序(Shell …

Selection Sort Shell Sort Insertion Sort

浅谈算法和数据结构: 一 栈和队列

最近晚上在家里看Algorithems,4th Edition,我买的英文版,觉得这本书写的比较浅显易懂,而且“图码并茂”,趁着这次机会打算好好学习做做笔记,这样也会印象深刻,这也是写这一系列文章的原因。另外普林斯顿大学在Coursera 上也有这本书同步的公开课,还有另外一门算法分析课,这门课程的作者也是这本书的作者,两门课都挺不错的。 计算机程序离不开算法和数据结构,本文简单介绍栈(Stack)和队列(Queue)的实现,.NET中与之相关的数据结构,典型应用等,希望能加深自己对这两个简单数据结构的理解。 1. 基本概念 概念很简单,栈 (Stack)是一种后进先出(last in first off,LIFO)的数据结构,而队列(Queue)则是一种先进先出 (fisrt in first out,FIFO)的结构,如下图: 2. 实现 现在来看如何实现以上 …


浅谈Excel开发:十 Excel 开发中与线程相关的若干问题

采用VSTO或者Shared Add-in等技术开发Excel插件,其实是在与Excel提供的API在打交道,Excel本身的组件大多数都是COM组件,也就是说通过Excel PIA来与COM进行交互。这其中会存在一些问题,这些问题如果处理不好,通常会导致在运行的时候会抛出难以调试的COM异常,从而导致我们开发出的Excel插件的不稳定。 和普通的WinForm程序一样,Excel也是一种STA(Single Thread Apartment)线程的应用程序,Excel插件是寄宿在Excel中运行的,这也就意味着插件也是一种STA线程的应用程序。插件在操作Excel的时候,如果是在Excel的主线程中,可以直接获取Excel对象进行操作,比如写入单元格值,对单元格进行格式化等操作。但是通常,我们会在多线程或者后台工作线程中去处理一系列复杂的数据或者逻辑,待处理完成获得结果 …

Excel STA COM Exception SynchronizationContext Excel Development

Word文档合并的一种实现

今天遇到一个问题,就是需要把多个Word文档的内容追加到一个目标Word文档的后面,如果我有目标文档a.doc以及其他很多个文档b.doc,c.doc…等等数量很多。这个问题,如果是在服务端的话,直接使用OpenXML技术,读写文档就可以实现,这样性能较稳定,但是需要对OpenXML有一定的了解。如果在客户端机器上,可以使用Word PIA实现。 由于本人对于Word PIA较熟悉,所以采用了该方法。但是在实现的过程中,也是有很多种思路的。 将b.doc打开,将其中的内容选中,复制到剪贴板,然后打开目标文件a.doc,通过代码将光标移到文档末尾,粘贴。粘贴一次保存一下文件,然后在打开c.doc重复以上过程,知道所有文件均添加完成。 将b.doc打开,将其中的内容选中,获取Range对象,然后打开目标文件a.doc,在里面通过代码插入b的内容。 以上两种方法都涉及 …


一种集合“相等性”的实现

最近在工作中遇到了一个小的功能,就是需要向一个服务发送请求命令,需要判断请求是否发生变化,如果发生变化了,则重新请求。该问题实际上就是判断两个集合是否相等,只需要记录最后一次请求的元素的集合,然后将其和最新一次进行比较是否相等。需要说明的是这里定义的集合相等是指:两个集合如果元素值一样并且出现的次数也一样,即使顺序不一样也认为是相等,比如集合A={1,2,3,4,4,5} 集合B={1,4,4,2,3,5} 这两个集合也认为是相等的。后面讨论的集合相等都是基于这一假设的。 就这么个简单的问题,也有不同种解决方法,这里和大家分享一下。 方法一 使用Dictionary计数来实现 这种方法思路很简单,创建一个Dictionary对象,将第一个集合中的元素作为key添加到Dictionary中,value即为出现的次数。然后遍历第二个集合,如果包含相同的 …


浅谈Excel开发:九 Excel 开发中遇到的常见问题及解决方法

Excel开发过程中有时候会遇到各种奇怪的问题,下面就列出一些本人在开发中遇到的一些比较典型的问题,并给出了解决方法,希望对大家有所帮助。 一 插件调试不了以及错误导致崩溃的问题 在开发机器上,有时可能会装有多个版本的.NET运行时,有时候也可能装有多个版本的Visual Studio,本人的开发机器上就安装了3个版本的Visual Studio,在最新的Visual Studio 2013出来之后,就迫不及待的把工程文件迁移到2013上来了,但是在设置了启动程序之后,调试的时候,断点根本不能命中,也调试不进去。即使使用Attached to process方式也不行。 该问题是由于在安装有多个.NET版本的机器上,由于某些原因,会导致Excel不知道为Com Add-in加载哪个版本的Framework导致的。注:这里仅针对是用.NET技术开发Shared Add-in插件 …

Excel Development

浅谈Excel开发:八 Excel 项目的安装部署

前面几篇文章讲解了Excel开发的几个比较主要的也是比较重要的方面,比如菜单系统,Excel对象模型,自定义函数,RTD函数,异步自定义函数,用户自定义任务面板等,在实际开发中我们还会遇到各种“千奇百怪”的问题,以及开发中的一些注意事项和技巧等,后面有空我会写文介绍。当我们的Excel外接应用程序开发好了之后,需要给用户使用,这就涉及到了应用程序的安装与部署,本文就简要介绍下Excel项目的安装和部署。 和一般的.NET 中的Windows Form程序不同,Excel开发通常是一种插件式的开发机制,它需要借宿在Excel上,并通过调用Excel的API来实现特定的业务逻辑。宿主Excel在运行的时候,会根据当前用户以及Excel版本信息,读取注册表特定位置,以查找在本机当前用户下面注册的插件信息,然后逐个加载。这里面就涉及到了和安装部署相关的一些 …

Excel Development Shared Add-in