如何提高编程效率

摘要：本文主要通过slit算法的功能模块划分，在实现该运算别注意内存空间的分配与排序算法的选择，通过分析排序算法的优劣来选择适当的排序算法。文章最后总结该过程，得到如何提高编程效率的心得。

关键词：slit算法；排序算法

中图分类号：TP311.1文献标识码：A文章编号：1007-9599 (2011) 16-0000-01

How to Improve Programming Efficiency

Li Juan

(Dezhou Vocational and Technical College,Dezhou253034,China)

Abstract:This paper mainly through slit function module division algorithm,particularly in the realization of the operator's attention to memory allocation and the choice of sorting algorithm,sorting algorithm by analyzing the pros and cons to select the appropriate sorting algorithm.Article concluded that the process has been how to improve the efficiency of programming experience.

Keywords:Slit algorithm;Sorting algorithm

一、引言

数据结构作为程序设计的基础，其对算法效率的影响必然是不可忽视的。本文就是通过实现slit算法的功能模块划分来分析如何合理选择数据结构来优化算法这一问题，对选择数据结构的原则和方法进行了一些探讨。首先对数据逻辑结构的重要性进行了分析，提出了选择逻辑结构的两个基本原则；接着又比较了顺序和链式两种存储结构的优点和缺点，并讨论了选择数据存储结构的方法；最后本文从选择数据结构的的另一角度出发，进一步探讨了如何将多种数据结构进行结合的方法。在讨论方法的同时，本文还结合实际，选用了一些较具有代表性的信息举例进行了分析。该问题的描述：求若干矩形的OR运算，所用算法slit（利用图形的对称性进行分割，从而集成一个大图形，即所求矩形）。

二、实现slit算法的功能模块划分

（1）getOneFData.cpp从输入文件中以点为单位读取数据，存放到指定链表中。（2）getLineList.cpp把以点为单位所读取的数据转换成以线段为单位，存放到指定的“Line”结构链表中。（3）sortLine.cpp把“Line”结构链表中的线段先按照Y轴（升序）再按照X轴（升序）排序。（4）getQ.cpp通过slit算法来切割线段，从而产生所需要的“小”矩形并输出到指定文件中。（5）mainSlit.cpp通过调用以上各个模块，来完成整个功能。

三、分类

（一）计算的复杂度（时间和空间），依据串列（list）的大小（n）。一般而言，好的表现是O（nlog n），最坏的行为是O（n2）。对于一个排序理想的表现是O（n）。

（二）记忆体使用量。稳定度：稳定排序算法会依照相等的关键（换言之就是值）维持纪录的相对次序。也就是一个排序算法是稳定的，就是当有两个有相等关键的记录R和S，且在原本的串列中R出现在S之前，在排序过的串列中R也将会是在S之前。

一般的方法：插入、交换、选择、合并等等。交换排序包含冒泡排序（bubble sort）和快速排序（quicksort）。选择排序包含shaker排序和堆排序（heapsort）。当相等的元素是无法分辨的，比如像是整数，稳定度并不是一个问题。然而，假设以下的数对将要以他们的第一个数字来排序。

（4，1）（3，1）（3，7）（5，6）

在这个状况下，有可能产生两种不同的结果，一个是依照相等的键值维持相对的次序，而另外一个则没有：

（3，1）（3，7）（4，1）（5，6）（维持次序）

（3，7）（3，1）（4，1）（5，6）（次序被改变）

不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但是稳定排序算法从来不会如此。

四、排列算法

在这些排列算法中，n是要被排序的纪录数量以及k是不同键值的数量。包括稳定的和不稳定的，具体如下：

（一）稳定的。

冒泡排序（bubble sort）―O（n2）

鸡尾酒排序（Cocktail sort，双向的冒泡排序）―O（n2）

插入排序（insertion sort）―O（n2）

计数排序（counting sort）―O（n+k）；需要O（n+k）额外记忆体

归并排序（merge sort）―O（n log n）；需要O（n）额外记忆体

原地归并排序―O（n2）

二叉树排序（Binary tree sort）―O（n log n）；需要O（n）额外记忆体

基数排序（radix sort）―O（n•k）；需要O（n）额外记忆体

（二）不稳定的。

选择排序（selection sort）―O（n2）

希尔排序（shell sort）―O（n log n）

快速排序（quicksort）―O（n log n）期望时间，O（n2）最坏情况；

对于大的、乱数串列一般相信是最快的已知排序

Introsort―O（n log n）

Patience sorting―O（n log n+k）最好情况；需要额外的O（n+k）空间，也需要找到最长的递增子序列（longest increasing subsequence）所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

在众多的排序法中之所以选择了带flag的冒泡排序法，而没有选择速度明显快很多的快速排序法，主要是针对特定的数据而言的。虽然引用计数的处理方法貌似不错，但是其亦存在其弊端：在多线程的条件下，其执行效率尤为低下。重要是因为快排法中，所选的转轴值是不确定的，当该转轴值是该组数中的中间值时效率是最好的，此时qsort（）递归所分的线程是最少的，其时间复杂度为O（nlogn）。但是当转轴值没选好，其值靠近两段时，会分配大量线程。特别是针对本程序中处理的数据是图形，量特别大，那么CPU会耗费大量的时间去进行任务间的跳转，不停地把任务挂起，段间的跳转，反到没去干它该干的“实事”，极大地降低了效率。

五、结论

并不是好的算法就一定能有高的效率，我们应该根据不同的环境和数据选择不同的算法，挖掘出数据与处理过程即算法的匹配度，这样才能有高的效率。

参考文献：

[1]钱能.C++程序设计教程[M].北京:清华大学出版社,2010:76-125

[2]潭浩强.C语言程序设计[M].北京:清华大学出版社,2008:34-186

[3]严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,2010:12-201