这个排序算法为什么被命名为Shell排序，我一直幻想着它可能最早被用以Shell脚本吧，Just Now我才知道，发明人叫做Donald Shell，居然有人叫自己壳？
以前从来没有写过这个排序，事实证明，没写过基本等于没听说过、没学过。
21行的小程序花了我将近一个小时来调试，对一个大小为9的逆序用gdb跟踪了程序整个的执行过程，发现两处错误，迭代变量j的类型习惯性地写成了size_t，导致死循环，以后凡是这种i,j,k，一律int。还有就是把最外层的while(step > 0)写成了while(size > 0)，纯属自作自受。
Posts Tagged ‘排序’
November 16, 2009
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
