递归是一种使用相同的方法，通过解决问题的子集以达到解决整个问题的方法，是一种使用有限代码解决“无限”计算的方法。在C/C++语言中递归表现在函数对自身的直接/间接的调用上，在实现上，递归依赖于语言的运行时调用堆栈，使用堆栈来保存每一次递归调用返回时所需要的条件。递归通常具有简洁的编码和清晰的思路，但这种简洁是有代价的。一方面，是函数调用的负担；另一方面，是堆栈占用的负担（堆栈的大小是有限的）。
避免这种负担的方法就是将递归转化为迭代。迭代的思想主要在于，在同一栈帧中不断使用现有数据计算出新的数据，然后使用新的数据来替换原有数据。递归于迭代可以相互转化。将递归转化为迭代需要做两方面的工作：显式地维护一个堆栈，在递归算法中堆栈的维护由编译器隐式地完成；使用迭代控制结构，完成出栈、入栈和相关的计算。
Posts Tagged ‘排序’
April 29, 2011
October 18, 2010
简单实现了常见的几种内部排序算法，包括冒泡（Bubble），插入（Insert），快速排序（Quick Sort），堆排序（Heap Sort），归并（Merge），希尔排序（Shell Sort），并对这些算法的耗时在伪随机数上进行了简单的测试。
说明：
- 没有实现计数、基数排序等线性复杂度的算法；
- 各算法只是对算法思想的一次简单模拟，没有过多的优化；
- 各排序主程序接口参数均为整型数组及元素个数；
- 程序计时使用了glibc的gettimeofday()，因此。。。；
- 归并排序中，每次调用都申请和释放堆空间，因此比较耗时。可以采用原地归并、使用全局/静态的方法加以优化；
- 快速排序中，对待排子序列的长度进行的了判断，对短序列进行优先排序可以减小函数的递归深度（而不是次数）；
- 希尔排序中，为了简洁，步长因子统一取做2.2（11/5）。
July 6, 2010
对qsort需要注意几点：
- qsort中第一个参数是待排序数组的开始地址，既然是数组，各元素就是同类型、同大小的对象，且数组是“一维数组”（即地址是连续的）；
- qsort用以区分对象的依据是第二和第三个参数，分别表示对象个数和每个对象的大小（字节）；
- qsort并不知道每个对象的类型和结构，排序准则由用户在第四个参数（比较函数）中指出，qsort按该比较函数准则的“升序”对数组进行排序；
- 标准C不支持运算符重载，各对象的交换（因为这是qsort）靠的是逐字节的拷贝（memcpy?）。
在上面的两片代码中，待排序的对象一个是字符型指针，一个是char (*)[10]型数组。然后，就没有然后了。
November 16, 2009
这个排序算法为什么被命名为Shell排序，我一直幻想着它可能最早被用以Shell脚本吧，Just Now我才知道，发明人叫做Donald Shell，居然有人叫自己壳？
以前从来没有写过这个排序，事实证明，没写过基本等于没听说过、没学过。
21行的小程序花了我将近一个小时来调试，对一个大小为9的逆序用gdb跟踪了程序整个的执行过程，发现两处错误，迭代变量j的类型习惯性地写成了size_t，导致死循环，以后凡是这种i,j,k，一律int。还有就是把最外层的while(step > 0)写成了while(size > 0)，纯属自作自受。
October 4, 2009
一个最小堆的C++模板。什么东西都想封装成类，做成模板，即使它仅仅就是一个普通的函数，尤其是用到一些全局的对象时，觉得封装成类看起来更紧凑一点，使用起来也更方便更顺手一些。这个最小堆模板实现了以下几个小特性：
容量不足时，能够动态地调整大小；
可以用一个数组来初始化，并建立最小堆；
没有复制构造，^*^.
August 24, 2009
没啥好说的，只是要注意防止m = (r + l) / 2;时m会发生上溢。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | template <class T> int BSearch(T *a, size_t n, T v) { assert(a != NULL && n > 0); //! a == NULL || n <= 0 就坏了:-( size_t l = 0, r = n -1, m = l + (r - l) / 2; //! 勿用m=(l+r)/2; while(l <= r) { if(a[m] == v) return (int)m; else if(a[m] < v) l = m + 1; else r = m - 1; } return -1; } |
August 23, 2009
归并排序算法(mergesort)是将一个序列划分为同样大小的两个子序列，然后对两个子序列分别进行排序，最后进行合并操作，将两个子序列合成有序的序列。在合成的过程中，一般的实现都需要开辟一块与原序列大小相同的空间，以进行合并操作。这里介绍一种不需要开辟新的空间就可以进行归并操作的原地归并算法。代码来说事儿：
1 2 3 4 5 6 7 8 9 | //~ 原地归并 while(l < r && r < size) //~ 核心算法 { while(v[l] <= v[r] && l < r) ++l; //~ 找到左面第一个比v[r]大的v[l] size_t to_mv = 0; //~ 计数器 while(v[r] < v[l] && r < size) ++r, ++to_mv; //~ 右侧找到to_mv个比v[l]小的数 Exchange(v+l, r-l-to_mv, r-l);//~ 将此to_mv个数移到v[l]前面 l += to_mv; //~ 改变l，继续下一轮循环 }//~ l >-r 或者 r >= size时归并结束 |
July 20, 2009
题目描述：
给你n个整数，用这n个拼成一个超长的整数，要令这个新的整数最小
输入：
多组测试数据，每组第一行为n(1<=n<=1000)，接下来是n个正整数，使用空格或者换行分开;
每个数字的长度不会超过1000，不存在前导0;
当n为0时结束程序.
输出：
对于每组输入，输出拼成的新的整数的结果
July 9, 2009
由于归并排序需要O(n)的额外空间，在普通函数中，我实在想不出好的办法来申请这块内存。于是只好把他写成一个模板类：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | template <class T> class Merger { public: Merger(T* array, size_t n):extra(new T[n/2]) //~ 归并需要O(n)的额外空间 { sub_Merger(array, n); //~ 调用递归子函数 } ~Merger() { delete [] extra; //~ 释放内存 } private: T* extra; Merger(); void sub_Merger(T* array, size_t n); }; |
如果你有什么好的建议的话，敬请赐教，不胜感激涕零！:)
May 1, 2009
算法：
1 2 3 4 5 | for i = 2:n, for (k = i; k > 1 and a[k] < a[k-1]; k--) swap a[k,k-1] → invariant: a[1..i] is sorted end |
算法性质：
- 稳定
- 需要O(1)的额外空间开销
- 需要O(n2)复杂度的比较和交换。
- 具有自适应性：当待排序序列接近有序时，复杂度为O(n)。
- 开销较低
讨论：
虽然在最坏情况下，插入法排序的复杂度为O(n2)，但当序列已经接近有序(算法具有自适应性)或者问题规模比较小(空间开销很小)时，插入法排序还是一种比较好的选择。所以，插入法排序，通常可以作为其他诸如归并排序、快速排序等递归递归排序的基础。
Page 1 of 11